RO126730A2 - Metodă de implementare a generatoarelor de numere real-aleatoare în dispozitive fpga - Google Patents

Abstract

Invenţia se referă la o metodă de implementare a generatoarelor de numere real-aleatoare în dispozitive FPGA (Field Programmable Gate Array). Metoda propusă exploatează o caracteristică a circuitelor electronice digitale numită "fanout", pentru a obţine un comportament nedeterminist sau,altfel spus, o sursă de entropie. Pentru aplicarea metodei conform invenţiei este folosit un generator alcătuit din următoarele componente: un bloc driver (1) care generează un semnal periodic şi comandă circuitele unui bloc sarcină (2), circuite care sunt în număr egal cu fanout-ul blocului driver (1), şi un bloc post-procesor (3) ce corectează posibilele dezechilibre ale fluxului de biţi. Metoda conform invenţiei constă, într-o primă etapă, din generarea, de către blocul driver, a unui semnal periodic a cărui frecvenţă este egală cu frecvenţa semnalului de tact, urmată, într-o a doua etapă, de eşantionarea cu aceeaşi frecvenţă a semnalului de ieşire al blocului driver, eşantionare realizată de circuitele blocului sarcină, rezultatele eşantionării fiind combinate, într-o a treia etapă, prin aplicarea unei operaţii SAU-EXCLUSIV pe un anumit număr de biţi consecutivi, în cadrul blocului post-procesor.

Description

METODĂ DE IMPLEMENTARE A GENERATOARELOR DE NUMERE REALALEATOARE ÎN DISPOZITIVE FPGA

Invenția se referă la o metodă de implementare a generatoarelor de numere real-aleatoare în dispozitive FPGA (Field Programmable Gate Array).

Generatorele de numere real-aleatoare se bazează întotdeauna pe un proces fizic nedeterminist, numit și sursă de entropie, ceea ce conduce la obținerea unor numere complet impredictibile, real-aleatoare.

Din acest motiv, generatoarele de numere real-aleatoare sunt superioare în anumite tipuri de aplicații (ex: securitate, criptografie, jocuri) față de generatoarele de numere pseudoaleatoare (generatoare deterministe, bazate pe formule matematice și algoritmi care produc secvențe de numere complet predictibile).

Generatoarele de numere real-aleatoare sunt utilizate cu precădere în domeniile:

• criptografie digitală • criptografie cuantică • protocoale de securitate •jocuri de noroc, loterie

Generatoarele de numere real-aleatoare sunt în genera] dispozitive sau ansambluri de dispozitive fizice, de natură mecanică, electrică, electronică, etc. La ora actuală, cel mai des sunt folosite în practică generatoarele de numere real-aleatoare care se bazează pe dispozitive și circuite electronice, analogice și/sau digitale.

Arhitectura generală a generatoarelor de numere real-aleatoare bazate pe circuite electronice are următoarele componente:

1. sursa de entropie - generează un semnal care este rezultatul unui fenomen fizic nedeterminist;

2. digitizor - eșantionează periodic semnalul generat de sursa de entropie, convertind acest semnal într-o secvență de biți aleatori;

3. post-procesor - ajustează distribuția de probabilitate a ieșirii, compensând imperfecțiunile statistice din interiorul sursei de entropie sau din digitizor.

Pentru asigurarea securității fizice, este foarte util ca generatorul de numere realaleatoare să fie compact, implementat într-un singur dispozitiv electronic care să conțină toate cele trei componente esențiale: sursa de entropie, digitizor și post-procesor. în plus, ideal este ca sursa de entropie să fie tot un sistem digital și nu unul mixt analog-digital.

Dispozitivele electronice FPGA (Field Programmable Gate Array), care sunt rețele de porți logice reconfigurabile, prezintă ambele avantaje menționate anterior, la care se adaugă avantajul flexibilității în proiectare și a unui time-to-market mult redus.

Metoda de proiectare preferată până la ora actuală pentru generatoarele real-aleatoare în dispozitive FPGA, atestată prin lucrări științifice și rapoarte tehnice publicate în literatura de specialitate ([FD02],[KG04],[Golic04]), constă în crearea unei oscilații cu jitter. Această oscilație se obține prin utilizarea unor oscilatoare inelare (ring oscillators) constând într-un număr impar de inversoare conectate într-o topologie de tip inel.

De exemplu, design-ul folosit de Kohlbrenner și Gaj [KG04] utilizează două oscilatoare inelare care se eșantionează reciproc, însă plasarea acestor oscilatoare în CLBurile dispozitivului FPGA este delicată, deoarece frecvențele de oscilație trebuie să fie foarte apropiate.

Prin urmare, obținerea unui design funcțional în parametri acceptabili necesită o plasare manuală a oscilatoarelor, care este neportabilă (necesită o replasare manuală în fiecare familie de dispozitive FPGA). Chiar și prin plasare manuală, calitatea numerelor aleatoare (V2 0 0 9 - 0 1 0 0 2 -3 0 -11- 2009 η

generate este slabă. Pentru creșterea calității este necesară folosirea unui bloc de postprocesare de mari dimensiuni, ceea ce duce ia scăderea semnificativă a debitului.

Golic a propus în [Golic04] două variante promițătoare de oscilatoare inelare clasice folosind concepte înrudite cu registrele de deplasare cu reacție lineară (LFSR - Linear Feedback Shift Register): oscilatoare inelare Fibonacci și Galois. Aceste circuite asincrone cu buclă de reacție (/ber/bncU combină aleatorismul real (dat de fenomenul de jitter din cadrul unor oscilatoare inelare) și pseudo-aleatorismul (dat de registrul LFSR).

Design-ul a fost implementat experimental în dispozitive FPGA, dar nu s-au oferit detalii precise; s-a spus doar că implementarea satisface testele statistice standard, dacă se aplică o post-procesare foarte puternică (un LFSR pe 64 de biți). Principalul dezavantaj al acestui tip de generator este acela că nu este un generator real aleator, ci un generator hibrid care combină elemente ale generatoarelor real-aleatoare cu cele ale generatoarelor pseudoaleatoare.

Parametrii de design ai majorității propunerilor publicate până la ora actuală (cum ar fi: frecvența de eșantionare, volumul post-procesării. și astfel debitul de biți aleatori care rezultă) sunt determinați în principal printr-un proces iterativ (trial-and-errof}, până când șirul de biți produs trece cu succes testele statistice existente la dispoziția comunității științifice internaționale: NIST [RSN+01], TestUOl [L’ES07] sau DIEHARD [Marsaglia96].’

Problema tehnică pe care o rezolvă invenția este implementarea unui generator de numere real-aleatoare în dispozitive FPGA având un debit ridicat și o sursă de entropie solidă (bazată pe un fenomen fizic de natură electronică, care nu este sensibil la plasarea componentelor în interiorul dispozitivului FPGA). De asemenea, invenția are ca scop implementarea unui generator portabil care să funcționeze pe cât mai multe familii de dispozitive FPGA. și deci să aibă o cât mai mare aplicabilitate practică.

Metoda propusă exploatează o caracteristică a circuitelor electronice digitale denumită “fanouf’, pentru a obține un comportament nedeterminist, sau altfel spus o sursă de entropie.

Fanout-uî unei componente logice este definit ca numărul de dispozitive logice ce pot fi conectate la ieșirea sa fără a depăși limitele de curent ale componentei logice. Pentru a menține niveluri logice corecte, ieșirea unei componente logice nu poate comanda un număr infinit de alte dispozitive logice, deoarece dispozitivele logice reale au capacități și rezistențe de intrare.

Prin urmare, dacă ieșirea unei componente logice comandă multe alte dispozitive logice, această componentă logică va avea de „înfruntat” o sarcină capacitivă ridicată, ceea ce încetinește tranziția ieșirii, mărind astfel întârzierea de propagare a semnalului.

în figura 1 se ilustrează timpul de tranziție al unui semnal digital pentru diferite valori ale sarcinii capacitive care este direct proporțională cu fdnout-uL Linia punctată indică momentul eșantionării care în exemplul de față generează un rezultat nedeterminist pentru o sarcină capacitivă de 6.5 nF.

Datorită faptului că întârzierea de propagare a semnalului crește, frecvența operațională maximă a sistemului scade. Prin urinare dacă frecvența depășește o anumită valoare limită care este dată de valoarea fanoui-iilui, atunci apare un comportament nedeterminist.

Generatorul, conform invenției, are următoarele componente (figura 2):

1. blocul Driver - generează un semnal periodic și comandă circuitele din componenta Sarcină',

2. blocul Sarcină - circuite care eșanlionează semnalul generat de componenta

Driver',

3. blocul Post-procesor - circuit care corectează posibilele dezechilibre ale fluxului de biți.

cv-2 Ο Ο 9 - Ο 1 Ο Ο 2 - -

Ο -11- 2009

Fanout-ul blocului Driver este egal cu numărul de circuite din blocul Sarcină. Semnalul generat de blocul Driver este eșantionat în intervalul de timp în care are loc tranziția semnalului.

Soliditatea sursei de entropie este asigurată prin faptul că numărul de circuite din blocul Sarcină este de ordinul miilor. Astfel, intervalul în care semnalul generat de blocul Driver are o valoare nedeterministă este lărgit. în plus, acest semnal va fi eșantionat de fiecare circuit din blocul Sarcină. Rezultatele eșantionării sunt combinate prin aplicarea operatorului SAU-EXCLUSIV (XOR) în cadrul blocului Post-procesor.

în figura 2 este ilustrată implementarea generatorului de numere real-aleatoare propus. Blocul Driver generează un semnal periodic, a cărui frecvență este egală cu frecvența semnalului de tact. Circuitele din blocul Sarcină sunt bistabile de tip D, care vor eșantiona cu aceeași frecvență semnalul de ieșire al blocului Driver.

Implementarea propusă are mai mulți parametrii, cei principali fiind frecvența semnalului de tact și numărul de bistabile din componenta Sarcină. în exemplul de realizare a generatorului, semnalul de tact este generat de un bloc DCM (Digital Clock Manager), având frecvența de 300 MHz.

Numărul de bistabile din blocul Sarcină este 1536 pentru acest exemplu de realizare. Majoritatea bistabilelor vor eșantiona semnalul generat de blocul Driver în momentul tranziției sale. Rezultatele eșantionării sunt combinate prin aplicarea operației SAUEXCLUSIV. Blocul Post-procesor aplică operația SAU-EXCLUSIV pe cinci biți consecutivi pentru creșterea enUOpiei și pentru eliminarea posibilelor dezechilibre ale fluxului de biți extrași din sursa de entropie.

Debitul generatorului astfel obținut este de 60 Mbps, iar șirul de biți produs trece cu succes testele statistice NIST, TestUOl și DIEHARD. Această configurație a fost realizată practic, testată exhaustiv și este funcțională pe următoarele familii de dispozitive FPGA: Xilinx Virtex Π-Pro, Virtex 4. Virtex 5 și Spartan-3E.

Prin aplicarea invenției, se obține un generator de numere real-aleatoare care prezintă următoarele avantaje:

1. debit ridicat - se constată creșterea semnificativă a debitului, comparativ cu alte medode bazate pe dispozitive FPGA ([FD02],[KG04],[Golic04]);

2. calitate ridicată - generatorul furnizează secvențe de numere aleatoare de înaltă calitate, care trec cu succes testele statistice existente: NIST [RSN+01], TestUOl [L’ES07] sau DIEHARD [Marsaglia96];

3. portabilitate - aceeași configurație a generatorului funcționează pe mai multe familii de dispozitive FPGA;

4. simplitate - generatorul este simplu și ușor de implementat/configurat;

5. insensibilitate la plasare - generatorul nu este sensibil la plasarea componentelor în interiorul dispozitivului FPGA.

Bibliografie:

[BL05] M. Bucci and R. Luzzi. Design of Testable Random Bit Generators. In Criptografic Hardware and Embedded Systems - CHES 2005, 7th International Workshop, Edinburgh, Scotland, August 29 - September 1, 2005, Proceedings, ser. Lecture Notes in Computer Science, J. R. Rao and B. Sunai’, Eds., voL 3659. Springer, 2005, pp. 147-156.

[Brouwer06] A. E. Brouwer. Server for bounds on the minimum distance of q-ary linear codes. [Online]. Available: http://www.win.tue.nl/--aeb/.

[BST03] B. Barak, R. Shalliel, and E. Tromer. True Random Number Generators Secure in a Changin^ Environment. In Criptografic Hardware and Embedded Systems - CHES 2003, 5 International Workshop, Cologne, Germany, September 8-10, 2003,

Claims (1)

1. Metodă pentru implementarea a generatoarelor de numere real-aleatoare într-un singur dispozitiv FPGA, caracterizată prin aceea că sursa de entropie o constituie eșantionarea unui semnal digital periodic generat de un bloc Driver (1) având un fanout ridicat, ceea ce determină un timp de tranziție al semnalului mărit, starea logică a semnalului fiind nedeterministă pe perioada tranziției, toate circuitele din blocul Sarcină (2) contribuind la determinarea valorii parametrului fanout și eșantionând semnalul în același timp, rezultatele eșantionării fiind combinate prin aplicarea operației SAU-EXCLUSIV într-un bloc Post-procesor (3).