Come funzionano i generatori di numeri casuali: PRNG, CSPRNG e vera casualità

I numeri casuali alimentano omaggi, giochi, simulazioni, password e crittografia. La parte sorprendente è che la maggior parte dei numeri casuali non sono affatto casuali. Sono prodotti da un processo deterministico che sembra imprevedibile dall’esterno.

Punti chiave

• Un generatore di numeri pseudo-casuali (PRNG) trasforma un seme in una sequenza lunga e ripetibile.
• Un PRNG crittograficamente sicuro (CSPRNG) è progettato in modo tale che gli output passati non possano praticamente rivelare quelli futuri.
• La vera casualità deriva da fonti fisiche di entropia, non solo da un algoritmo.
• I browser espongono un CSPRNG tramite crypto.getRandomValues(), che è la scelta giusta per le estrazioni quotidiane.
• L'equità dipende anche da come i valori vengono mappati in un intervallo: l'aritmetica del modulo distorta può tranquillamente favorire alcuni risultati.

Perché la casualità è più difficile di quanto sembri

Un computer segue le istruzioni. Se esegui due volte lo stesso programma con gli stessi input, normalmente ottieni lo stesso output. Un generatore di numeri casuali deve infrangere tale aspettativa senza danneggiare la macchina.

Il software di solito risolve il problema in due livelli. Innanzitutto, raccoglie una piccola quantità di dati imprevedibili, chiamati entropia, da fonti quali jitter temporale, eventi della tastiera o rumore dell'hardware. In secondo luogo, utilizza quell’entropia come seme per un algoritmo che produce un lungo flusso di numeri. Il flusso sembra casuale, ma è completamente determinato dal seme e dall'algoritmo.

Quel disegno è utile. Rende riproducibili i numeri casuali per simulazioni e test. Significa anche che un generatore con una semina scarsa può ripetere la stessa sequenza su macchine diverse, motivo per cui la qualità del seme è importante.

Cosa fa un generatore di numeri pseudo-casuali

Un PRNG mantiene uno stato interno. Ogni volta che chiedi un numero, trasforma lo stato e restituisce parte del risultato. La trasformazione è solitamente veloce e deterministica. Dato lo stesso stato iniziale, ricompare la stessa sequenza.

La maggior parte dei PRNG alla fine ripetono il proprio stato. Il numero di valori prima della ripetizione è chiamato periodo. Un periodo lungo è utile, ma non rende automaticamente sicuro un generatore. Un utente malintenzionato in grado di osservare un output sufficiente potrebbe essere in grado di ricostruire lo stato interno e prevedere i valori futuri.

PRNG contro CSPRNG

Un PRNG generico è ottimizzato per velocità e qualità statistica. Un CSPRNG è progettato per resistere alla previsione. Utilizza primitive crittografiche ed è costruito in modo che l'apprendimento di un output non debba rivelare quello successivo.

Math.random() di JavaScript non è adatto per lavori sensibili alla sicurezza. È veloce e conveniente, ma i motori non garantiscono la qualità crittografica. I browser forniscono crypto.getRandomValues() per la casualità rilevante per la sicurezza. Riempie un array tipizzato con byte casuali utilizzando l'origine crittografica della piattaforma.

Per password, token, equa estrazione con premio e qualsiasi cosa un utente malintenzionato possa voler prevedere, utilizza un CSPRNG. Per un'animazione decorativa o una simulazione approssimativa, un normale PRNG potrebbe essere sufficiente.

Da dove nasce la vera casualità

Nessun algoritmo software può creare informazioni dal nulla. La vera casualità entra nel sistema attraverso processi fisici: decadimento radioattivo, rumore termico o la tempistica precisa dell'input dell'utente. I sistemi operativi raccolgono questi segnali in un pool di entropia e li usano per seminare generatori crittografici.

I moderni sistemi operativi e browser mescolano continuamente entropia. Non è necessario muovere il mouse per effettuare un pareggio corretto, ma il sistema ha bisogno di una sana fonte di entropia durante l'avvio e dopo lunghi periodi senza attività. Questo è uno dei motivi per cui i generatori crittografici sono progettati attentamente piuttosto che improvvisati.

Come funzionano i generatori su questo sito

Gli strumenti su questo sito utilizzano crypto.getRandomValues() nel tuo browser. I risultati vengono generati localmente e non vengono caricati.

Per gli intervalli interi, il browser restituisce un valore senza segno a 32 bit. Un approccio ingenuo utilizza il resto dopo la divisione, ma ciò può introdurre una piccola distorsione quando l'intervallo non si divide uniformemente nell'intero spazio a 32 bit. I generatori utilizzano invece il campionamento di rifiuto: i valori al di fuori della regione imparziale vengono scartati e ridisegnati. Il risultato è una distribuzione uniforme nell'intervallo richiesto.

I mescolamenti utilizzano l'algoritmo di Fisher-Yates con indici casuali sicuri. A differenza dell'ordinamento casuale con comparatore casuale, Fisher-Yates produce ogni permutazione con uguale probabilità quando gli indici casuali sono uniformi.

Cosa è sufficientemente casuale per il tuo caso d'uso?

Utilizza la normale pseudo-casualità per animazioni, grafica di gioco o simulazioni approssimative in cui la prevedibilità non ha alcun costo. Utilizza un CSPRNG per:

• Password e codici di ripristino.
• Omaggi, lotterie e audizioni con un vero premio.
• Assegnazione casuale delle persone a squadre o gruppi.
• Token, identificatori di sessione e qualsiasi cosa relativa alla sicurezza.
• Qualsiasi pareggio potresti dover difendere pubblicamente.

Per le chiavi crittografiche a lungo termine, utilizzare un sistema di gestione delle chiavi dedicato anziché un sito Web. La casualità del browser è forte, ma il ciclo di vita delle chiavi, l'archiviazione e il controllo degli accessi contano tanto quanto i bit iniziali.

Un semplice controllo di equità

Puoi testare un generatore in modo informale eseguendo molte estrazioni e osservando la distribuzione. Con un dado a sei facce, ogni faccia dovrebbe apparire circa un sesto delle volte. Le tirature brevi possono variare e le strisce sono normali. Ciò che conta è se il processo è imparziale su molti studi e se è sufficientemente riproducibile da poter essere sottoposto a audit.

Per le estrazioni pubbliche, registra gli input, le impostazioni e il risultato. Il record fa di più per la fiducia di qualsiasi affermazione di casualità.

Conclusione

La casualità è una catena di decisioni ingegneristiche: raccolta di entropia, scelta dell’algoritmo, mappatura imparziale e utilizzo trasparente. Un buon generatore non deve essere misterioso. Deve essere imprevedibile dove conta, documentato dove viene utilizzato e onesto riguardo ai suoi limiti.