Nicolcioiu A.pdf

7/23/2019 Nicolcioiu A.pdf

http://slidepdf.com/reader/full/nicolcioiu-apdf 1/11

24

IMPLEMENTAREA ALGORITMULUI RSA FOLOSIND STRUCTURI

HARDWARE RECONFIGURABILE

RSA ALGORITHM IMPLEMENTATION USING FPGA

NICOLCIOIU ANDREEA-TEODORADoctorand Institutul de Economie Mondială

Facultatea de Sisteme Electronice şi Informatice Militare, Academia Tehnică Militară

E-mail: [email protected]

Rezumat: Comunicaţiile în această societate informatizată se bazează din ce în ce mai mult pe

Internet. O problemă majoră a reţelelor de calculatoare şi a comunicaţiilor prin Internet o reprezintă

securitatea informaţiilor. Algoritmii criptografici cu chei publice sunt utilizaţi pentru a asigura

confidenţialitatea, autenticitatea şi non-repudierea comunicaţiilor în mediul electronic. Această

lucrare analizează algoritmii matematici utilizaţi în implementarea unei arhitecturi a algoritmului

criptografic cu chei publice RSA, folosind structuri hardware reconfigurabile.

Cuvinte cheie - algoritm RSA, criptografie, criptografie cu chei publice, FPGA

Abstract: Communications in the modern society rely more and more on the Internet. A major problem in computer networks and communications via the Internet is the information security.

Public-key cryptography algorithms are used to ensure confidentiality, authenticity and non-

repudiation of data through the Internet. This paper analyzes the mathematical algorithms used in

implementing an RSA algorithm architecture using FPGA devices.

Key words - cryptography, FPGA, public-key cryptography, RSA algorithm



25

1. Introducere

Progresele enorme în tehnologia reţelelor au dus la schimbări majore asupra modului în care

se comunică şi se fac afaceri pe Internet. Cu toate acestea, pentru transmiterea datelor confidenţiale,

avantajele oferite de Internet sunt diminuate de principalul dezavantaj al reţelelor publice: riscurilede securitate. Creşterea semnificativă a traficului de date confidenţiale pe Internet a făcut ca această

problemă de securitate să devină o problemă fundamentală. Prin urmare, aplicaţiile precum serviciile

bancare electronice, comerţul electronic, reţelele virtuale private (VPN-uri) necesită un mod eficient

şi rentabil de a aborda ameninţările de securitate ale reţelelor publice.

Atributele securităţii informaţiilor sunt disponibilitatea, confidenţialitatea, integritatea

informaţiei, autenticitatea şi non-repudierea. Disponibilitatea asigură utilizatorilor legali informaţia

atunci când este necesară. Funcţia de confidenţialitate blochează accesul utilizatorilor nelegitimi la

informaţie, păstrând informaţiile private, private. Integritatea informaţiei este funcţia de securitate

care protejează informaţia împotriva modificărilor neautorizate sau accidentale. Autenticitatea permite asocierea între informaţie şi sursa legală de producere a ei. Non-repudierea este funcţia de

securitate a unui sistem informaţional care asociază informaţiei dovezi că aceasta a fost trimisă de

expeditor destinatarului legal şi că a fost recepţionată de acesta fără posibilitatea de a contesta aceste

aspecte.

Criptografia este componenta fundamentală utilizată pentru asigurarea securităţii traficului pe

Internet. Algoritmii criptografici asigură atributele de securitate ale informaţiei enumerate anterior.

Sistemele criptografice cu chei private (simetrice) folosesc aceeaşi cheie atât în procesul de criptare

cât şi în procesul de decriptare. Cheia utilizată în sistemele criptografice cu chei private trebuie să

rămână secretă şi să fie distribuită entităţilor prin canale sigure. Exemple de algoritmi cu chei privatefolosiţi la scară largă sunt: AES (Advanced Encryption Standard), DES (Data Encryption Standard),

3DES (Triple DES), Blowfish, RC4, etc. Sistemele criptografice cu chei publice (simetrice) utilizează

o pereche de chei: o cheie folosită pentru criptarea datelor şi o cheie folosită pentru decriptarea

datelor. Sunt de asemenea utilizate în semnăturile digitale. Exemple de sisteme criptografice cu chei

publice sunt: RSA, ElGamal, Diffie-Hellman.

Algoritmii de criptare impun cerinţe de putere de procesare foarte mare care pot gene ra

blocaje în reţelele de mare viteză. Implementarea unui algoritm criptografic trebuie să atingă putere

mare de procesare pentru a utiliza pe deplin banda de reţea disponibilă. Pentru a urmări schimbările

rapide ale algoritmilor şi ale standardelor, o implementare criptografică trebuie să suporte diferiţialgoritmi şi trebuie să aibă capacitate de actualizare. Soluţia finală pentru această problemă ar fi un

procesor care poate oferi flexibilitatea implementărilor software şi performanţa implementărilor

hardware.

Soluţia este reprezentată de circuitele FPGA care pot fi reconfigurate şi oferă performanţe

ridicate la un cost rezonabil. Această lucrare propune o implementare a algoritmului criptografic cu

chei publice RSA folosind structuri hardware reconfigurabile.



26

2. Algoritmul RSA

Algoritmul RSA este denumit după Ron Rivest, Adi Shamir si Leonard Adleman, care l -au

inventat în anul 1977. Algoritmul RSA este cel mai utilizat algoritm cu chei publice. Poate fi folosit

pentru a cripta mesaje fără a fi necesar un schimb de chei separat în prealabil.Acest algoritm poate fi folosit atât pentru criptare cu chei publice cât şi pentru semnături digitale.

Securitatea acestuia se bazează pe dificultatea factorizării numerelor prime foarte mari. Un emiţător

A poate trimite un mesaj criptat unui receptor B fără a face schimb în prealabil de chei secrete.

Emiţătorul A utilizează cheia publică a lui B pentru a cripta mesajul şi B îl decriptează folosind cheia

sa privată, cunoscută doar de el. Algoritmul RSA poate fi folosit şi pentru a semna un mesaj. Astfel,

A poate semna un mesaj folosind cheia sa privată şi B poate să verifice semnătura folosind cheia

publică a lui A.

Algoritmul RSA cuprinde trei paşi: generarea cheii, operaţia de criptare şi operaţia de decriptare.

2.1. Al gori tmul de generare a cheii

1. Se aleg aleatoriu două numere prime mari, p şi q, care au acelaşi ordin de mărime. Pentru

a genera numerele prime p şi q, se generează aleatoriu un număr având lungimea de k/2 biţi, unde k

reprezintă lungimea pe biţi a modulului n; se setează la valoarea 1 bitul cel mai puţin semnificativ (se

asigură ca numărul să fie impar) şi se setează la valoarea 1 primii doi cei mai semnificativi biţi ( se

asigură că bitul cel mai semnificativ al lui n este setat); se verifică dacă numărul este prim ( se

utilizează testul Rabin-Miller); dacă nu este prim, se incrementează numărul cu doi şi se verifică din

nou dacă este prim.

Astfel, s-a găsit numărul p.

2. Se repetă acelaşi procedeu pentru numărul q pornind de la un număr întreg generat aleatoriucu o lungime egală cu k -k/2. Dacă p<q, se vor inter -schimba cele două valori (acest pas se efectuează

doar dacă se va folosi forma CRT, Chinese Remainder Theorem). Dacă p=q (probabilitate foarte

scăzută), se va verifica generatorul de numere aleatoare. Alternativ, în loc să se incrementeze cu 2,

se va genera un alt număr aleator de fiecare dată. În (NIST 2012) şi (NIST 2005) sunt stipulate reguli

stricte pentru generarea unor numere prime tari şi alte restricţii pentru a minimiza posibilitatea ca

atacuri cunoscute să fie folosite asupra algoritmului.

3. Se calculează n=p*q. Produsul n calculat va reprezenta modulul în care se vor efectua

operaţiile de criptare şi decriptare.

4. Se calculează φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1).5. Se va alege, aleatoriu cheia de cifrare e, 1 < e < φ(n) , astfel încât e şi φ(n) să fie relativ

prime. În practică, valorile cele mai utilizate ale parametrului de cifrare e sunt 3, 5, 17, 257 şi 65537

(216+1). Aceste valori sunt alese deoarece sunt prime şi măresc viteza de execuţie a operaţiei de

exponenţiere modulară, având doar doi biţi cu valoarea 1.

6. Se calculează exponentul secret d, 1<d< φ(n), astfel încât e*d=1 mod φ(n). Pentru a calculavaloarea parametrului d, se utilizează Algoritmul Extins al lui Euclid, calculându-se d=e-1 mod φ(n),

scris şi sub forma d=(1/e) mod φ(n). Această operaţie este denumită inversie modulară.

Perechea (e, n ) reprezintă cheia publică a algoritmului de criptare. Cheia privată este

reprezentată de parametrii (d,p,q). Valorile parametrilor d, p, q şi φ(n) trebuie păstrate secrete.• n este denumit modul;



27

• e este denumit exponent public sau exponent de criptare sau doar exponent;

• d este denumit exponent secret sau exponent de decriptare.

2.2. Operaţia de criptare a algoritmului RSA

1. Se obţine cheia publică (n,e).

2. Se reprezintă mesajul în clar ca un număr întreg pozitiv m, 1<m<n

Când se reprezintă octeţii mesajului în clar ca un număr întreg m, este important să se adauge

caractere de padding pentru ca dimensiunea numărului întreg m să fie mare şi mai puţin vulnerabilă

la anumite tipuri de atacuri. Dacă m=0 sau 1 sau n-1 securitatea este inexistentă deoarece textul cifrat

va avea aceeaşi valoare. PKCS#1 oferă mai multe detalii despre reprezentarea octeţilor mesajului în

clar sub forma mesajului număr întreg m. Este important ca m să fie mai mic decât n, altfel algoritmul

va eşua.

3. Se calculează textul cifrat c = me mod n. 4. Se transmite textul cifrat.

2.3. Operaţia de decriptare a algori tmului RSA

1. Se utilizează cheia privată (d, n) pentru a calcula m = cd mod n.

2. Se extrage mesajul în clar din mesajul reprezentativ m.

2.4. Operaţia de semnare digitală cu algoritmului RSA

1. Se creează un rezumat (message digest) al informaţiei care va fi trimisă.

2. Se reprezintă acest rezumat ca un număr întreg m cu valoarea între 1 şi n-1. Operaţiile dedecriptare şi de semnare sunt identice din punct de vedere matematic, amândouă utilizând cheia

privată. Similar, operaţiile de criptare şi de verificare a semnăturii utilizează aceleaşi operaţii

matematice cu cheia publică. Cu toate acestea, există diferenţe importante în implementare:

semnătura este derivată dintr -un mesaj rezumat al informaţiei originale. Cel care verifică semnătura

va trebui să urmeze exact acelaşi proces pentru a deriva mesajul rezumat, utilizând acelaşi set de date.

Metodele recomandate pentru derivarea numerelor întregi reprezentative sunt diferite pentru criptare

şi semnare (în cazul criptării se foloseşte un padding random iar în cazul semnăturii electronice se

foloseşte acelaşi padding de fiecare dată)

3. Se foloseşte cheia privată (n,d) pentru a calcula semnătura s=md mod n. 4. Se transmite semnătura destinatarului.

2.5. Operaţia de verificare a semnătur ii digitale cu algoritmului RSA

1. Se foloseşte cheia publică a expeditorului (n,e) pentru a calcula valoarea întreagă v= se

mod n.

2. Se extrage rezumatul mesajului din numărul întreg calculat.

3. În mod independent se calculează rezumatul informaţiei care a fost semnată.

4. Dacă cele două valori rezumate sunt identice, atunci semnătura este validă.



28

3. Algoritmi matematici utilizaţi în efectuarea operaţiilor aritmetice specifice RSA Exponenţierea modulară este un tip de exponenţiere care se calculează modulo un număr

întreg n. Este o operaţie care se utilizează în criptografia cu chei publice. În algoritmul RSA este

utilizată în operaţiile de criptare, decriptare, semnătură electronică şi verificare a semnăturiielectronice. Exemplu operaţie de calcul exponenţial modular: a=be mod n. O modalitate de calcul

constă în efectuarea de e-1 multiplicări modulare, un proces foarte ineficient pentru un exponent e

mare, deoarece algoritmul devine de complexitate exponenţială. Există algoritmi de exponenţiere

rapidă precum algoritmul care face exponenţierea prin prin ridicări la pătrat şi înmulţiri modulare.

3.1. Algoritm de exponenţiere prin ridicări la pătrat şi înmulţiri modulare

Pentru calcularea Z , exponentul este convertit în format binar. Astfel

.

Algoritm 1

Z=X

1. pentru i=n-2 până la 0 execută

2. Z=Z 2 mod M

3. dacă ei=1 atunci Z=Z*X mod M

4. sfârşit instrucţiune repetitivă Acest algoritm se execută în 2(n-1) operaţii în cel mai rău caz şi în 1.5(n-1) operaţii în medie. Pentrua calcula ridicarea la pătrat şi înmulţirea în paralel, se poate utiliza versiunea următoare a algoritmului

(Montgomery, 1985).

Algoritm 2

1. P 0=1, Z 0=X

2. pentru i=0 până la n-1 execută

3. Z i+1=Z i2 mod M

4. dacă ei=1 atunci P i+1=P i*Z i mod M

altfel P i+1=P i

5. sfârşit instrucţiune repetitivă

Acest algoritm se execută în 2*n operaţii în cel mai rău caz şi în 1.5*n operaţii în medie. Viteza

acestuia depinde de viteza execuţiei operaţiei de înmulţire modulară de la punctul 4.

3.2. Algoritmul Montgomery pentru înmulţire modulară

Exponenţierea modulară, conform algoritmilor prezentaţi anterior, se reduce la o serie de înmulţiri

modulare şi ridicări la pătrat. Algoritmul pentru înmulţire modulară a fost propus de P. L.

Montgomery în anul 1985 (Montgomery, 1985). Este o metodă care calculează operaţia de înmulţire

a două numere întregi modulo M, evitând împărţirea la M.

Ideea din spatele algoritmului este transformarea celor două numere întregi în reziduuri ale lui m

şi calcularea înmulţirii cu aceste numere. În final se vor transforma în valoarea corectă.

Pentru a calcula înmulţirea conform algoritmului Montgomery, se alege o valoare rădăcină R>M,cu cmmdc(M,R)=1. Împărţirea la această valoare R trebuie să nu consume multe resurse, astfel,



29

alegerea optima este R=2m dacă presupunem că M= . Reziduul lui m al numărului x este xR

mod M . Se calculează de asemenea M’=-M-1 mod R. Se defineşte o funcţie care RED_M(T) carecalculează TR-1 mod M : Această funcţie calculează reprezentarea corectă a lui T , T fiind un reziduu.

Algoritm 3

RED_M(T) calculează o reducere Montgomery a lui T, T<RM, R=2m , M= , cmmdc(M,R)=1.

1. U=TM’ mod R

2. t=(T+UM)/R

3. dacă t≥M returnează t -M

altfel returnează t Rezultatul funcţiei RED_M (T) este t=TR-1 mod M .

Pentru a înmulţi două numere întregi a şi b în domeniul transformat unde sunt reprezentate ca (aR

mod M ) şi (bR mod M), produsul lor este transmis ca parametru funcţiei RED_M(T) : RED_M((aR mod M)*(bR mod M))=abR2 R-1=abR mod M

Pentru un calcul exponenţial modular se repetă acest pas de mai multe ori, conform algoritmului

de calcul exponenţial modular prin ridicări la pătrat şi înmulţire prezentat anterior.

Pasul iniţial de transformare necesită reducţii modulare consumatoare de resurse. Pentru a evita

operaţia de împărţire, se calculează iniţial R2 mod M folosind operaţia de împărţire. Acest pas trebuie

efectuat o singură dată pentru un sistem de criptare. Pentru a calcula valorile numerelor întregi a şi bîn domeniul transformat se calculează RED_M(aR2 mod M) şi RED_M(bR2 mod M) pentru a obţine aR

mod M şi bR mod M .

Algoritmul următor este o implementare hardware a algoritmului 3. Pentru a executa pasul 2 sunt

necesare un multiplicator pe m x m biţi şi un sumator pe 2m biţi. Rezultatul intermediar poate avea

2m biţi. În loc de a calcula valoarea U direct, se poate calcula la un moment câte o cifră a reprezentării

în rădăcina r . Trebuie ales un număr întreg r ca rădăcină astfel încât cmmdc(M,r)=1. Împărţirea la r

nu trebuie să consume multe resurse, astfel, o alegere optimă ar fi r=2k . O îmbunătăţire a algoritmului

este includerea unui multiplicator A x B în algoritm.

Algoritm 4 Înmulţirea modulară Montgomery pentru calculul AxB mod M , unde M= ,

;

B= ;

A= ;A,B<M; M<R=2km; M’=-M-1 mod 2k ; cmmdc(2k ,M)=1



30

1. S 0= 0

2. pentru i=0 până la m-1 execută

3. qi=(((S i+ai B) mod 2k ) M’) mod 2k

4. S i+1=(S i + qi M+ ai B)/2k

5. sfârşit instrucţiune repetitivă

6. dacă S m≥M returnează S m-M

altfel returnează S m

Rezultatul returnat de acest algoritm este Sm=ABR -1 mod M. Considerând rădăcina r=2k , sunt

necesare cel puţin două înmulţiri pe k x k biţi şi o adunare pe k biţi pentru a executa pasul 3. Pentru

pasul 4 sunt necesare două înmulţiri pe k x m biţi şi două operaţii de adunare pe m+k biţi. Lungimea

maximă pe biţi a lui S este redusă la m+k+2 biţi, comparată cu lungimea de 2m biţi a algoritmului

prezentat anterior.

Algoritmul Montgomery pentru înmulţire cu rădăcina 2

Acest algoritm este o simplificare a algoritmilor anteriori pentru r=2. Pentru rădăcina r=2,

operaţiile de la pasul 3 al algoritmului 4 sunt executate modulo 2. Modulul M trebuie să fie impar,

având în vedere condiţia cmmdc(M, 2k )=1. Deoarece M’=-M -1 mod 2, rezultă că M’=1. Înmulţirea cu

M’ mod 2 din pasul 3 poate fi omisă.

Algoritm 5 Înmulţirea modulară Montgomery ( cu rădăcina r=2) pentru calculul AxB mod M, unde

M= , ;

B= ;

A= ;

A,B<M; M<R=2m; cmmdc(2,M)=1

1. S 0= 0

2. pentru i=0 până la m-1 execută

3. qi=(S i+ai B) mod 2

4. S i+1=(S i + qi M+ ai B)/2

5. sfârşit instrucţiune rpetitivă



31

6. dacă S m≥M returnează S m-M

altfel returnează S m

4. Implementarea algoritmului RSA folosind structuri hardware reconfigurabileUn circuit FPGA (Field Programmable Gate Array) este un circuit integrat care aparţine unei

familii de dispozitive programabile numite PLD – Programmable Logic Devices. Introduse in 1985

de Xilinx, acestea au cunoscut un succes deosebit atât la nivel comercial, cat si la nivel academic,

prin existenţa a numeroase studii, cărţi si conferinţe dedicate in totalitate acestor arhitecturi. Cei mai

populari producători de circuite FPGA sunt Xilinx şi Altera. Aceşti doi producători împart mai mult

de 70% din cota de piaţă a circuitelor FPGA.

Un circuit FPGA este alcătuit dintr -un număr mare de celule logice de bază numite blocurilogice configurabile (CLB- Configurable Logic Blocks). Aceste celule logice sunt distribuite pe toată

suprafaţa cipului. Fiecare celulă este înconjurată de interconexiuni programabile, ansamblul acestor

interconexiuni poartă numele de matrice de conexiuni programabile. Întreg ansamblul de celule şi

interconexiuni se află într -un inel format de blocurile de intrare / ieşire (IOB – Input/Output Blocks).

Blocurile CLB furnizează elementele funcţionale şi realizează structura logică proiectată. Blocurile

IOB furnizează interfaţa între semnalele interne şi exteriorul circuitului (legătura realizată fizic prin

intermediul pinilor).

FPGA-urile sunt utilizate pentru calcul reconfigurabil atunci când obiectivul principal este

obţinerea unei performanţe ridicate la un cost rezonabil prin implementare hardware a algoritmilor.Principalul avantaj al FPGA este reconfigurabilitatea lor, putând fi utilizate pentru diferite scopuri în

diferite stadii ale procesului de calcul şi pot fi, cel puţin parţial, reprogramate la run-time.

În afară de criptografie, aplicaţii ale circuitelor FPGA se regăsesc în domenii precum

procesarea de semnale digitale, sisteme în timp real, realizarea de prototipuri rapide pentru circuite

ASIC, procesoare de reţea, grafică pe calculator, robotică, aplicaţii embedded,etc. În general, FPGA-

urile tind să fie o alegere excelentă atunci când se doreşte implementarea unor algoritmi care pot

beneficia de paralelismul mare oferit de arhitectura FPGA.

Utilizarea FPGA pentru aplicaţii criptografice este extrem de atractivă pentru o varietate de

motive, dar, în acelaşi timp, există multe aspecte deschise legate de securitatea generală a circuitelorFPGA. Alegerea platformei de implementare a unui sistem digital este determinată de mai multe

criterii şi depinde în mare măsură de zona de aplicare. În aplicaţii criptografice există multe criterii

care sunt unice pentru contextul de securitate în care sunt utilizate. În plus faţă de aspectele legate de

algoritm, de viteza sistemului şi de costuri - care sunt prezente în cele mai multe alte domenii de

aplicare – se adaugă cele cripto-specific: securitatea fizică (de exemplu, împotriva recuperării cheilor

şi modificării algoritmului), flexibilitatea (în ceea ce priveşte parametrii algoritmului, cheile, chiar

algoritmul în sine), consumul de energie (utilizarea absolută şi prevenirea atacurilor prin analiză de

putere) şi alte scurgeri side chanel.

Avantajele implementărilor software includ utilizarea relativ simplă a mediilor de dezvoltare, posibilitatea de îmbunătăţire rapidă a implementării, portabilitatea, costurile de dezvoltare reduse,



32

preţurile unitare mici şi flexibilitatea. Pe de altă parte, o implementare software oferă o viteză

moderată, consum mare de putere comparativ cu hardware-ul personalizat, securitatea fizică limitată,

în special în ceea ce priveşte depozitarea cheilor. Implementările hardware asigură un preţ mai redus

pe unitate, ating viteze mari şi pot avea disipări reduse de energie. În plus, implementările hardwareale algoritmilor cri ptografici sunt mai sigure deoarece acestea nu pot fi la fel de uşor de citit sau

modificat de un atacator extern ca implementările software.

Fig. 1 Capsula modulului criptografic

Mesaj [1023 downto 0]

Exponent [1023 downto 0]

Modul [1023 downto 0]

Output [1023 downto 0]

Reset

Start

CLK

Finish

Sursa: Prelucrarea autorului

Folosind noţiunile teoretice şi algoritmii descrişi în capitolele anterioare, s-a realizat

implementarea folosind limbajul VHDL (Verilog Hardware Description Language) a unui modul de

criptare şi decriptare a unui mesaj folosind algoritmul RSA. S-au studiat implementări anterioare

(Perovic, 2012, Wang1997, Zutter, 2009) care prezintă arhitecturi ale algoritmului RSA care doresc

utilizarea eficientă a structurilor reconfigurabile (Iana, 2011), utilizarea unui algoritm eficientizat

pentru exponenţiere modulară (Khalil Hani, 2000) sau implementarea unei arhitecturi seriale a

algoritmului RSA(Mazzeo, 2003).

Acest modul are ca intrări exponentul cu lungimea de 1024 de biţi, modulul cu lungimea de

1024 de biţi şi mesajul cu lungimea de 1024 de biţi. Modulul returnează la ieşire mesajul criptat sau

decriptat (Fig. 1).

Operaţia exponenţială modulară: a=be mod n necesară atât în procesul de criptare cât şi în

procesul de decriptare al algoritmului RSA este calculată folosind algoritmul de exponenţiere prin

ridicări la pătrat şi înmulţiri modulare (Algoritmul 1 prezentat în capitolul anterior).



33

Fig. 2 Schema bloc a implementării algoritmului RSA

Sursa: Prelucrarea autorului

Pentru calculul operaţiilor de înmulţire modulară s-a implementat algoritmul Montgomery

prezentat în capitolul anterior (Algoritmul 4). Au fost implementate de asemenea circuite

multiplicatoare şi sumatoare.

5.

ConcluziiŢările dezvoltate dar şi ţările în curs de dezvoltare profită de avantajele şi oportunităţile oferite

în economie de tehnologia informaţiilor. Luând în considerare impactul tehnologiei informaţiilor

asupra economiei există cerinţe permanente de a asigura în mod eficient protecţia informaţiilor şi a

proceselor de comunicaţie împotriva riscurilor ameninţărilor de securitate. Nevoia de servicii

criptografice este din ce în ce mai ridicată, criptografia fiind componenta fundamentală care asigură

securitatea informaţiilor în mediul virtual.

Această lucrare este un studiu al implementării algoritmului criptografic RSA folosind

structuri hardware reconfigurabile. S-a implementat o arhitectură eficientă a acestui algoritm

utilizând în modelul propus algoritmi care eficientizează operaţiile matematice costisitoare din procesele de criptare şi decriptare precum exponenţierea modulară şi înmulţirea modulară. S-a utilizat

de asemenea o platformă FPGA care oferă flexibilitatea implementărilor software şi performanţa

implementărilor hardware.

În prima parte s-a prezentat algoritmul RSA şi paşii care trebuie urmaţi pentru generarea celor

două perechi de chei, operaţia de criptare, operaţia de decriptare, operaţia de semnare digitală şi

operaţia de verificare a semnăturii digitale.

Sunt descrişi algoritmi care eficientizează calculul operaţiilor executate în criptarea şi

decriptarea algoritmului RSA. Astfel, pentru exponenţierea modulară este prezentat algoritmul de

ridicare la pătrat şi înmulţire. Pentru calculul operaţiilor de înmulţire modulară, sunt prezentatevariante ale algoritmului Montgomery.

Z=XE mod M

X

E

M

Z

Algoritm ridicare la pătrat și înmulțire pentru calcul

exponențial modular

R=AxB mod M

A

Algoritmul Montgomery

pentru înmulțire

modulară

B R

R1=A1+B1

Sumator

R2=A2*B2

Multiplicator

A1

B1

R1

A2

B2

R2



34

Aceşti algoritmi au fost implementaţi în limbajul VHDL într -un modul criptografic care

criptează şi decriptează mesaje folosind algoritmul RSA.

Un obiectiv al cercetărilor viitoare îl reprezintă implementarea operaţiilor de semnare digitală

şi verificare a semnăturii digitale. Pentru generarea celor două perechi de chei ale algoritmului RSAse vor studia şi implementa algoritmi pentru generarea unor numere aleatoare şi pentru verificarea

numerelor prime.

Dezvoltarea unor aplicaţii optimizate ale algoritmului RSA presupune studierea şi

aprofundarea algoritmilor care eficientizează operaţiile matematice utilizate în criptare sau decriptare.

Bibliografie

1. Iana, G.V. (2011) - RSA encryption algorithm implemented on FPGA, International Conference onApplied Electronics (AE), pp. 1 - 4

2.

Khalil Hani, M. (2000) - FPGA implementation of RSA public-key cryptographic coprocessor ,TENCON 2000. Proceedings, vol. 3, pp. 6 – 11

3. Mazzeo, A. (2003) - FPGA-based implementation of a serial RSA processor , Design, Automation andTest in Europe Conference and Exhibition, pp. 582 – 587

4. Montgomery, P.L. (1985) - Modular multiplication without trial division. Mathematics ofComputation, vol. 44, No 170, pp. 519 – 521

5. NIST (2005) - Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.46. NIST (2012) - Special Publication 800-90A Recommendation for Random Number Generation Using

Deterministic Random Bit Generators 7. Perovic, N.S. (2012) - FPGA implementation of RSA cryptoalgorithm using shift and carry algorithm,

20thTelecommunications Forum (TELFOR), pp. 1040 - 10438. Wang, P.A. (1997) - New VLSI architectures of RSA public key cryptosystems, Proceedings of 1997

IEEE International Symposium on Circuits and Systems, vol. 3, pp 2040 – 20439. Zutter, J. (2009) - Acceleration of RSA Cryptographic Operations Using FPGA Technology, 20th

International Workshop on Database and Expert Systems Application, pp. 20 - 25

Acknowledgements

Această lucrare a fost realizată cu sprijinul finanţării obţinute în cadrul proiectului de studii

doctorale şi postdoctorale: „Studii doctorale şi postdoctorale Orizont 2020: promovarea

interesului naţional prin excelenţă, competitivitate şi responsabilitate în cercetarea ştiinţifică

fundamentală şi aplicată românească” Contract POSDRU/159/1.5/S/140106. Proiectul este

cofinanţat din Fondul Social European prin Programul Operaţional Sectorial Dezvoltarea

Resurselor Umane 2007-2013. Investeşte în Oameni!

Nicolcioiu A.pdf

Documents

Transcript of Nicolcioiu A.pdf