Sono così importanti i numeri casuali? che differenze ci sono tra i numeri casuali e pseudocasuali? In questo articolo vedremo come generare numeri veramente casuali.
I generatori di numeri casuali sono dei componenti fondamentali per diverse applicazioni, quali crittografia, algoritmi probabilistici, simulazioni di sistemi stocastici, analisi di algoritmi o protocolli di comunicazione sicuri. In questo ambito i numeri casuali sono utilizzati per costruire simulazioni di natura probabilistica di fenomeni fisici, di problemi decisionali o semplicemente per fornire delle applicazioni ludiche (per esempio, i videogiochi).
C’è chi afferma che esiste un forte legame tra il gioco e le simulazioni probabilistiche, non per niente a tali simulazioni viene dato il nome di metodi di Monte Carlo in onore del famoso casinò a Monaco. La successione dei numeri casuali è utilizzata da diverso tempo in diversi problemi di simulazione quali statistica, integrazione numerica e crittografia. Per questa ragione si ha l’esigenza di disporre di tecniche affidabili per la generazione di numeri casuali. Il termine numero casuale ha tre significati. Nel calcolo delle probabilità denota una variabile casuale a valori numerici (reali o interi): cioè un’entità che non è un numero ma, nell’assioma di Kolmogorov, una funzione misurabile nel senso di Borel a valori reali definita su uno spazio di probabilità, mentre le successioni generate da metodi matematici, che sono per loro natura non casuali ma deterministiche, vengono tecnicamente denominate successioni di numeri pseudocasuali. Questo implica che un vero generatore di numeri casuali deve necessariamente basarsi su dei fenomeni non deterministici. Esistono diverse tecniche per generare una sequenza di valori casuali. E’ possibile ricorrere a dispositivi hardware dedicati, o utilizzare procedure software per estrarre sequenze di valori o, ancora, a volte si ricorre a delle soluzioni miste. I generatori del primo tipo sono comunemente chiamati hardware-based, mentre il secondo gruppo identifica quelli definiti come software-based. Generalmente i generatori software-based sono implementati su un sistema d’elaborazione e i valori numerici che vengono estratti sono ottenuti con l’ausilio di differenti apporti, per esempio quelli definiti da:
Event timing
➤ Sono basati su movimenti del mouse con il relativo clicks
➤ Tastiera
➤ Accessi al disco o alla rete
Oppure dove i dati dipendono dalla storia del sistema:
➤ Clock di sistema
➤ Accesso a dispositivi di I/O
A questo scopo un esempio classico è il generatore implementato in PGP; infatti, le prime versioni utilizzavano come seme le pause durante la battitura. Da questo è facile dedurre che questi tipi di rilevazioni sono lontani da una visione ideale. L’entropia è quasi sempre bassa ed è difficile da valutare così come la robustezza delle osservazioni proposte. Le tecniche basate su software non generano vere e proprie sequenze casuali, ma sequenze pseudo-casuali, cioè valori generati da algoritmi deterministici in grado di superare una serie di test statistici che conferiscono alla sequenza stessa una almeno apparente casualità. Diventa necessario, per questa ragione, scegliere sistemi che siano in grado di offrire dei numeri realmente casuali. Tipicamente il flusso dei dati casuali deve essere rappresentato come un sistema che genera una sequenza X come il prodotto di operazioni su fenomeni microscopici quali il rumore termico o l’effetto fotoelettrico o altri fenomeni quantistici di una grandezza non deterministica.
Tecniche hw-based
Questa tecnica permette di fornire vere e proprie sequenze casuali. Infatti, basandosi su rumore fisico è possibile ottenere realizzazioni che garantiscono la totale casualità del processo che genera i valori stessi: questa caratteristica è garantita dal fenomeno fisico sul quale viene modellato il dispositivo. Esistono diverse tecniche che utilizzano una sorgente di rumore e, fra queste, di particolare interesse sono quelle che adottano la tecnica che prende il nome di “amplificazione diretta”. Questo tipo di tecnica è adottata quando è possibile separare, tramite schermatura, la parte che genera il rumore dalla sezione che si occupa della sua elaborazione. Il piccolo segnale generato dalla sorgente di rumore viene amplificato tramite un amplificatore ad alto guadagno e con banda passante estesa, per poi essere convertito in una sequenza casuale, ad esempio digitale, mediante l’utilizzo di un comparatore sincronizzato con un adeguato segnale di clock. Tipicamente questo genere di dispositivi adotta come sorgente di rumore diodi zener, giunzioni p-n di diodi o transistor bjt che vengono polarizzati inversamente o nella zona di breakdown, oppure semplicemente un resistore ai cui capi viene prelevata una tensione dovuta a fenomeni associati al rumore termico. Sorgenti migliori di quelle citate sono i fotoni e i fenomeni di decadimento radioattivo. Il rumore, nel campo dell’elettronica, è un segnale che generalmente ha un andamento nel tempo non descrivibile in maniera analitica, è quindi possibile studiarlo solo in termini statistici.
La generazione del rumore avviene generalmente a causa del movimento irregolare dei portatori di carica, che determinano la formazione di una tensione o di una corrente di rumore che è misurabile ai capi del dispositivo. In base all’origine e alle caratteristiche il rumore elettronico e suddivisibile in tre grandi categorie: rumore shot, rumore 1\f e rumore termico. Il rumore shot è un segnale generato da un processo poissoniano dovuto alla granulosità dei portatori di carica che si muovono senza seguire il flusso medio delle altre cariche, dando così origine ad un impulso di corrente associato ad ogni singolo carica. Questo tipo di rumore è presente nel dispositivo anche quando ad esso non è applicata nessuna tensione e non è presente un flusso medio di corrente. Il rumore bianco è un particolare tipo di rumore che ha la caratteristica di avere uno spettro di ampiezza costante per tutte le frequenze. Un tale segnale ovviamente è disponibile solo in linea teorica, in quanto non esistono dispositivi in grado di generare uno spettro di ampiezza costante per tutte le frequenze tra zero e infinito. Esistono tuttavia sistemi in grado di fornire uno spettro simile al rumore bianco, dove l’ampiezza è funzione della particolare frequenza e tende a zero con l’aumentare di essa, ma è possibile avere un intervallo in cui questa ampiezza è pressoché costante (rumore bianco a tale intervallo).
Generatori numeri casuali con AVR
La generazione di numeri casuali con AVR è un lavoro che può essere facilitato ricorrendo alle sue risorse hardware onchip. Per esempio, il listato 2 mostra una routine che gestisce l’accesso ad un LED con un tempo impostato in maniera casuale. Per fare questo si è utilizzata una funzione della libreria C, la rand(). In realtà quello che si genera è un numero pseudocasuale, e per ottenere realmente dei numeri casuali è necessario ricorrere ad una sorgente esterna. Per esempio, utilizzando un convertitore ADC con il bit 0, lsb, posto in modalità floating o connesso ad una buona sorgente di rumore in tal caso è possibile ottenere un valore sufficientemente casuale. Oppure si potrebbe costruire una buona funzione random ricorrendo alternativamente ad un RTC, ad un valore di un timer, al valore di un registro o di un indirizzo di I/O. E’ possibile anche utilizzare gli oscillatori on-chip per ottenere un valore casuale; in questo modo si potrebbe sfruttare il jitter prodotto. Il listato 1 mostra una possibile realizzazione di questa tecnica. Il codice mostrato è stato scritto per ATMega168 con una frequenza di 16 MHz. Sostanzialmente, leggendo il codice è possibile notare l’uso del registro r24, il watchdog è stato triggerato a 16 millisecondi. Il registro r24 è utilizzato come contatore (3 clocks/iterations) fino a quando il watchdog viene triggerato. I risultati del listato 1 indicano una buona approssimazione, anche se è possibile ottenere valori ancora migliori. Per concludere, è possibile anche utilizzare come ingresso ad un pin del convertitore ADC il valore di un transistor BJT con polarizzazione inversa (listato 3).
; ; Does the watchdog fire with ; a good random spread? ; .INCLUDE “m168def.inc” .org 0 rjmp mainp .org 0x40 mainp: ldi r16,0xFF ldi r17,0x04 out SPL,r16 out SPH,r17 ;set up uart 16M/19200/16 = 52 ldi r16,52-1 sts UBRR0L,r16;reload ldi r16,0x06 sts UCSR0C,r16;8 bit ldi r16,0x18 sts UCSR0B,r16;enable in r16,MCUSR andi r16,0x0F cpi r16,0x08 breq acquiremode ;power on, not acquisiton. so. clr r16 out MCUSR,r16 wdr ldi r16,0x08 sts WDTCSR,r16 stopp: rjmp stopp ;acquiremode: clr r16 out MCUCR,r16 mov r16,r24 sub r16,r25 ;to count increment distance mov r25,r24 rcall sendc ldi r16,0x08 sts WDTCSR,r16 acqloop: inc r24 rjmp acqloop sendc: lds r17,UCSR0A sbrs r17,5 rjmp sendc sts UDR0,r16 ret
| Listato 1 - watchdog e casualità |
void GetRandomTime(void)
{
int i, iRandomNumber;
srand(9);
/********RANDOM DELAY*********/
while(1)
{
iRandomNumber = (rand() % 10) + 11;
for(i=0; i<iRandomNumber; i++)
{delay_ms(1000);
}
LightLED();
}
}
| Listato 2 - accessione e spegnimento di un LED |
coj=
0;
for (j=0;j<8;j++)
{
ranbyte<<=1;
ranbit=0;
lastranbit=0;
while (ranbit==lastranbit)
{
lastranbit=(read_adc(0)&1);
ranbit=(read_adc(0)&1);
}
ranbyte^=ranbit;
}
| Listato 3 - porzione di codice per generazione da ADC |
Bellissima tematica, che a me piace tanto. I numeri casuali non esistono poiché se uno conoscesse tutte le condizioni che sono alla base (esempio peso del dado, forza di lancio, gravità, inclinazione del lancio, e 1000 altre variabili) potrebbe calcolare, in anticipo l’esito della faccia del dado.
Si parlerebbe, piuttosto, di eventi imprevisti, di cui non si conoscono le condizioni iniziali di accadimento.