Generatore di numeri casuali

Informazioni su questo generatore

I computer sono macchine deterministiche, il che rende il "casuale" una cosa strana da produrre. La storia dei generatori di numeri pseudocasuali (PRNG) sui computer comincia con il middle-square method di John von Neumann nel 1946: eleva al quadrato il numero precedente, prendi le cifre centrali come nuovo valore, ripeti. Lo stesso von Neumann la chiamò "uno stato di peccato usare generatori di numeri casuali di qualsiasi tipo" se non li si comprendeva del tutto, perché middle-square ha modi di fallimento ovvi (cicli a zero, periodi corti). Il linear congruential generator (LCG, 1951) di Lehmer, x_(n+1) = (a × x_n + c) mod m, fu la prima famiglia di PRNG con proprietà statistiche ragionevoli; rand() della libreria standard del C usa ancora tipicamente una variante LCG. Il Mersenne Twister (Matsumoto e Nishimura, 1997-1998) ci ha dato un generatore con un periodo di 2¹⁹⁹³⁷−1 (sì, un numero di 6.000 cifre) e proprietà statistiche eccellenti; è diventato il default in Python, R, MATLAB, PHP e in molti altri linguaggi. La famiglia xorshift di Marsaglia (2003) è molto più veloce e abbastanza piccola da entrare in un registro hardware; la moderna V8 (il motore JavaScript di Chrome) usa una variante xorshift128+ per Math.random(). PCG (Permuted Congruential Generator) di Melissa O'Neill (2014) è l'attuale stato dell'arte statistico per i PRNG non crittografici, combinando avanzamento di stato in stile LCG con permutazione dell'output per ottenere ottime proprietà statistiche a basso costo.

I PRNG crittograficamente sicuri (CSPRNG) sono una bestia diversa. La proprietà definitoria: anche se un attaccante conosce ogni output che il generatore ha prodotto, non può prevedere il prossimo output con un vantaggio migliore di trascurabile. La syscall getrandom() di Linux (aggiunta nel kernel 3.17, ottobre 2014) e il sottostante /dev/urandom usano un generatore basato su ChaCha20 seminato da fonti hardware di entropia (RDRAND, timing degli interrupt, rumore audio). Windows BCryptGenRandom usa una costruzione AES-CTR-DRBG (NIST SP 800-90A) seminata da molteplici fonti di entropia. macOS / iOS usano un CSPRNG derivato da Fortuna. La differenza tra PRNG e CSPRNG conta enormemente: un PRNG va bene per la casualità nei giochi, l'assegnazione dei bucket per A/B test o le simulazioni; per qualsiasi cosa che un attaccante potrebbe provare a prevedere (token di sessione, generazione di password, ID di sicurezza), solo un CSPRNG è sicuro.

Le due API casuali di JavaScript

Math.random() è l'API più vecchia e semplice: restituisce un numero in virgola mobile distribuito approssimativamente uniformemente in [0, 1). La specifica ECMAScript lascia deliberatamente non specificato l'algoritmo sottostante ("distribuzione approssimativamente uniforme tra 0 e 1, esclusivo"), e i motori hanno cambiato ciò che usano nel corso degli anni. V8 (Chrome) ha usato un LCG Park-Miller fino al 2015, poi è passato a xorshift128+ per migliori proprietà statistiche. SpiderMonkey (Firefox) e JavaScriptCore (Safari) usano generatori non crittografici veloci simili. Math.random() è veloce e abbastanza uniforme per meccaniche di gioco, simulazioni e qualsiasi applicazione in cui l'imprevedibilità non sia un requisito di sicurezza. Non è crittograficamente sicuro: il periodo dipende dall'implementazione, lo stato può essere recuperato da un piccolo numero di output e la sequenza non è sicura per la generazione di password o casi d'uso sensibili alla sicurezza. crypto.getRandomValues() è il CSPRNG della Web Crypto API. Riempie un typed array con byte casuali crittograficamente sicuri prelevati dal CSPRNG del sistema operativo (la stessa fonte che TLS usa per le chiavi di sessione). Disponibile in tutti i browser moderni dal 2014 circa; la dimensione massima del buffer in una singola chiamata è 65.536 byte. La scelta giusta per qualsiasi numero casuale che conta: generazione di token, ID di sicurezza, generazione di password, qualsiasi cosa che un attaccante potrebbe provare a prevedere.

La trappola del bias modulo

Generare un intero uniforme in un intervallo specifico da un CSPRNG è più difficile di quanto sembri. L'approccio ingenuo, crypto.getRandomValues(new Uint8Array(1))[0] % 6 per un tiro di dado, produce una distribuzione distorta perché 256 non si divide esattamente per 6. I valori 0-3 ricorrono ciascuno 43 volte nell'intervallo 0-255; i valori 4-5 ricorrono 42 volte. Il bias è piccolo per intervalli piccoli ma reale, e rilevabile su lunghe esecuzioni. La correzione standard è il rejection sampling: genera un byte casuale, verifica se cade nel più grande multiplo del tuo intervallo che ci entra (qui, 252 = 42 × 6), usalo se è così, scartalo e riprova altrimenti. Il tasso di scarto è limitato da (intervallo / prossima potenza di 2), quindi per "1-6" sprechi circa l'1,5% dei byte; per "1-1000000" contro un int casuale a 32 bit sprechi circa lo 0,02%. Ogni libreria casuale seria implementa il rejection sampling; l'approccio basato su Math.random() con Math.floor(Math.random() * (max - min + 1)) + min evita il bias perché la precisione di Math.random() è abbastanza alta (53 bit di mantissa) che il bias è sotto livelli rilevabili dall'umano per qualsiasi intervallo ragionevole. Questo generatore usa output CSPRNG con rejection sampling: output uniforme su qualsiasi intervallo intero richiesto.

Casi d'uso, e di che livello di casualità ciascuno ha bisogno

• Estrazioni di lotteria e tombole. Per estrazioni non monetarie (scambi in ufficio, assegnazione di team a un hackathon, posti in aula), Math.random() va bene. Per estrazioni monetarie o regolamentate, usa un CSPRNG e idealmente pubblica il seme per la verificabilità.
• Meccaniche di gioco. Tiri di dado, mescolamenti di carte, drop di loot, generazione procedurale. Math.random() è la scelta standard: veloce, abbastanza uniforme, abbastanza imprevedibile che i giocatori non noteranno schemi. I CSPRNG sono riservati ai giochi di carte online dove il lato server deve impedire i bari.
• Assegnazione bucket per A/B test. Esegui l'hash dell'ID utente con un segreto stabile per piazzare deterministicamente ogni utente in un bucket: usare Math.random() significherebbe che un utente atterrerebbe in bucket diversi attraverso i caricamenti di pagina, il che vanificherebbe l'esperimento. L'assegnazione basata su hash è il pattern giusto; la casualità è usata solo per scegliere il seme dell'esperimento, una volta sola.
• Campionamento casuale per sondaggi. Estrarre un sottoinsieme rappresentativo da una popolazione. Math.random() va bene; la domanda statistica è se il tuo campione sia abbastanza grande, non se la fonte casuale sia crittografica.
• Generazione di dati di test. Faker, dati mockup, fixture sintetiche per database. Math.random() con un seme fisso (per riproducibilità) è la scelta giusta.
• Chiavi crittografiche, token di sessione, generazione di password. Solo CSPRNG: crypto.getRandomValues() nel browser, modulo secrets in Python, crypto/rand in Go, mai il random predefinito del linguaggio. Un bug in questo strato compromette tutto ciò che dipende da esso; le conseguenze vanno da "la sessione di tutti è dirottabile" a "la chiave di cifratura è recuperabile."

RANDOM.ORG e la distinzione della casualità vera

RANDOM.ORG fu lanciato nel 1998 da Mads Haahr al Trinity College Dublin e rimane il riferimento per la "casualità vera" online. Mentre ogni CSPRNG deriva ultimamente i suoi bit da trasformazioni algoritmiche di uno stato seminato hardware (un processo deterministico, anche se imprevedibile per un attaccante), RANDOM.ORG misura il rumore atmosferico da ricevitori radio e converte il rumore analogico direttamente in bit. Questo lo rende un True Random Number Generator (TRNG) piuttosto che un Pseudo-Random Number Generator: i bit provengono da un processo fisico genuinamente non deterministico, non da un algoritmo deterministico. RANDOM.ORG è usato da operatori di lotteria, ricercatori accademici che eseguono studi in doppio cieco e giochi in cui la casualità verificabile conta. Il compromesso: un round-trip di rete per richiesta, una quota giornaliera per il livello gratuito e la domanda filosofica se ti fidi della fonte di entropia dichiarata da RANDOM.ORG più del tuo CSPRNG locale. Per la maggior parte dei casi d'uso il CSPRNG locale è sufficiente; per casi in cui una terza parte deve verificare la casualità in modo indipendente, RANDOM.ORG fornisce certificati firmati di casualità come servizio a pagamento.

Campionamento senza ripetizione: il Fisher-Yates shuffle

Quando hai bisogno di N numeri unici da un intervallo (estrarre 6 numeri da 1-49 per una lotteria, scegliere 10 vincitori da 1000 partecipanti), l'approccio ingenuo "genera e rifiuta se duplicato" funziona per N piccoli ma degrada bruscamente quando N si avvicina alla dimensione dell'intervallo (la probabilità di estrarre un numero fresco diminuisce mentre il pool si restringe). L'algoritmo standard è il Fisher-Yates shuffle, che ha origine nelle tavole statistiche di Fisher e Yates del 1938 e ha avuto la sua forma moderna informatica da Donald Knuth nel 1969 (a volte chiamato Knuth shuffle). L'algoritmo è semplicissimo: scrivi i numeri da 1 a N in un array; per i da N-1 fino a 1, scambia l'elemento i con un elemento casuale tra 0 e i (incluso); l'array è ora mescolato uniformemente. Prendi i primi K elementi per K numeri casuali unici. Il dettaglio cruciale: l'indice casuale deve essere in [0, i], incluso: usare [0, i-1] introduce un bias sottile che ha richiesto anni alla comunità crittografica per essere caratterizzato (la variante Sattolo, a volte erroneamente usata al posto del vero Fisher-Yates). Per intervalli molto grandi dove allocare un array di tutti gli N valori è impraticabile (es. scegliere 100 valori unici da 1-10⁹), il reservoir sampling (Vitter, 1985) gestisce input in streaming o illimitati in un singolo passaggio con memoria limitata.

Convenzioni sui tiri di dado

I generatori di numeri casuali sono dadi sotto mentite spoglie. D6 (dado a sei facce) è il default universale dei giochi da tavolo, intervallo 1-6. D20 (dado a venti facce) è il dado iconico di Dungeons & Dragons usato per le prove di abilità, i tiri d'attacco e i tiri salvezza: il sistema di modificatori di D&D significa che un singolo tiro di D20 più un bonus di caratteristica determina l'esito della maggior parte delle azioni. D100 (percentile, 1-100) è usato per i tiri percentili in Call of Cthulhu, Warhammer Roleplay e molti sistemi di chance critica. La notazione NdM significa "tira N dadi con M facce ciascuno e somma"; NdM+B aggiunge un bonus. 3d6 tira tre dadi a sei facce e somma (intervallo 3-18, l'intervallo classico delle caratteristiche di D&D, con una distribuzione triangolare centrata su 10-11). Per una simulazione equa, generare un intero uniforme in [1, M] per ogni dado e sommare è esattamente equivalente a tirare dadi fisici: la distribuzione del CSPRNG sottostante è più uniforme di qualsiasi dado fisico tu possa comprare. I casinò e il gioco regolamentato usano RNG certificati che vengono testati contro batterie statistiche (BigCrush di TestU01, NIST SP 800-22) per provare l'uniformità ai regolatori del gioco; gli stessi standard si applicano agli RNG delle lotterie.

Seeding e riproducibilità

Una proprietà sottile ma importante dei PRNG: sono deterministici dato un seme. Imposta il seme su un valore noto e la sequenza di numeri "casuali" è esattamente riproducibile. Questo è inestimabile per i test (uno unit test che usa dati casuali dovrebbe impostare un seme fisso così i fallimenti sono riproducibili) e per le tombole verificabili (pubblica il seme prima del sorteggio, poi chiunque può verificare il risultato). Il modulo random di Python ha random.seed(value) per questo; Random di Java prende un seme nel costruttore. Math.random() di JavaScript deliberatamente non espone un'API di seeding (i motori trattano il seme come stato interno) ma diverse librerie pure-JS (seedrandom, pcg-random) forniscono PRNG seminati. I CSPRNG sono diversi per design: non espongono il seeding perché il punto è proprio l'imprevedibilità. Se hai bisogno di riproducibilità, usa un PRNG con seeding esplicito; se hai bisogno di sicurezza, usa un CSPRNG e accetta che non puoi riprodurre la sequenza in seguito.

Privacy: perché solo browser anche per i numeri casuali

I numeri casuali in sé contengono raramente informazioni sensibili, quindi perché conta l'architettura solo-browser? Due ragioni. Primo, quando un numero casuale viene usato come token di sessione, chiave di idempotenza, sfida di autenticazione o qualunque altro valore tipo-segreto, generarlo su un server di terze parti significa che quel server ha visto il valore prima che lo usassi tu: un'esposizione piccola ma reale. Secondo, i generatori lato server che promettono "casualità crittografica" non possono essere verificati dall'utente; un server buggy o malizioso potrebbe restituire valori non casuali o distorti che sembrano casuali, e non avresti modo di rilevare il bias senza un campionamento massiccio. Un generatore solo-browser esegue la stessa chiamata crypto.getRandomValues() che la tua applicazione eseguirebbe lato server; l'entropia proviene dalla stessa fonte del sistema operativo (Linux getrandom(), Windows BCryptGenRandom, macOS); nessuna terza parte vede l'output. Puoi verificarlo aprendo il pannello Network di DevTools mentre clicchi Genera: non ci sono richieste in uscita. Metti la pagina offline (modalità aereo) dopo che si è caricata e il generatore continuerà a funzionare.

Domande frequenti