backup del Post

Numeri pseudocasuali e il ritorno dei TRNG

Abbiamo visto la volta scorsa che gli scienziati hanno bisogno di tanti numeri casuali, ma gli informatici hanno bisogno che i programmi abbiano sempre gli stessi dati di input per poterli testare. La soluzione che si è scelta è stata quella dei generatori di numeri pseudocasuali, i PRNG. Un PNRG è in pratica una funzione matematica deterministica che viene man mano iterata, nel senso che usa il risultato precedente per calcolare quello nuovo. Quindi se si parte con dallo stesso valore iniziale (il “seme”, in inglese “seed”) si otterrà sempre la stessa soluzione. Il problema a questo punto si sposta: bisogna dimostrare che le successioni ottenute siano effettivamente abbastanza casuali per gli scopi previsti, e che questo capiti con qualunque seme.

La prima persona a sviluppare un PNRG fu John von Neumann, nel 1946. La sua idea fu di partire da un seme iniziale, elevarlo al quadrato e prendere le cifre di mezzo del risultato. Peccato che all’atto pratico si arrivi sempre a un ciclo molto breve, come 8100, 6100, 4100, 8100, 6100, 4100, … che di casuale ha davvero ben poco. Intendiamoci: una qualunque funzione deterministica produrrà un ciclo, di qui non si scappa. Ma se il ciclo è moooolto grande, lungo miliardi di miliardi, è poi così importante? Evidentemente no. Tutto stava insomma nel cercare una formula relativamente semplice da implementare, o meglio che sputasse il nuovo valore pseudocasuale molto in fretta, e che avesse un ciclo molto lungo di ripetizioni. Ah: dimenticavo che naturalmente la formula deve anche dare numeri sufficientemente casuali. Pensate a che cosa succederebbe se la cifra 9 comparisse la metà delle volte rispetto all’8!

La prima formula di questo tipo usata in pratica fu definita nel 1949 dal matematico D. H. Lehmer – magari ne avete sentito parlare a proposito dei primi di Mersenne, visto che ha modificato il criterio di Lucas per renderlo ancora più veloce – con i generatori a congruenze lineari (linear congruential generators, o LCG in breve). L’idea alla base di un LCG è scegliere opportunamente tre numeri positivi a, b, m: una volta poi preso un valore di partenza r, quello successivo sarà s = ar+b mod m. È immediato vedere che il ciclo di questo generatore è al più lungo m; in realtà a seconda dei valori di a e b esso potrebbe essere un suo divisore. Quello che succede in pratica è che si sceglie spesso m come 2³² oppure 2⁶⁴, perché sono numeri comodi per velocizzare le operazioni; poiché però non sono i migliori per la generazione di numeri davvero casuali e soprattutto di successioni di numeri casuali, vengono mostrati solo i bit più significativi del risultato.

Se vi sembra che tutti questi caveat siano solo fisime dei matematici, sbagliate di grosso. Tanto per dire, a metà anni ’90 venne scoperto un problema con i certificati SSL di Netscape, quelli che servono per le connessioni protette con il protocollo https. In pratica, Netscape – che all’epoca era tra i piú importanti attori – usava come seme per il suo LCG una combinazione del tempo di sistema e del numero di processo, il che significava che un cracker poteva facilmente ricavare quei dati e decrittare tutti i dati della sessione che a questo punto era tutto meno che sicura. Si doveva insomma tornare a qualche altro sistema davvero casuale, almeno per quando i programmi erano ormai stati testati e dovevano essere eseguiti in pratica. Alla fine degli anni ’90 ci sono stati due esempi pratici: dalla SGI LavaRand, che generava numeri casuali filmando una coppia di lava lamp (ve l’avevo detto che l’idea era molto anni ’90) e generando 165Kb/s di dati casuali; da uno dei fondatori di Autodesk invece nacque HotBits, che sfruttava un contatore geiger per ottenere numeri quantisticamente casuali. Nel 1998 è stato anche creato il sito irlandese random.org, che oggi fornisce Numeri Davvero Casuali con servizi gratuiti e a pagamento. Nel 1999 infine l’Intel ha cominciato a introdurre nei chipset i810 un generatore di numeri casuali basato sul rumore termico, anche se un po’ più lento di quelli software; se quindi vogliamo comunque usare un PNRG esiste un bellissimo software del 1997, sviluppate da Makoto Matsumoto (松本 眞) e Takuji Nishimura (西村 拓士). Il Mersenne Twister si chiama così perché usa come base un primo di Mersenne. Quello usato attualmente ha un ciclo di lunghezza 2¹⁹⁹³⁷−1, che dovrebbe essere sufficiente per un qualunque uso pratico.

E nel nuovo millennio? Si è partiti a studiare i PNRG crittograficamente sicuri (CSPRNG) e i TRNG open source per sincerarci che i valori forniti non abbiano qualche backdoor inserita dalla NSA. Ma su questo vi rimando all’articolo di FreeCodeCamp da cui ho preso molte delle informazioni di questi post. Buona lettura :)