Bachelor Degree Thesis / Tesi di Laurea Triennale

IN ITALIAN ONLY

TESI DI LAUREA:
"Realizzazione su FPGA di un sistema di controllo per l'incremento dell'entropia di un generatore di bit casuali".
Relatore: Prof. V. Vignoli - Correlatore: Ing. T. Addabbo - A.A. 2006/2007.

ABSTRACT:

La generazione di numeri casuali ricopre un ruolo fondamentale in svariati settori: ad esempio in crittografia [1-8], nelle diagnosi di guasti in sistemi complessi [9], nella generazione di segnali a spettro espanso per telecomunicazioni [10,11], nella computazione stocastica [12].
Le sequenze di numeri casuali sono generate mediante dispositivi denominati Random Number Generator (RNG), assimilabili a sorgenti informative ad entropia massima, ovvero sorgenti tempo discreto di simboli statisticamente indipendenti e a distribuzione uniforme.
Gli RNG sono usualmente classificati in generatori pseudo random (PRNG) e true random (TRNG) [13].
I PRNG sono degli algoritmi ricorsivi implementati su macchine a stati finiti e capaci di generare sequenze periodiche dalle caratteristiche simili a quelle idealmente casuali. Fra i PRNG comunemente impiegati, i generatori alle ricorrenze lineari (ad esempio i Linear Feedback Shift Registers (LFSR) ed i Linear Congruential Generators (LCG)) sono quelli che hanno avuto maggiore diffusione [14,15].
I TRNG sono dispositivi generalmente realizzati mediante circuiti analogici che si basano sul campionamento di processi dinamici di una delle due seguenti classi:
  •  Processi fisici intrinsecamente aleatori;
  •  Processi associati a sistemi dinamici non lineari in regime di caos deterministico.
Le sequenze generate da un TRNG sono quindi intrinsecamente aleatorie, con grado di impredicibilità legato alle caratteristiche del processo dinamico su cui esso si basa. Fra i TRNG del primo tipo si hanno circuiti basati sull'amplificazione di rumore elettronico, sul campionamento di oscillatori a jitter elevato, e sullo sfruttamento di specifici fenomeni stocastici [16,17].
In generale questi TRNG risultano sensibili alle tolleranze del processo implementativo e all'accoppiamento elettromagnetico con segnali deterministici. Fra le soluzioni citate, l'approccio basato sull'amplificazione del rumore elettronico è penalizzato anche dalla necessità di condizionare la sorgente di rumore, cosa che altera le sue caratteristiche statistiche.
I TRNG appartenenti alla seconda classe hanno preso campo in questi ultimi anni [18,19]. Le conoscenze raggiunte sui meccanismi che regolano l'evoluzione dinamica dei sistemi dinamici caotici forniscono infatti strumenti teorici per il progetto di RNG nominalmente ideali [20]. In generale questi TRNG si basano sul campionamento e la quantizzazione dello stato dei sistemi caotici implementati con diversi approcci circuitali [18,21]. Le soluzioni proposte fino ad ora sono compatibili con la tecnologia CMOS e tipicamente presentano una ridotta sensibilità alle interferenze elettromagnetiche. A fronte di questi vantaggi tuttavia, nei circuiti reali, le tolleranze del processo implementativo comportano un'alterazione dei parametri nominali di progetto, provocando una degradazione significativa delle caratteristiche statistiche delle sequenze generate, ed una conseguente riduzione dell'entropia della sorgente. Tale degradazione è contrastabile con un post-processing digitale, a spese tuttavia sia di un aumento della complessità circuitale del TRNG sia di una riduzione significativa della frequenza di emissione dei simboli (throughput) [18,22,23]. È quindi di notevole interesse individuare soluzioni che minimizzino la necessità di post-processing, come ad esempio l'impiego di sistemi caotici retroazionati ed autocorrettivi [24] recentemente proposto. In questi sistemi, il TRNG, è corredato da un sistema di controllo che sulla base dell'analisi statistica delle sequenze generate, altera il comportamento dinamico del generatore, massimizzando l'entropia senza ridurre il throughput.
Oggetto del presente lavoro di tesi è stata la realizzazione su Field Programmable Gate Array (FPGA) del sistema di controllo proposto in [24] per l'incremento dell'entropia di un generatore di bit casuali (TRBG, True Random Bit Generator) basato sulla mappa caotica

xn+1 = Bxn - A sign(xn).

Il sistema di controllo, che agisce attraverso la modifica dei parametri del sistema caotico, è basato sull'analisi statistica delle sequenze binarie generate e ha lo scopo di minimizzare la diminuzione dell'entropia dovuta agli effetti delle non idealità introdotte dalle tolleranze del processo implementativo.
Il sistema di controllo, realizzato mediante una macchina a stati finiti descritta in linguaggio VHDL utilizzando il sistema di sviluppo Altera Quartus II, è stato testato interfacciando la FPGA con il TRBG realizzato mediante una Field Programmable Analog Array (FPAA).
In dettaglio, la verifica sperimentale è stata eseguita analizzando le sequenze ottenute dal generatore di numeri casuali acquisite ed elaborate mediante un PC impiegando il software LabView della National Instruments.


BIBLIOGRAPHY:

[1] A. Menezes, P. Van Oorschot, and S. Vanstone, Handbook of Applied Cryptography. CRC Press, 1997.

[2] J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard. Springer Verlag, 2002.

[3] A. S. Eli Biham, Differential Cryptanalysis of the Data Encryption Standard. Springer Verlag, 1993.

[4] “DES: Data Encryption Standard,” Available online at: http://www.itl.nist.gov/fipspubs/fip46-2.htm.

[5] “RSA,” Available online at: http://csrc.nist.gov/cryptval/dss/rsaval.html, http://www.rsa.com/.

[6] “AES: Advanced Encryption Standard,” Available online at: http://csrc.nist.gov/CryptoToolkit/aes/index2.html.

[7] U. D. o. C. National Bureau of Standards, “Data encryption standard,” FIPSPub, vol. 56, January 1977.

[8] W. Mao, Modern Cryptography. Prentice Hall, 2004.

[9] R. David, Random Testing of Digital Circuits: Theory and Application. Marcel Dekker, 1998.

[10] R. Rovatti, G. Setti, and G. Mazzini, “Chaotic complex spreading sequences for asynchronous ds-cdma. part ii. some theoretical performance bounds,” IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., vol. 45, no. 4, pp. 496–506, 1998.

[11] L. E. M. Jhong Sam Lee, CDMA Systems Engineering Handbook. Artech House, 1998.

[12] F. Klebaner, Introduction to Stochastic Calculus with Applications. Imperial College Press, 2005.

[13] “NIST Special Publication 800-22: A statistical test suite for random and pseudorandom number generators for cryptographic applications,” 2001.

[14] D. Knuth, The art of computer programming, 2nd ed. Addison-Wesley, 1981, vol. 2.

[15] A. M. Frieze, J. Hastad, R. Kannan, J. C. Lagarias, and A. Shamir, “Reconstructing truncated integer variables satisfying linear congruences,” SIAM Journal on Computing, vol. 17, no. 2, pp. 262–280, 1988.

[16] C. Petrie and A. Connelly, “A noise-based ic random number generator for applications in cryptography,” IEEE Transaction on Circuits and Systems I, vol. 47, no. 5, pp. 615–621, 2000.

[17] D. C. Ranasinghe, D. Lim, S. Devadas, D. Abbott, and P. H. Cole, “Random numbers from metastability and thermal noise,” IEEE Electronics Letters, vol. 41, no. 16, pp. 13–14, 2005.

[18] A. Fort, F. Cortigiani, S. Rocchi, and V. Vignoli, “High-speed true random noise generator,” Analog Integrated Circuits and Signal Processing Journal, vol. 34, pp. 97–105, 2003.

[19] A. Rodriguez-Vazquez, M. Delgrado-Restituto, S. Espejo, and J. Huertas, “Switched-capacitor broadband noise generator for CMOS VLSI,” Electronics Letters, vol. 27, no. 21, pp. 1913–1915, 1981.

[20] T. Stojanovski and L. Kocarev, “Chaos-based random number generator – part I: Analysis,” IEEE Transactions on Circuits and Systems I, vol. 48, no. 3, pp. 281–288, 2001.

[21] A. Rodriguez-Vazquez, J. Huertas, and L. Chua, “Chaos in switched-capacitor circuit,” IEEE Transaction on Circuits and Systems I, vol. 32, no. 10, pp. 1083–1085, 1985.

[22] S. Callegari, R. Rovatti, and G. Setti, “Embeddable adc-based true random number generator for cryptographic applications exploiting nonlinear signal processing and chaos,” IEEE Trans. on Signal Processing, vol. 53, no. 2, pp. 793–805, 2005.

[23] M. E. Yalcyn, J. A. K. Suykens, and J. Vandewalle, “True random bit generation from a double-scroll attractor,” IEEE Transaction on Circuits and Systems I, vol. 51, no. 7, pp. 1395–1404, 2004.

[24] T. Addabbo, M. Alioto, A. Fort, S. Rocchi, and V. Vignoli, “A feedback strategy to improve the entropy of a chaos-based random bit generator,” IEEE Transaction on Circuits and Systems – part I, vol. 53, no. 2, pp. 326–337, 2006.

 

Related Resource