Leggendo un articolo su slashdot ultimamente mi sono imbattutto in questa notizia:
The German team has now developed a true random number generator that uses an extra layer of randomness by making a computer memory element, a flip-flop, twitch randomly between its two states 1 or 0. Immediately prior to the switch, the flip-flop is in a ‘metastable state’ where its behavior cannot be predicted. At the end of the metastable state, the contents of the memory are purely random. The researchers’ experiments with an array of flip-flop units show that for small arrays the extra layer makes the random number almost twenty times more ‘random’ than conventional methods.
“Il team tedesco ha sviluppato un generatore di “veri numeri casuali” che utilizza uno strato aggiuntivo di casualità ottenuto grazie ad un flip-flop che viene fatto saltare in maniera casuale tra i suoi due stati 1 o 0. Nell’istante che precede il cambio di stato, il flip-flop è un uno “stato metastabile” in cui il suo comportamento non può essere predetto. Alla fine dello stato metastabile, il contenuto della memoria sarà puramente casuale. L’esperimento dei ricercatori fatto con una serie di flip-flop mostra che per piccole serie lo strato aggiuntivo permette di ottenere numeri quasi venti volte più random dei metodi convenzionali.”
Per capire meglio la portata dell’esperimento dobbiamo prima capire cosa è un generatore di numeri pseudo random. Un generatore di numeri pseudo random è un algoritmo deterministico che dato in ingresso una sequenza di bit di lunghezza 
restituisce una sequenza di bit 
che in qualche modo “sembra” casuale. Il sembra che ho scritto è dovuto al fatto che nel processo di trasformazione dell’input (chiamato seme) i passi sono passi deterministici quindi ripercorribili a ritroso.
Il numero delle possibili sequenze di output l infatti è al più una frazione di tutte le possibili sequenze binarie di lunghezza 
, solitamente nell’ordine di 
.
L’unico modo per avere un numero veramente random attualmente è generare tutte le cifre in maniera casuale. Il processo in se non sarebbe niente di difficile considerando che si potrebbe utilizzare un dado o addirittura il lancio di una monetina per farlo, ma questi metodi si scontrano con la necessità di crearne grandi quantità nella maniera più rapida possibile.
I sistemi hardware che riescono a fare qualcosa del genere attualmente si basano su diversi eventi fisici random come per esempio:
- Il tempo intercorso tra l’emissione di particelle in un processo di decadimento radioattivo
- Le fluttuazioni di segnale dovute a rumore termico su dispositivi elettrici o elettronici
- Suoni catturati da un microfono o video presi da una camera
Tutto ciò può essere fatto naturalmente anche utilizzando in qualche modo dati provenienti da un ambiente software sfruttando diversi fattori come:
- Il clock di sistema
- Tempo che intercorre tra la pressione di un tasto ed un altro della tastiera.
- Movimenti del mouse.
- Contenuto di buffer o registri vari del sistema.
La prima classe di generatori sono estremamente performanti ma possono arrivare a costare anche migliaia di euro.
I sistemi del secondo tipo sono assolutamente economici ma per loro stessa natura sono meno robusti. Per esempio conoscendo l’ambiente e il momento in cui la sequenza è stata generata si potrebbe per esempio restringere di molto il campo del clock di sistema. In generale ci sono dei test probabilistici che valutano la bontà di un numero random (la casualità di un numero non è dimostrabile matematicamente).
Nella pratica l’esperimento è volto a dimostrare che con il semplice utilizzo di proprietà fisiche ben conosciute presenti in hardware economico di consumo si può creare un generatore di numeri pseudo random estremamente più performante di quelli convenzionali.
Per premiare chi è arrivato fino alla fine dell’articolo presento un assaggio di due generatori di numeri random di prossima generazione
hardware…
…e software:
[Immagine originale in Home di MissTurner]
Molto interessante…
Ma in linux non esiste il device virtuale /dev/random che genera numeri basandosi proprio sul rumore elettrico?
@Giulio85
/dev/random funziona in maniera simile come una “piscina di entropia” che catturata da diverse fonti come driver e altro. Appartiene comunque alla famiglia dei generatori software. Il suo principale problema è che non è molto rapida a “ricaricarsi”. Comunque per un utente che deve generarsi una chiave random produce risultati ottimi.
/dev/random sfrutta gli interrupt, ma prova a riempirci un hd… dubito che la tua vita sia sufficientemente lunga per farlo :)
@Giulio85
/dev/random sfrutta gli interrupt, ma prova a riempirci un hd… dubito che la tua vita sia sufficientemente lunga per farlo :)
Il random è uno dei problemi peggiori da parte di un programmatore.. La funzione rand() del c non è affatto random (si basa sul tempo di esecuzione del programma, quindi..a meno di rallentamenti eccessivi o input che variano le tempistiche, il risultato ottenuto in 20 esecuzioni diverse sarà molto probabilmente lo stesso. E con srand il problema non sempre si risolve, dato che il seed viene scelto arbitrariamente (e anche se si usasse rand per il seed..ad ogni esecuzione sarebbe uguale! ^^) dal programmatore, non dando i risultati sperati..
Sul forum di hwupgrade c’è la discussione di un utente che spiega un suo modo per ottenere un random “più random del random”, il che fa ragionare sull’efficacia della funzione rand.
Vorrà dire che per il prossimo programma che dovrò “randomizzare” userò la funzione getRandomNumber() indicata qui sopra! ;)
@TheFoggy
Se ti serve un bool puoi anche usare la monetina! :P
Salve…
scusate l’ignoranza informatica.. ma non avete spiegato la cosa più importante. A cosa serve un numero random… ?? Per cosa viene utilizzato ??
ciao
@davide
Urca… hai proprio ragione. Certe volte commetto ancora l’errore di dare per scontate cose che non lo sono affatto. Grazie di averlo fatto notare. I numeri random servono in moltissimi campi applicativi. I più importanti che mi vengono in mente sono le simulazioni computerizzate di eventi casuali e tutto il ramo della crittografia (pensa per semplicità alla generazione di una password robusta o di una chiave di cifratura).
@ TheFoggy
Credo che glibc implementi rand con un generatore congruenziale lineare, il tempo di esecuzione del programma non c’entra.
@ Emanuele
L’articolo originale potrebbe essere questo (vecchiotto, del 2008):
http://portal.acm.org/citation.cfm?id=1441301
La cosa interessante e’ che usa solo logica CMOS standard, quindi e’ semplice da costruire; inoltre, sembrano avere un modo semplice di detettare un attacco elettromagnetico.
Per contro, alcuni problemi potrebbero essere:
* non so come costruiscono il circuito, ma io della metastabilita’ ho paura :) facile bruciare i flip-flop… non so come si cautelino
* e’ difficile dire quando il flip-flop uscira’ dalla metastabilita’, potrebbe volerci parecchio: il generatore potrebbe essere lento
* usa 2^(2k) flip-flop per generare un singolo bit casuale: il circuito potrebbe essere grosso
* i flip-flop non hanno la stessa probabilita’ di uscire dalla metastabilita’ verso lo stato 0 e verso lo stato 1 (sono sbilanciati); questo impone l’uso di tecniche per migliorare la casualita’ ottenuta dall’hardware (loro scartano alcuni bit), e questo rallenta ancora di piu’ il sistema (ma e’ un problema comune)
* stuck-at faults riducono le prestazioni del sistema
Sarebbe interessante confrontarlo col generatore Intel (che e’ abbastanza complicato: si basa su due clock in free running, di cui uno molto piu’ lento dell’altro modulato dal rumore Johnson di due resistori, filtrato col correttore di von Neumann e infine dato in pasto a SHA-1).
@pleg
Al fatto che la metastabilità non fosse modellata da una gaussiana perfettamente simmetrica non avevo pensato e in effetti aggiunge qualche problema. Mi chiedo anche se da che parte sia sbilanciata sia determinabile in maniera esatta o dipenda dal processo di lavorazione dei componenti.
L’articolo che hai linkato adesso purtroppo non posso leggerlo (l’abbonamento springerlink è valido solo sulla rete universitaria) ma domani appena arrivo in facoltà ci darò un occhiata di sicuro.
Il generatore intel non lo conosco. Con una ricerca veloce ho trovato questo:
http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
ma è solo una comparativa tra un generatore congruenziale lineare standard ed uno ottenuto utilizzando le SSE2.
Immagino che lo stato di uscita del flip-flop dalla metastabilita’ dipenda da tanti fattori: il layout del circuito, variazioni di processo, polarizzazione del circuito e interferenze elettromagnetiche durante il funzionamento, eccetera.
D’altro canto, nessun generatore hardware e’ “true random”, c’e’ sempre del filtraggio dopo per aumentare la casualita’.
Per la Intel, mi riferivo al loro generatore hardware (credo sia presente da qualche parte in alcuni dei loro chipset, non conosco i dettagli):
http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf
Io avrei una mezza idea: un simulatore di rottura.
Supponiamo una lastra di vetro intesa come prodotto chimico (non so di preciso se miscuglio o soluzione). Ogni vetro anche quando viene fatto con lo stampo è praticamente diverso da un altro perchè al suo interno corrono sempre delle “venature” che si comportano da punto debole.
Dati due vetri uguali colpiti nello stesso punto dalla stessa forza i frammenti ottenuti non sarebbero mai uguali.
Aggiungendo a tutto il processo la simulazione tutta una serie di fenomeni fisici quali attrito, temperature (chiaramente non uniformi sulla superficie di vetro) che finirebbero per influenzare la forma dei frammenti, si potrebbe scegliere un numero di questi e determinare un valore preciso del loro volume, peso ecc.ecc.
La possibilità di scegliere materiali e forme di pavimento e proiettile si aumenterebbe a dismisura il numero di casualità.
Unico neo di questa cosa sarebbero i tempi di calcolo disumani.
@ D
Appunto, non e’ molto pratico :)
Comunque, si’, l’idea generale di un TRNG e’ di usare fenomeni fisici altamente caotici, che producono eventi difficilmente prevedibili. Ad esempio, fenomeni atmosferici (anche questi non molto pratici :) , oppure quantici: ad es. uno specchio semiriflettente e un emettitore che emette un fotone alla volta: il fotone ha il 50% di probabilita’ di attraversare la lastra e il 50% di non farlo, e l’esito per il singolo fotone e’ impredicibile.
Un meccanismo molto usato e’ il rumore elettronico di una resistenza o di un diodo, anch’esso molto poco prevedibile.
@D
Beh ma a quel punto basta utilizzare veramente il lancio di una monetina… Se non altro è più economica visto che la puoi riutilizzare per il lancio successivo :D . Con 256 lanci ti crei un bel “true random”. Il problema qui non è generare un numero random, ma generarne grosse quantità in tempi molto bassi. Pensa per esempio ad un server che deve generare grosse quantità di chiavi per la connessione cifrata con ssl.
Interessante. Da non professionista del settore, davo per scontata la generazione dei numeri random dai tempi del basic del C=64.
Ma usare srand() con la data unix come seme? Ad ogni esecuzione si ha seme diverso, no?
@ Davide
Dipende da che tipo di numeri casuali hai bisogno. Per applicazioni crittografiche, e’ la ricetta per il sicuro disastro. Per applicazioni scientifiche, non e’ in genere una buona idea (ma dipende da caso a caso, devi valutare). Per mischiare le carte in un gioco di poker online, potrebbe essere sufficiente :)
@Davide
Il problema come già detto è che srand() utilizza un algoritmo per espandere in maniera deterministica il seme. Ma in alcuni ambiti prendere come seme la data di sistema non va bene poichè se si sa più o meno quando è stata generata la chiave si restringe di molto il range dei possibili numeri in uscita dalla funzione.
“Credo che glibc implementi rand con un generatore congruenziale lineare, il tempo di esecuzione del programma non c’entra.”
Esatto, con modulo 2^32, moltiplicatore 1103515245 e incremento 12345.
Quasi tutte le librerie standard dei vari linguaggi usano un LCG, per cui andrebbero usate solo in casi dove la qualità dei numeri generati non è importante.