Numeri random a buon mercato

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]

Press ESC to close