1

Presentazione dell’articolo:

True Random Bit Generation From a Double-Scroll AttractorMüştak E. Yalçin, Student Member, IEEE, Johan A. K. Suykens, Member, IEEE, and Joos Venderwalle, Fellow, IEEE

POLITECNICO DI MILANO

CORSO: caos deterministico e applicazioni

Matteo Verzillo, matr.666690

Professore: Carlo Piccardi

2

INTRODUZIONE

Matteo Verzillo

La possibilità di generare numeri casuali risulta molto utile in alcune applicazioni,quali:

- simulazioni;

- generazione di test per la valutazione delle performance degli algoritmi;

- metodi di ottimizzazione stocastica per il riconoscimento delle immagini.

Nell’ambito della crittografia l’utilizzo di un generatore di numeri casuali sicuro èaddirittura di vitale importanza (generazione di password, chiavi …).Affinché il RNG sia sicuro occorre che il suo output sia statisticamenteindistinguibile da una sequenza realmente casuale di numeri e che siaimpredicibile.

Generatore di numeri casuali (RNG):

3

INTRODUZIONE

Matteo Verzillo

Gli RNG possono essere suddivisi in tre classi:

-True RNGs (TRNGs): questi generatori operano misurando processi naturaliimpredicibili e sono anche detti basati su hardware perché utilizzano gli aspetticasuali presenti nell’hardware.

- Pseudo RNGs (PRNGs): utilizzano processi deterministici (infatti vengonoanche chiamati RNGs deterministici) per generare una serie di output partendoda uno stato iniziale. Essi sono migliaia di volte più veloci e molto più economicidei TRNGs.

- Hybrid RNGs (HRNGs): utilizzano un TRNG con o senza interazione da partedell’utente (come le battute dei tasti, i movimenti del mouse o il tempo di ricercain un disco), come generatore di origine. Questo generatore viene poi espanso.

Classificazione dei RNGs:

4

INTRODUZIONE

Matteo Verzillo

Lo scopo dell’articolo è quello di mostrare come, utilizzando sistemi caotici atempo continuo, si possa generare una sequenza di bit realmente casuali;ovvero si vuole mostrare la sicurezza di un generatore di numeri casuali basatosu un sistema caotico a tempo continuo.

Per far ciò viene proposto e analizzato un particolare TRNG, e viene verificata lareale casualità e impredicibilità dei bit generati tramite alcuni test statistici a cuiesso è stato sottoposto.

Scopo dell’articolo:

5

TRBG BASATO SU UN ATTRATTORE DOUBLE-SCROLL

Matteo Verzillo

Il TRBG proposto:

6

TRBG BASATO SU UN ATTRATTORE DOUBLE-SCROLL

Matteo Verzillo

Parte Hardware:

- Blocco S1 (oscillatore caotico):è un sistema autonomo del terzo ordine a tempo continuo che presenta unattrattore double – scroll. È qualitativamente simile all’attrattore osservato nelcircuito di Chua.

- Blocco S2 (circuito di soglia):divide lo spazio di stato in tre sotto-spazi. Due di questi sono posizionati incorrispondenza delle due “matasse” dell’attrattore, il terzo, invece, corrispondealla regione di transizione.

Il TRBG proposto:

7

TRBG BASATO SU UN ATTRATTORE DOUBLE-SCROLL

Matteo Verzillo

Parte Software:

- Blocco S3 (generatore di bit):essenzialmente codifica le due “matasse” dell’attrattore (0 se ci si trova sullaprima, 1 se si è sulla seconda).L’unione di S2 e S3 è descritta da una funzione non-invertibile che ha lacaratteristica di migliorare la casualità dell’output. Infatti il campionamento delsegnale nello spazio porta ad un campionamento irregolare dello stesso neltempo. Ciò rende molto difficile eventuali previsioni sui futuri output.

-Blocco S4 (reallineamento):elimina il bias nell’output del generatore di bit. Questo bias dipende dalla densitàdi probabilità del segnale caotico stesso e dalle limitazioni di ampiezza elarghezza di banda.

Il TRBG proposto:

8

OSCILLATORE CAOTICO

Matteo Verzillo

Per generare il comportamento di un attrattore “a doppia matassa” si èrecentemente scoperto un modello semplice di circuito elettrico. Esso è dato da:

S1: = Ax + Bf(Cx)

Realizzazione dell’attrattore double-scroll:

x&

= Β

a

0

0

−−−

= Α

aaa

100

010

[ ]100= C

ℜ∈∧

<−

≥= ζ

ζ

ζζ

01

01)(

se

sef ℜ∈

= 3

z

y

x

x

Questo modello produce un attrattore “a doppia matassa” per a = 0.8

9

OSCILLATORE CAOTICO

Matteo Verzillo

Utilizzando il modello precedentemente descritto e apportando opportunemodifiche viene realizzato il circuito col comportamento desiderato:

Realizzazione dell’attrattore double-scroll:

Cx = Cy = Cz = C

R1 = R

R2 = R4 = R/a

Vx = ax

Vy = ay

Vz = z

10

CIRCUITO DI SOGLIA

Matteo Verzillo

Lo spazio di stato viene suddiviso in 3 regioni (V0, VT, V1) introducendo 2 valori disoglia (c1 = 0 e c2 = -1) e vengono definite due nuove funzioni (che compongonoil blocco S2):

Suddivisione dello spazio di stato:

( )( ) ( )( )

≥

<=

1

11

1

0

ctxse

ctxsetxσ

( )( ) ( )( )

≤

>=

2

20

1

0

ctxse

ctxsetxσ

11

GENERATORE DEI BIT

Matteo Verzillo

Un bit è generato quando il segnale attraversa il sottospazio V0 o il sottospazioV1 passando per il sottospazio VT:

Generazione dei bit:

( )

↑=

↑==

101

110

10

:,01

:,00,

ose

osei σσ

σσσσσ

dove σ0 : o ↑1 indica una transizione da 0 a 1 di σ0 e i = {0, 1, 2, …}.L’immagine seguente mostra la generazione di una sequenza di bit.

12

REALLINEAMENTO E SETTAGGIO DELLA SOGLIA C2

Matteo Verzillo

I generatori casuali di bit, molto frequentemente sono affetti da piccoli errori e daoscillazioni rispetto al comportamento che realmente dovrebbero presentare.

Si utilizzano quindi tecniche di reallineamento (de-skewing) aventi i due seguentivantaggi:

- eliminano il bias che influenza il sistema;

- eliminano la correlazione presente nei dati in uscita dal sistema.

Tecniche di reallineamento (de-skewing):

13

REALLINEAMENTO E SETTAGGIO DELLA SOGLIA C2

Matteo Verzillo

In questo generatore casuale di bit viene utilizzata la tecnica di reallineamentoproposta da Von Neumanns, che prevede di:- convertire la coppia 0 1 in un output pari a 0;- convertire la coppia 1 0 in un output pari a 1;- eliminare le coppie 0 0 e 1 1.

Si ottiene in questo modo il blocco S4, regolato dalla seguente funzione:

La tecnica di reallineamento di Von Neumanns:

( )

=∧=

=∧==

−

−−

011

100,:

1

1

14

ii

ii

iiise

sebS

σσ

σσσσ

Il TRBG proposto ha quindi un unico output:B = {… , b(i-1), b(i), b(i+1), …} con b(i) = {0, 1}.

14

REALLINEAMENTO E SETTAGGIO DELLA SOGLIA C2

Matteo Verzillo

L’eliminazione del bias porta a delle variazioni delle proprietà statistiche delTRBG. Occorre quindi effettuare delle correzioni. Ciò è possibile modificando ilvalore della soglia c2, che ha quindi funzione di parametro di controllo delsistema.

Utilizzando la conoscenza che il rumore ha entropia massima, il valore di sogliac2 viene settato in modo tale da massimizzare la misura di entropia del TRBG.

In questo particolare TRBG il valore corretto per C2 è stimato essere pari a -1,44Volt.

Settaggio della soglia c2:

15

TEST STATISTICI

Matteo Verzillo

Sono 4 test statistici differenti (Monobit, Poker, Runs, Long-run) chegarantiscono la casualità dei dati.Nel nostro caso sono state sottoposte ai test stringhe di 20000 bit prodotte dalTRBG realizzato.Ogni stringa di bit ha passato brillantemente tutti i test.

FIPS 140 - 1:

Diehard:

È composto da 200 istanze di 15 tradizionali test statistici ed è particolarmenteefficace per il testing empirico.Nel nostro caso sono stati sottoposti ai test più di 80 milioni di bit prodotti dalTRBG.Il generatore ha passato l’intera suite Diehard.

16

CONCLUSIONI

Matteo Verzillo

Il TRBG realizzato ha passato entrambe le suite di test statistici, ciò garantiscebuone proprietà statistiche del generatore di bit.Un altro aspetto a favore è che il TRBG è realizzato tramite un integrato, perciòesso può diventare una parte hardware standard.

Ci sono anche tre direzioni in cui effettuare ulteriori approfondimenti:- si potrebbe prendere in considerazione il bit rate del TRBG proposto, cosa chein questo articolo non è stata fatta;- si sono testate le proprietà statistiche del TRBG, ma non ancora l’impredicibilitàdegli output da questo forniti;- si potrebbe provare ad effettuare una previsione dell’output ad un passocercando di sincronizzare un altro sistema caotico a quello del generatore. Ènecessario che il nuovo sistema caotico sia identico a quello del TRBG.

Conclusioni: