Il problema della generazione di numeri casuali è strettamente legato con il problema della sicurezza informatica, infatti i principali metodi di crittografia risultano vulnerabili se non si dispone di un generatore di numeri "veramente" casuali. Vediamo quindi l'innovazione apportata da Intel in questo importate settore.
Potrà sembrare strano che generare numeri causali sia tanto difficile e forse sembra ancora più strano che i numeri casuali abbiano una qualche relazione con la sicurezza informatica. Iniziamo a capire questi due problemi con due racconti molto educativi.
Torniamo indietro al 1995. Supponiamo di voler fare il nostro primo acquisto online, tramite il nostro favoloso browser Netscape ci colleghiamo al sito di Amazon, scegliamo un bel libro e decidiamo di comprarlo. Per effettuare l'acquisto siamo rimandati ad una pagina https, quindi tutti i dati che inviamo sono criptati in modo sicuro per evitare che utenti maliziosi possano intercettare informazioni sensibili. Netscape per criptare i dati usa una sequenza numerica generata in modo casuale di modo da rendere praticamente impossibile decriptare i dati, poichè dovrebbe essere impossibile indovinare una sequenza numerica casuale. Piccolo problema, la sequenza casuale aveva una dimensione fissa di 40 bit, ciò implica circa tre trilioni di possibili combinazioni, sembrano tante ma anche un computer dell'epoca in trenta o poche più ore di lavoro avrebbe potuto identificare la sequenza esatta. Tutto sommato potrebbe anche andar bene così, solo che il presunto numero casuale era generato in base all'ora ed al numero del process id, dati tutt'altro che casuali e facilmente predicibili. Quindi servono numeri casuali molto ben generati. Penserete, va bene, ma sui sistemi seri queste cose non succedono... bene, allora passiamo alla prossima storia.
Andiamo al 2008, tempi recenti quindi, in cui si sarebbe dovuto far tesoro degli errori passati. Tutte le sequenze casuali usate da OpenSSL tra il 2006 ed il 2008 erano generate tramite hashing del "process ID" (numero univoco del processo) in Debian e derivati. La vignetta sottostante commemora quei tempi...
Spero di aver reso bene il concetto. Generare numeri casuali non è una operazione banale ed è di grande importanza.
Il problema di fondo è che, per nostra fortuna, i calcolatori che usiamo quotidianamente sono deterministici e sempre in uno stato logico ben definito (al netto di qualche schermata blue ogni tanto in certi presunti sistemi operativi...), è un non senso generare numeri casuali partendo da un comportamento non casuale.
Fortunatamente "Dio gioca a dadi con l'universo" (contrariamente a quanto pensava Einstein) e quindi non è difficile trovare in natura sorgenti di "casualità".
Una buona soluzione è mostrata nella figura sottostante.
Non ho sbagliato figura, è proprio quello che vedete. Nel 1996, il sito LavaRnd si basò su questo caotico ed impredicibile movimento di liquidi per generare e fornire via web numeri del tutto casuali. Il sito esiste ancora ma si basa su metodi più sofisticati.
Però vogliamo qualcosa di facilmente integrabile in un computer. Certamente si potrebbe usare qualche dato fisico relativo alla CPU o leggere il rumore da un porta a cui non è collegato nessun dispositivo, ma sono fenomeni troppo incontrollabili per i quali non si può garantire una ampia gamma di valori non deterministici.
I ricercatori di Intel hanno sviluppato un circuito digitale per generare numeri completamente casuali in modo semplice e facilmente integrabile in un processore. L'idea alla base è semplice ed illustrata nella figura sottostante.
.png)
[figura tratta da IEEE Spectrum]
Per capirne il funzionamento facciamo riferimeto al grafico sottostante.
[figura tratta da IEEE Spectrum]
Quando la coppia di transistor è nello stato on, la coppia di inverter forza il nodo A ed il nodo B allo stesso stato. Quando il segnale di Clock sale, i transistor sono nello stato off, lo stato dei due inverter è indeterminato, ma a causa del rumore termico ogni nodo passa ad uno stato logico univoco. In tal modo al variare del clock si possono generare sequenze casuali di bit.
Un precedente tentativo sempre da parte di Intel non diede buoni risultati. Basato su un circuito analogico, consumava potenza e non era di facile integrazione.
La soluzione prospettata di recente sembra decisamente più promettente, ancora devono essere fatte tutte le dovute prove per soddisfare una serie di standard internazionali sul tema, ma con buona probabilità la prossima generazione di processori avrà un generatore di numeri casuali altamente attendibile.
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
John Von Neumann
Visita lo spazio dedicato a Intel su Farnell
L’application note che citi (15 anni fa, i pic17… quanti ricordi, penso ormai siano completamente spariti dalla circolazione) genera numeri pseudo casuali, infatti inserendo il famoso 3045h iniziale si ottiene sempre 608Bh quindi a livello matematico non genera un numero casuale che possiamo utilizzare come base per crittografia o codici di sicurezza, password etc. (correggetemi se sbaglio)
Stesso vale anche per la sequenza, infatti, genera sempre la stessa frequenza.
Ecco il codice del pseudo number generator Microchip per i PIC17C42
movwf RandHi
movlw 0x45
movwf RandLo
Random16
rlcf RandHi,W
xorwf RandHi,W
rlcf WREG, F ; carry bit = xorwf(Q15,14)
;
swapf RandHi, F
swapf RandLo,W
rlncf WREG, F
xorwf RandHi,W ; LSB = xorwf(Q12,Q3)
swapf RandHi, F
andlw 0x01
rlcf RandLo, F
xorwf RandLo, F
rlcf RandHi, F
return
Se avete idea del campo di applicazione di questa routine fatemi sapere…..
Vista da una persona non esperta del settore, la routine attualmente utilizzata nei calcolatori può sembrare una perfetta routine di generazione casuale dei numeri quando in realtà non lo è per chi conosce come funziona.
Stessa cosa vale per “Dio gioca a dadi con l’universo (contrariamente a quanto pensava Einstein)”. Ora come ora la meccanica quantistica sta dando risultati sempre più eclatanti, ma chi ci dice che non stiamo guardando la natura con un occhio inesperto e che forse quello che a noi sembra casuale, in realtà è il risultato di qualcosa ben ordinato, non casuale e deterministico?!
Lascio a voi il dubbio.
Se scendiamo a basso_livello la cosa si complica. Infatti generare un numero casuale sui microcontrollori è praticamente impossibile, in quanto non ci sono parametri sconosciuti o random da cui partire. Il tempo è dettato dal clock e quindi qualsiasi operazione o numero di operazioni può essere replicata.
Non sono un matematico ma presumo che esistano degli algoritmi matematici in grado di generare numeri pseudo-casuali ma implementare tali routine su un micro (ad esempio ad 8 bit) penso significhi azzerarne le risorse….
I numeri casuali sono fondamentali per la creazione di algoritmi di crittigrafia, per generare password e per i sistemi di sicurezza in genere.
Tornando quindi al problema di come generare un numero casuale sui microcontrollori l’unica soluzione che mi è venuta in mente (tempo fa quando ho dovuto realizzare una chiave elettronica a microcontrollore) è stato di interagire con l’esterno.
Infatti ho inserito un tasto per la generazione del codice ed appunto il tempo di pressione del tasto era l’evento random. Provateci a premere un tasto ed ottenere due numeri uguali…. espressi in uSecondi ovviamente 🙂
Da questo numero-random poi, tramite delle mappe xor veniva generato il codice segreto da X miliardi di combinazioni (per fare un po di scenografia / richiesto dal commerciale).
Altra soluzione potrebbe essere quella di leggere una tensione (il meno stabile possibile) tramite un ADC e quindi avere un altro parametro random.
Altre idee?
la soluzione del tempo della pressione tasto è si utile, però non genera numeri realmente random in quanto un tempo “minimo” di pressione c’è, a meno che tu non sia capace di premere il tasto per 1 microsecondo.
Per quanto riguarda il tasto si potrebbe avere una variabile che viene incrementata ad ogni ciclo macchina, e alla pressione del pulsante il micro legge la variabile: causa overflow farà ripetere sempre quei 255 valori, ma essendo il tempo della pressione del tasto non determinato dall’interno si avrebbe un codice random.
Se invece vogliamo qualcosa di automatico che non richieda un pulsante potremmo usare un timer per esempio: il sistema è sempre lo stesso che ho descritto prima, però in questo caso usiamo il valore di un timer asincrono alla clock di sistema (per esempio quando si crea l’rtc usando i quarzetti da 32khz sui pic a fianco dei quarzi di sistema da 20mhz)
Se il microcontrollore ha bisogno di un numero random semplicemente và a leggersi il valore del timer asincrono ed è fatta.
Se proprio vogliamo esagerare usiamo 2 variabili: una che è il timer asincrono, e l’altra che è quella che viene incrementata ad ogni ciclo: facciamo qualche operazione matematica a caso ed ecco il nostro numero casuale.
Sono esempi che butto lì, ma che potrebbero funzionare.
E’ proprio vero, talvolta conoscere come funzionano “i piani bassi” è utile per capire le difficoltà che si incontrano nell’eseguire determinate operazioni.
In un microcontrollore ogni operazione, ogni passo, ogni istruzione, è scandita dal clock, quindi è tutto prevedibile.
Solitamente ci sono due esecuzioni asincrone: l’esecuzione “normale” del programma e gli interrupt. Si potrebbe utilizzare come variabile random il tempo trascorso tra un interrupt ed un’altro ma si deve essere sicuri che questi interrupt devono essere casuali altrimenti si rischia di fare un buco nell’acqua.
Un’altra soluzione potrebbe essere quella di utilizzare la lettura analogica di una porta del micro lasciata flottante (come suggerito nell’articolo) ma non sempre si hanno ottimi risultati.
Condivido la soluzione proposta da Emanuele nel generare il numero casuale sfruttando “l’imperfezione” dell’utente, in quanto non riuscirà ad eseguire la stessa operazione sempre allo stesso modo e con gli stessi tempi, soprattutto se quest’ultimo è in microsecondi.
Anche io ho avuto modo di imbattermi in una soluzione simile ma nel mio caso il tempo viene calcolato tra una pressione ed un altra dello stesso tasto.
Per quanto riguarda il discorso sulle risorse usate da una routine di generazione di numeri pseudo-casuali, non sono proprio d’accordo, infatti esistono delle routine di generazione di numeri pseudo-casuali che non richiedono molte risorse, come quella proposta dalla Microchip: http://ww1.microchip.com/downloads/en/AppNotes/00544d.pdf (pagina 4-5).
In questo caso, da un valore di partenza (consigliato dalla Microchip pari a 0x304), si generano via via, numeri pseudo-casuali.
Per esperienza la soluzione migliore è quella del tasto, ma se non se ne ha la possibilità, questa soluzione credo sia buona.
Molti anni fa mi sono imbattuto nel problema di dover generare numeri casuali nel creare un programma.
Mi ricordo che alla fine, anche io, avevo usato come numero fisso della formula usata il, clock del computer. Lo avevo reputato l’unica fonte variabile disponibile.
Tempo fa vagando su internet mi sono imbattuto in alcuni siti che parlavano della teoria del caos.
Cosi ho scoperto che un ricercatore, credo Cinese, ha realizzato un circuito elettronico in grado di generare una forma d’onda sempre diversa. Naturalmente questo circuito è usato al puro scopo scientifico relazionato alla teoria del caos nell’universo.
Alla lettura di questo articolo su i numeri casuali mi sono chiesto se questo circuito è utilizzabile o se è mai stato utilizzato come possibile generatore di numeri casuali. Naturalmente ha bisogno di una adeguata trasposizione analogico / digitale.
Anch’io nel tempo ho dovuto affrontare più volte questa situazione di generare codici rendom.
Quando l’ho dovuto realizzare a livello altra ottobre ho preceduto usando il semplice inverta di tipo CMOS che per la sua natura costruttiva se viene lasciato ingresso flottante, si comporta come antenna e amplifica tutti segnali elettromagnetica dell’aria.
Tutti quei segnali che si trovano in aria sono tipo caotici visto che vengono immessi da talmente di quelle sorgenti trasmettitori cellulari e perfino il rumore termico della materia non è possibile.
A questo punto avevo l’uscita del mio inverta CMOS dei valori casuali queste sufficiente collegarlo a una porta d’ingresso della microcontrollori.
Purtroppo il problema rimane estraendo una sequenza casuale da un protocollo,
visto che per definizione protocollo descrivei valori possibili utilizzato dentro il protocollo quindi limita moltissimo il numero di possibilità
Anche Leon Chua pare avesse il suo circuito
per generare segnali caotici
http://en.wikipedia.org/wiki/Chua's_circuit#Model