È possibile creare un algoritmo di generatore di numeri casuali più sicuro mediante XORing di due o più algoritmi di numeri casuali meno sicuri?

Poiché questo non sembra essere stato ancora fatto, suggerirò una risposta da un punto di vista puramente teorico:

Sia X, Y due variabili casuali in {0,1} ^ n. Sia f (x, y) = x XOR y

Ora, H (X, Y) = H (X) + H (Y | X) = H (Y) + H (X | Y), e poiché l'entropia dell'informazione è sempre non negativa, abbiamo H (X , Y) > = H (X) e H (X, Y) > = H (Y). Quindi la variabile casuale join (X, Y) ha almeno un'entropia pari a quella di ogni singola variabile casuale (l'uguaglianza si verifica quando una variabile casuale dipende perfettamente dall'altra).

Tuttavia, quando si applica una funzione a una variabile casuale, si riduce la sua entropia (nessuna riduzione se f è biiettiva, ma questo non è certamente vero per il nostro caso), quindi abbiamo H (f (X, Y)) < H (X, Y). Una prova è qui (domanda due).

Ora, la domanda di OP è se è possibile rendere H (f (X, Y)) più grande di entrambi H (X) e H (Y)? La risposta è sì.

Scriviamo X come (X_1, ..., X_n) e Y come (Y_1, ..., Y_n). Consideriamo ora un caso estremo in cui X_1 è costante e il resto dei bit sono iid Bernoulli con p = 0.5, e Y_1 è Bernoulli con p = 0.5 e indipendente da X, mentre gli altri bit di Y sono costanti, quindi H (X) = n-1, H (Y) = 1 e H (f (X, Y)) = n, maggiore di entrambi H (X) e H (Y).

Questa potrebbe non essere una risposta molto interessante, ma penso che risponda esattamente a ciò che l'OP chiede.

Modifica

Penso che una domanda che l'OP ha in mente sia: è possibile ottenere un numero casuale peggiore di entrambi gli input quando lo facciamo? La risposta è anche sì. Considera X Bernoulli con p = 0.5. E Y = NON X. Prima di combinare X e Y, otteniamo H (X) = H (Y) = 1. Ma, X XOR Y == 1, quindi H (f (X, Y)) = 0! Oops ... Quindi sicuramente non solo XOR arbitrariamente due numeri casuali e aspettati di ottenerne uno migliore.

EDIT 2:

Una discussione interessante di seguito ha fatto sorgere una domanda importante: se X e Y sono indipendenti, X XOR è almeno casuale come sia X che Y? Mark ha assolutamente ragione: la risposta è sì.

Ecco perché:

Prima nota che per qualsiasi due variabili casuali U e V, abbiamo H (U) > = H (U | V). L'uguaglianza vale quando U e V sono indipendenti. Intuitivamente, questo significa che conoscere qualcosa su V non fa mai male se stiamo cercando di scoprire dove si trova U. Una dimostrazione formale riduce H (U) -H (U | V) a una divergenza KL, che è sempre non negativa.

Ora, usando la stessa notazione di cui sopra, abbiamo:

H (f (X, Y), X) = H (f (X, Y) | X) + H (X) = H (X | f (X, Y)) + H (f (X, Y))

Poiché per ogni x fissa, abbiamo H (f (x, Y)) = H (Y) (attenzione: non vero per arbitrario f, ma abbiamo questo dato che abbiamo definito f (x, y) essere x XOR y), abbiamo H (f (X, Y) | X) = H (Y), e questo ci dà:

H (X) + H (Y) = H (X | f (X, Y)) + H (f (X, Y))

Ma poiché H (X) > = H (X | f (X, Y)), abbiamo:

H (Y) < = H (f (X, Y))

e per simmetria:

H (X) < = H (f (X, Y))

Quindi questa è una buona notizia. La cattiva notizia è che testare l'indipendenza non è probabilmente più facile che provare la casualità, se non più difficile. Quindi non ci aiuta tanto come sembra.

btw, come si sentono tutti a chiedere a SE di abilitare MathJax qui in modo che possiamo fare alcuni calcoli matematici quando necessario?

Non consiglierei di combinare generatori di numeri casuali in questo modo senza avere una teoria di base per supportare il tuo caso.

Un modo semplice per illustrare i problemi è considerare il comportamento degli algoritmi LCG di fascia bassa, i famosi schemi "one-liner" per generare numeri casuali.

Questi possono essere fatti per produrre sequenze che supereranno determinati test statistici, ma non sono adatti per applicazioni crittografiche. Un difetto noto in tali generatori è che i bit di basso ordine non sono casuali. Ad esempio, ho osservato il bit basso per oscillare tra 0/1 e se hai due generatori come questo, e XOR quel bit basso, e i generatori sono in fase o fuori fase, in entrambi i casi il risultato di lo XOR è piuttosto prevedibile. Non è chiaro se hai migliorato la situazione, ma potrebbe aver peggiorato la situazione.

Nella discussione di Knuth sulla generazione di numeri casuali, presenta un divertente esempio dei suoi tentativi di costruire un generatore "super deluxe".

Probabilmente questo sembra uno snark, ma la tua soluzione migliora solo la situazione se i due PRNG vengono scelti con sufficiente casualità. Pensa al motivo per cui consideriamo un PRNG debole come insicuro: il risultato è statisticamente facile da indovinare in parte o in parte, risultando in operazioni crittografiche e di altro tipo che possono essere attaccate conoscendo parte dei dati di input. Se si passa da un PRNG a due PRNG, l'hacker deve semplicemente conoscere entrambi i PRNG (o indovinarli un paio di volte) prima che possano ridurre la forza potenziale di entrambi (fornendo più dati di input casuali) nella debolezza dell'altro ( fornire dati di input ipotetici). Probabilmente puoi migliorare statisticamente la forza se sviluppi un algoritmo alimentato con PRNG per scegliere quali due (o, meglio ancora, più) PRNG a caso, ma è solo un fattore lontano dalla stessa debolezza con cui hai iniziato. Meglio, probabilmente, cercare in un singolo PRNG più sicuro.

È abbastanza possibile creare un RNG più strong usando il metodo suggerito, tuttavia è anche possibile creare un RNG più debole, o uno che non migliora. Il risultato finale dipende dalle proprietà degli RNG più deboli. La distribuzione e il bias dei bit hanno lo stesso effetto del livello di entropia. Solo un'attenta analisi e conoscenza dell'intero schema può dire se la forza migliora e se ci sono potenziali problemi possono compromettere la sicurezza.

Considera i seguenti 2 RNG deboli, A e B .
A produce un flusso di bit in cui ogni bit dispari è 0, e ogni bit pari è crittograficamente pseudocasuale.
B produce un flusso di bit in cui ogni bit pari è 0 e ogni bit dispari è crittograficamente pseudocasuale.
Lo stream XOR risultante C ha una pseudo-casualità crittografica completa ed è ovviamente più strong degli altri, assumendo semi indipendenti.

Considera ora quanto segue.
A è l'output bitstream di Dual_EC_DRBG con costanti backdoor NSA. I risultati futuri sono prevedibili per un utente malintenzionato che può osservare l'output non elaborato del flusso di bit.
B è l'output bitstream da un hash MD5 ciclico su un numero casuale, in cui l'output futuro è l'hash dell'output corrente. I risultati futuri sono prevedibili per un utente malintenzionato che può osservare l'output non elaborato del flusso di bit.
Lo stream XOR risultante C non è più prevedibile allo stesso modo dei suoi componenti. Se un utente malintenzionato è in grado di visualizzare l'output di A o B da solo, C non è più sicuro. Il recupero del seed per MD5 rende immediatamente prevedibili tutti gli output futuri, deve essere abbastanza grande da prevenire un attacco di forza bruta. La sicurezza dello stream non è migliore dello sforzo di lavoro per ripristinare e verificare il seed MD5 o uno dei valori hash iterati.

E infine.
A è l'output bitstream di AES-CTR in cui la chiave è nota all'NSA.
B è l'output bitstream di AES-CTR in cui la chiave è nota al KGB.
Lo stream XOR risultante C è sicuro e imprevedibile per entrambe le agenzie in assenza di collusione, il che renderebbe l'output completamente prevedibile.

Questi esempi mostrano che i bitstreams con entropia debole o output prevedibile possono essere resi più sicuri da XORing insieme, date le proprietà e le condizioni corrette. Ciò non li rende necessariamente completamente sicuri.

A meno che uno sia perfettamente casuale, i risultati finali non sono chiari . Ma se uno fosse perfettamente casuale, non sarebbe più debole.

Modifica: a meno che tu non sia sicuro che i due siano completamente indipendenti l'uno dall'altro, i vantaggi potrebbero non essere chiari.

La risposta rapida ma eccessivamente vaga alla tua domanda originale è: Sì.

Tuttavia, come la maggior parte delle persone ha indicato: più sicuro! = sicuro.

Lo scopo degli RNG / PRNG è di produrre entropia sufficiente a rendere impossibile per un utente malintenzionato di indovinare sufficienti informazioni per recuperare sufficienti dati protetti.

La maggior parte delle fonti di entropia viene testata per determinare se contengono una sequenza sufficientemente mista di 0 e 1 binari in modo tale che semplicemente "indovinare" la successiva cifra binaria sarebbe errata approssimativamente il 50% delle volte.

Ci sono un paio di elementi sottostanti che determinano cosa significa "sufficientemente mescolato".

Prima , è il rapporto effettivo tra 1 e 0 nell'output:

Ad esempio, se il PRNG ha prodotto 110110101011101, allora dei 15 bit che abbiamo generato c'erano 10 di loro impostati su 1, che è il 66% dello spazio di entropia. Un attaccante che anticipa questo tipo di PRNG sarebbe "meglio" supponendo che ci siano complessivamente più 1 di 0, quindi per ogni bit essi preferirebbero impostarlo su 1 e 2/3 del tempo in cui sarebbero corretti.

Al contrario, un PRNG che ha prodotto 011011000100110 ha otto 0 e 7 1, che favoriscono uno 0 bit contro un 1 bit al 53%: 47%. Pertanto, l'attaccante che cerca di sconfiggere questo sistema ha fondamentalmente poco vantaggio nell'indovinare uno 0 su un 1 (... circa il 6% di probabilità migliori).

Idealmente, più vicino a 50:50 ottieni più protezione per questa prima caratteristica di protezione.

Secondi , è la casualità dell'entropia tale che non è possibile distinguere un modello . Ad esempio, se il PRNG emette un rapporto di bit perfetto per gli 0 e gli 1 di 50:50, ma è possibile osservare un modello, il vantaggio del sistema è ridotto.

Considera la seguente entropia a 16 bit: 1010101010101010 Bene, abbiamo sicuramente superato il primo requisito di avere una perfetta distribuzione bit-bit del 50% 0 e del 50% 1; tuttavia, come puoi banalmente osservare questo non è sicuro. Lo stesso si può dire per: 0011001100110011 o 0000000011111111.

Esiste un modello discernibile per l'output di entropia. I pattern sono la rovina delle operazioni crittografiche perché perdono informazioni che riducono l'efficacia complessiva dell'algoritmo.

Ora come esempio migliore, vediamo la seguente sequenza PRNG a 16 cifre: 0001011011000111 Questa uscita è molto più "casuale" rispetto ai precedenti diversi esempi in questa sezione. Certo, ci sono 2 sequenze in cui ci sono tre 0 di fila, ma date queste prime 16 cifre puoi indovinare banalmente quando la terza sequenza di tre 0 verrebbe visualizzata? Non è così facile.

Quindi per riportare questo alla tua domanda originale: se hai combinato due fonti di entropia deboli e successivamente assicurato che il loro XOR risultante ha prodotto un rapporto quasi uguale tra 0 e 1 E non c'erano motivi ovvi per l'output allora POTREBBE produrre un generatore di numeri pseudo casuali più strong di quanto uno dei due sarebbe stato da solo.

Nota: per aggirare alcuni dei problemi che altri hanno citato (come lo stato prevedibile del bit inferiore) puoi spostare uno o entrambi weak_random1 e < em> weak_random2 di un certo numero di bit prima di condurre lo XOR. Ad esempio, sposta work_random1 per 3 bit e sposta weak_random2 per 5 bit. Tranne il fatto che ho rivelato i valori di shift (3 e 5, rispettivamente), questo avrebbe "strapazzato" i valori che erano tradizionalmente indovinati / prevedibili in diverse posizioni nelle rispettive stringhe PRNG prima Operazione XOR che rende la prevedibilità molto più difficile.

Tutto ciò detto, suggerisco di usare una fonte casuale migliore per cominciare! Sebbene sia possibile ottenere ciò che stai chiedendo, conosco pochi matematici che direbbero che è facile da realizzare e meno che lo considererebbero una soluzione sicura.

Buona fortuna:)

Un potenziale problema che vedo è se il primo generatore di numeri casuali genera numeri casuali uguali o simili al secondo. Se i numeri prodotti dagli algoritmi corrispondono esattamente, il numero risultante sarebbe 0, che non è molto sicuro. Fintanto che gli algoritmi sono sufficientemente diversi, questo trabocchetto probabilmente non dovrebbe accadere. Accolgo con favore ulteriori discussioni su questo.