Era un uggioso pomeriggio milanese dello scorso anno quando, procrastinando lo studio, venni colpito da un lampo di genio. “Cosa succederebbe se facessi un generatore di numeri casuali alimentato a banane?“. Preso dall’idea andai subito a raccontarla al coinquilino anch’esso elettronico.
Lui mi guardò in faccia e scoppiò a ridere. In quel momento capii che avevo nelle mie mani un grande progetto.
Prima di essere preso per pazzo: ha davvero un senso, e questo post è qui per spiegarvelo. Partiamo dalla radice del problema: i computer sono sistemi deterministici. Detto in modo meno complicato, se gli diamo sempre gli stessi dati in ingresso, ci restituiscono sempre gli stessi valori in uscita (Non chiedetemi perché, se aprite quattro volte un programma nel corso della giornata, due volte si apre e due no; quello gli scienziati lo stanno ancora studiando). Che è esattamente quello che ci aspettiamo da un calcolatore. È chiaro da subito, però, che il determinismo e la casualità non sono grandi amici. Anzi, di per sé un computer, non è in grado di fare nulla di casuale.
Se chi legge è tra i fortunati ad aver scritto qualche programma in C, sarà sicuramente incappato in qualche chiamata della funzione rand(). Io stesso ne ho fatto largo uso nei post ([1][2]) riguardo al calcolo di pi greco col metodo Monte Carlo.
Per chi non avesse mai avuto la fortuna, rand() è la funzione che (con molta fantasia nel nome) permette di ottenere numeri casuali in un programma in C. Ma abbiamo appena finito di dire che non c’è nulla di casuale nei computer. Quindi?
Quindi ci hanno ingannato. Purtroppo, amici, siamo stati tutti ingannati. Mi prendo anche io la mia parte di responsabilità per averli chiamati, con leggerezza, numeri casuali nei post sul pi greco. Avremmo dovuto chiamarli numeri pseudocasuali. Che è il nome che gli informatici danno a quei set di numeri che hanno la distribuzione in linea con i numeri casuali, ma che in realtà casuali non sono.
Per capirci meglio, per essere definito casuale un set di numeri deve avere almeno (condizione necessaria ma non sufficiente) queste due caratteristiche:
- Ogni numero deve avere la stessa probabilità di ogni altro numero di comparire nella nostra lista (preso un intervallo di riferimento). Questo è quello che chiamiamo distribuzione uniforme;
- La sequenza dei numeri non deve poter essere prevista in anticipo.
È evidente che la difficoltà delle macchine deterministiche è quella di rispondere al punto 2. Il punto 1 viene risolto con facilità, e da luogo a quelli che abbiamo appena chiamato numeri pseudocasuali. Numeri che rispettano la distribuzione uniforme, ma che in realtà non sono veramente casuali.
E insomma, le banane cosa c’entrano?!
Adesso ci arriviamo!
Quando è necessario fornire ad un computer dei veri numeri casuali, si usano dei sistemi hardware, detti appunto true random number generator (TRNG). Esisono tanti tipi di TRNG, che sfruttano diverse grandezze fisiche casuali e le convertono in informazioni digitali che vengono passate al computer.
I più comuni sfruttano fenomeni fisici come il rumore termico dei resistori, l’effetto valanga dei diodi ed altri effetti caotici. Altri sfruttano fenomeni quantistici più complessi come il rumore shot, il decadimento radioattivo o effetti fotonici.
La via percorribile utilizzando le banane è quella del decadimento radioattivo. Le banane infatti sono note per contenere molto potassio, e una piccola ma significativa percentuale del potassio presente in natura è radioattiva. Nello specifico parliamo dell’isotopo 40K, che costituisce lo 0,01% del potassio in natura. E poi sono buonissime con il limone e lo zucchero, che da solo sarebbe un ottimo motivo per averne sempre una a portata di mano.
Ora che l’affermazione del “generatore di numeri casuali alimentato a banane” ha un po’ più di senso o almeno un po’ di contesto, resta una domanda: cosa ce ne facciamo dei veri numeri casuali in un computer? La mia risposta vorrebbe essere “non mi interessa, voglio che il focus del mio progetto sia limitato al generarli”, ma sono sicuro che lascerebbe molti insoddisfatti.
Per cui proverò a rispondere anche a questa domanda: la crittografia. Questa è la principale ragione per cui vengono studiati i numeri casuali e il loro rapporto coi calcolatori. I numeri casuali vengono usati per generare le chiavi crittografiche, che sono l’unico fattore a determinare l’efficacia di un sistema di crittografia. Come afferma il Principio di Kerckhoffs: “la sicurezza di un crittosistema non deve dipendere dal tenere celato il crittoalgoritmo ma solo dal tenere celata la chiave”.
È chiaro che, se chi attacca può prevedere in qualche modo la chiave, questa non sarà più nascosta e saremo in presenza di un sistema vulnerabile. Un “buon random” quindi sta alla base di un buon sistema crittografico. [3]
Ok ma… se il random è casuale, come facciamo a distinguere un buon random da un cattivo random?
Per analizzare la qualità dei generatori di numeri casuali, di solito si fa ricorso a degli strumenti software progettati appositamente. Due dei più diffusi sono ent [4] e dieharder [5]. Il primo è stato progettato come test leggero per i generatori di numeri casuali a decadimento radioattivo, è molto semplice e veloce, necessita di pochi dati ma il risultato è puramente indicativo.
Dieharder di contro è una suite di test che viene considerata lo standard di riferimento per i generatori di numeri casuali, esegue test molto approfonditi ma necessita di gigabyte di campioni su cui eseguire i suoi test.
Per ora ci concentreremo solo sui risultati ottenuti con ent.
Prepariamo i dati per eseguire un primo test con ent.
I dati vengono scritti sulla seriale dal generatore sulla seriale, possiamo salvarli su un file da console linux con cat /dev/ttyACM0 >> campionetesto.txt. Sfruttiamo il comando di redirect degli stream di bash in modalità “append“, in questo modo potremo interrompere l’acquisizione e riprenderla più tardi senza sovrascrivere il file.
Il campione raccolto nel corso di due giorni consta di 90628 numeri, uno per riga, compresi tra 0 e 65535. I numeri sono però salvati come file di testo ascii, mentre ent analizza file binari. Si può scrivere un brevissimo programma in C per convertirli in binario:
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdint.h>
int main(int argc, char const *argv[]) {
FILE * lettura = fopen("campionetesto.txt", "r");
assert(lettura != NULL);
FILE * scrittura = fopen("campione.txt", "wb");
assert(scrittura != NULL);
uint16_t N = 0; //N is 16 bytes
char bytes[2];
char buffer[6]; // 5 char + terminator
do{
fscanf(lettura,"%s",buffer); // put one line in the buffer
N = atoi(buffer); // from char array to integer
bytes[0] = (N >> 8); // take the 8 msb
bytes[1] = (N & 0xFF); // take the 8 lsb
fwrite(bytes, 1, sizeof(bytes), scrittura); // output raw msb and lsb
}while (!feof(lettura));
fclose(lettura);
fclose(scrittura);
return 0;
}
Fatto questo, possiamo eseguire per la prima volta il test di ent:
valerio@valerio ~/tests $ ./ent campione.txt Entropy = 7.997995 bits per byte. Optimum compression would reduce the size of this 181256 byte file by 0 percent. Chi square distribution for 181256 samples is 498.15, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 127.4942 (127.5 = random). Monte Carlo value for Pi is 3.138799695 (error 0.09 percent). Serial correlation coefficient is 0.005408 (totally uncorrelated = 0.0).
Ent ci resitutisce diversi parametri:
- Entropia: l’entropia è la quantità di “casualità” contenuta in una porzione di informazione. La teoria dell’informazione ci dice che la minima dimensione teoricamente ottenibile tramite compressione senza perdite di informazione, è rappresentata dal valore di entropia.
- Distribuzione chi quadro: questo test viene usato per capire quanto bene la distribuzione dei nostri valori aderisce a una distribuzione teorica (nel nostro caso la distribuzione uniforme). Dal manuale di ent, questo valore deve essere più vicino possibile a 256, con valori percentuali compresi tra 10 e 90%
- Media aritmetica: La semplice media aritmetica dei nostri bit. Essendo i nostri valori compresi tra 0 e 255, dovrebbe essere circa uguale a 127.
- Valore di pi greco col metodo Monte Carlo: Il metodo dovrebbe essere ormai fin troppo conosciuto da chi segue i miei post, in questo contesto rappresenta però più un dato simpatico che un dato utile.
- Autocorrelazione: Serial correlation in inglese, rappresenta la dipendenza tra i valori della serie. Nel caso ottimo deve essere uguale a zero.
Da questo primo test tutti i valori risultano passabili, tranne il chi quadro. Nel prossimo post approfondiremo il perché e le possibili soluzioni.
La seconda parte è disponibile qui.
Note:
[1] Follia computazionale: pi greco e il metodo Monte Carlo
[2] Follia computazionale: pi greco, i thread e la follia collettiva
[3] inside secure – The importance of true randomness in cryptography – white paper
[4] Ent: A Pseudorandom Number Sequence Test Program
[5] Dieharder: A Random Number Test Suite – Robert G. Brown
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.