Come creare un generatore casuale

La chiave per un numero veramente casuale è un'origine dati casuale. A volte si tratta di informazioni come ritardi negli eventi della tastiera o eventi di rete. Quando si desiderano dati casuali di alta qualità, potrebbe essere decadimento radioattivo . SGI ha implementato lavarand che ha estratto il seme per un generatore di numeri casuali da un'immagine digitalizzata di una lampada di lava. Questo era sufficiente per essere considerato un generatore di numeri casuali.

Al di fuori di dati veramente casuali, si può lavorare con un sistema deterministico ma caotico. Ad esempio, il mersenne twister . In queste situazioni, uno semina il generatore con un numero e poi lo avvia in avanti per ottenere numeri pseudo-casuali. Questi sono sufficienti per giochi e simili dove non è fondamentale se qualcuno può determinare il seme (e il numero successivo nella sequenza).

Considera di leggere il brevetto 5.732.138 e link per i dettagli di implementazione su come creare un numero.

Che tipo di casuale stai parlando?

Ci sono due proprietà principali che definiscono casuali in senso matematico: la prima è imprevedibilità e la seconda è distribuzione uniforme .

Se parli del primo, generalmente è quasi impossibile generarlo interamente all'interno del software (e farlo correttamente). Esistono alcuni modi, come la raccolta di entropia da dispositivi di interfaccia umani, ad es. /dev/random in Linux, ma generiamo un livello di entropia piuttosto basso per essere utile. Altri hanno già indicato alcune implementazioni hardware. Tutti hanno radici profonde nella teoria della fisica (come la nostra convinzione che il momento preciso in cui un fotone colpirà un rivelatore è veramente casuale). Ci sono alcuni algoritmi software per questo, come Blum-Blum-Shub . In generale, non scrivere un PRNG se hai bisogno di imprevedibilità, ma piuttosto usa uno stabilito . Questo va soprattutto con crypto.

L'altra importante proprietà delle funzioni casuali è in realtà abbastanza semplice da soddisfare. Ci sono molti esempi di questo, come il RNG dietro RC4 , Registri spostamento lineare feedback (questo è stato effettivamente usato anche per crypto una volta, ma è stato trovato insufficientemente sicuro), ecc. Anche la libreria C standard rand() funzionerà probabilmente va bene per questo scopo.

La cosa più importante: assicurati di sapere quale delle due proprietà è fondamentale per le tue necessità. Anche i PRNG Unpredictable sono distribuiti uniformemente, ma viceversa non è vero. Inoltre, se stai esponendo la casualità all'interno di un "motore" di qualche tipo (come un motore di gioco), assicurati che le persone non possano giocare al sistema, perché potresti essere sorpreso di quanto sia facile. Ad esempio, i CSS (l'algoritmo di crittografia dei DVD) hanno utilizzato 2 LSFR per scopi di crittografia e sono stati suddivisi in modo abbastanza semplice.

Innanzitutto, non è possibile generare numeri veramente casuali nel software. Ci sono un sacco di algoritmi diversi che ti permettono di generare numeri pseudo-casuali. A seconda del motivo per cui hai bisogno di numeri pseudo-casuali (cioè se li stai utilizzando in crittografia i requisiti sono molto diversi), generalmente useresti qualcosa come il generatore di numeri casuali nel biblioteca scientifica GNU (che, ovviamente, puoi implementare in qualunque lingua tu preferisca).

Hardware. È necessario connettersi all'hardware in grado di raccogliere entropia da ... ovunque. Leggi la statica da una radio, metti una webcam su un campo di lavalamp o fai in modo che l'utente non chiami o giochi con il mouse. Senza alcun contatto con il mondo reale, generare casualità è impossibile. È un'area di studio importante, e molto lavoro è stato dedicato. Dubito che stiate bruciando nuove piste, quindi dovresti davvero stare sulle spalle dei giganti e iniziare a leggere le voci di Wikipedia.

"La generazione di numeri casuali è troppo importante per essere lasciata al caso."
-Robert R. Coveyou

Modifica
Quindi ho imparato che l'hardware che desideri è in realtà solo un chip CMOS . Il tipo con fotocamere economiche. Basta tenerlo nell'oscurità, impostare la sensibilità verso l'alto e apparentemente le minuscole variazioni osservate hanno radici nella meccanica quantistica, che è il punto in cui deriviamo la nostra entropia nella vita reale.

L'ultima volta che ho guardato, che era un po 'di tempo fa, il riferimento canonico sull'implementazione dei generatori di numeri pseudocasuali (PRNG) è Knuth, vol. 2, "Algoritmi seminali" .

Non pensare nemmeno di provare a implementare il tuo PRNG almeno finché non hai almeno controllato Knuth.