Dal momento che Garbage Collection non è deterministico, perché non viene utilizzato per la generazione sicura di numeri casuali?

13

Ho capito che / dev / random è una buona fonte di entropia, ed è quello che viene solitamente usato-- È come sto leggendo su GC, almeno in Java, sembra accettato che il demone della raccolta dei dati inutili venga eseguito non deterministicamente. Se questo è vero, perché non usiamo i tempi della garbage collection come fonte di entropia invece della variabile / dev / random?

    
posta edthethird 03.11.2013 - 22:19
fonte

2 risposte

58

"Non specificato" e "casuale" sono due concetti completamente diversi.

Il funzionamento esatto di un garbage collector non è specificato e dipende dal garbage collector (solitamente implementato da una VM di sorta, ma non necessariamente).

Pertanto, non hai un tempo specifico (cioè deterministico) in cui raccogliere i rifiuti.

Tuttavia qualsiasi implementazione fornita seguirà alcune regole e vi è un'alta probabilità che due esecuzioni successive dello stesso programma presentino pattern di garbage collection molto simili.

Quindi l'effettiva entropia fornita da un garbage collector sarebbe molto bassa (e scoprendo quali parti puoi usare come l'entropia essere ingannevole).

Come confronto: un HashMap in Java non garantisce alcun ordine di recupero per i suoi membri (fondamentalmente perché garantirebbe un sovraccarico che non vale la pena pagare, il più delle volte). Tuttavia per un'implementazione data e un insieme dato di inserimenti / rimuovi puoi sicuramente calcolare l'ordine risultante. Solo perché non esiste alcuna garanzia per un determinato ordine, non significa che l'ordine sia casuale.

    
risposta data 03.11.2013 - 22:26
fonte
8

In primo luogo, dobbiamo stare attenti a non cadere nella trappola del ragionamento mediante la manipolazione di semplici parole. Per esempio, potremmo chiedere, dal momento che un NFA è un "automa finito non deterministico", perché non lo usiamo per ottenere numeri casuali? In tal caso, sarebbe perché non è quello che "non deterministico" significa in un NFA; infatti, quando simuliamo un NFA, su un dato input, il comportamento della simulazione è perfettamente deterministico.

"Deterministico" è una frase caricata. Per un programmatore di computer o uno scienziato informatico, un comportamento non deterministico significa semplicemente "determinare il comportamento esatto a cui è difficile pensare" e dipende da troppi fattori, incluso l'input del programma.

Tuttavia, ciò non significa che non sia deterministico per qualcuno motivato ad attaccare un sistema crittografico. A volte fattori ambientali e fattori di produzione possono essere bloccati e schemi ripetibili emergono dal comportamento "non deterministico".

    
risposta data 04.11.2013 - 05:47
fonte

Leggi altre domande sui tag