Algoritmul RSA

Denumirea de algoritm RSA provine de la initialele numelor inventatorilor sai,Ron Rivest, Adi Shamir si Len Adleman.Algoritmul RSA poate fi folosit atat pentru criptare cu cheie publica cat si pentru semantura digitala. Securitatea algoritmului se bazeaza pe dificultatea de a descompune numere intregi mari in factori primi.

Continut

•Algoritm de generare a cheilor•Criptare•Decriptare•Semnatura digitala•Verificarea semnaturii•Observatii si aplicatii practice•Un exemplu de criptare RSA• Implementarea Java

Algoritm de generare a cheilor

1.Se genereaza doua numere prime mari ( la intamplare) , p si q, de lungimi aproximativ egale astfel incat produsul lor este de lungimea ceruta (ex. 1024 biti).(obs 1)2.Se calculeaza n=p*q is ?=(p-1)*(q-1).3.Se alege un numar intreg e (1<e<?) astfel incat cmmdc(e, ?)=1.(obs 2)4.Se afla exponentul secret d, 1<d<?, astfel incat (e*d)? 1 (mod ?).(obs 3)5.Cheia publica este perechea (n,e) ,iar cheia privata perechea (n,d). Valorile lui p, q, ? trebuie de asemenea pastrate secrete.

• e este cunoscut si sub denumirea de exponent public (exponent de criptare) , iar d sub numele de exponent secret (exponent de decriptare).

Criptarea

Expeditorul A face urmatoarele lucruri:

1.Obtine cheia publica (n,e) a destinatarului B.2.Reprezinta mesajul ca un numar pozitiv m.3.”Compune” textul criptat c=m^e mod n.4.Ii trimite textul c lui B.

Decriptare

Destinatarul B face urmatoarele lucruri:

1.Foloseste cheia privata (n,d) pentru a calcula m=c^d mod n.2.”Extrage” textul original din numarul reprezentativ m.

Semnarea digitala

Expeditorul A face urmatoarele lucruri:

1.Creeaza un mesaj corespunzator informatiei care va fi trimisa.2.Il reprezinta pe acesta ca un numar intreg m cuprins intre 0 si n-1.3.Foloseste cheia privata (n,d) pentru a calcula semnatura s=m^d mod n.4.Trimite aceasta semnatura s destinatarului B.

Verificarea semnaturii

Destinatarul B face urmatoarele lucruri:

1.Utilizeaza cheia publica (n,e) a expeditorului A pentru a calcula numarul intreg v=s^e mod n.2.Extrage mesajul din acest intreg.3.Independent “calculeaza” mesajul corespunzator al informatiei care a fost semnat.4.Daca sunt identice, inseamna ca semnatura este valida.

Observatii si aplicatii practice

1.Pentru a genera numerele prime p si q se genereaza un numar cu b/2 biti unde b este numarul de biti ai lui n; se seteaza bitul cel mai putin semnificativ (asigura faptul ca numarul este impar) si cei mai semnificativi doi biti (inseamna ca si bitul cel mai semnificativ al lui n este setat); se verifica daca este prim; daca nu se creste numarul cu doi si se verifica din nou.Acesta va fi p.Se repeta si pentru q pornind cu un intreg de lungime b-b/2.2.In practica alegeri comune pentru e sunt 3,17,65537(2^16+1).Acestea sunt numere prime Fermat si sunt alese pentru ca produc exponentierea modulara mai rapid. 3.Pentru a calcula valoarea lui d se foloseste algoritmul euclidian extins (d=e^-1 mod f).

• Algoritmul RSA

1.Se aleg la intamplare doua numere prime mari de aproximativ aceeasi dimensiune.2.Se calculeaza produsul n=p*q (inmultire obisnuita de numere intregi).3.Se alege un exponent de criptare e la intamplare mai mic decat n care nu are factor comun nici cu p-1 si nici cu q-1(e si (p-1)*(q-1) sunt relativ prime).4.Se calculeaza exponentul de decriptare (unic) care satisface urmatoarea conditie e*d mod (p-1)*(q-1)=1.5.Functia de criptare este E(m)=me mod n, pentru orice mesaj m.6.Functia de decriptare este D(c)=cd mod n, pentru orice text cifrat c.7.Cheia publica (facuta publica) este perechea de intregi (n,e).8.Cheia privata (pastrata secreta) este tripletul de intregi (p,q,d).

Cateva indicatii pentru “regulile” prezentate anterior:

1.In present, “mare” inseamna cel putin 512 de biti.Pentru o mai mare securitate fiecare numar prim ar trebui sa fie de cel putin 1024 biti.2.n este de lungime cel putin 1024 sau 2048 biti.3.Exponentul de criptare e poate fi doar 3.Daca cineva foloseste acest exponent, atunci numerele prime trebuie alese astfel incat p-1 si q-1 sa nu fie divizibile cu 3.

Pentru a arata ca decriptarea RSA “intoarece” ceea ce RSA a criptat, trebuie aratat doar faptul ca D(E(m))=m pentru orice mesaj m sau ca (me)d mod n=m.Dar e*d mod (p-1)*(q-1)=1, deci (me)d mod n=(med mod n=med mod(p-1)*(q-1) mod n= m1 mod n=m.Implementarea Java a algoritmului RSA uilizeaza clasa BigInteger care contine toate metodele care sunt necesare implementarii algoritmului fara dificultate.

Un simplu exemplu de criptare RSA

1.Se selecteaza numerele prime p=11, q=32. n = pq = 11*3 = 33f = (p-1)*(q-1) = 10*2 = 20 1. Se alege e=3Se verifica daca cmmdc(e, p-1) = cmmdc(3, 10) = 1 (adica 3 si 10 nu au alt divizor comun in afara de 1),si se verifica daca cmmdc(e, q-1) = cmmdc(3, 2) = 1astfel cmmdc(e, f) = cmmdc(e, (p-1)(q-1)) = cmmdc(3, 20) = 1 2. Se calculeaza d astfel incat ed = 1 (mod f)d = e^-1 mod f = 3^-1 mod 20 adica se gaseste o valoare pentru d astfel incat f este divizibli cu (ed-1) adica 20 este divizibil cu 3d-1.O simpla testare (d = 1, 2, ...) si-l obtinem pe d: d = 7Se verifica: ed-1 = 3*7 - 1 = 20, care este divizibil cu f. 3. Cheia publica= (n, e) = (33, 3)Cheia privata = (n, d) = (33, 7). Acesta este de fapt cea mai mica valoare a lui n pentru care funcitoneaza algoritmul RSA. Sa zicem ca vrem sa criptam mesajul m=7,c = m^e mod n = 7^3 mod 33 =343 mod 33 = 13.Deci textul cifrat este c = 13. Pentru a verifica decriptarea calculam m' = c^d mod n = 13^7 mod 33 = 7. Observam ca nu trebuie sa calculam valoarea lui 13 la puterea a 7-a. Ne putem folosi de faptul ca a=bc mod n=(b mod n)*(c mod n) mod n asa ca putem descompune un numer mare in componente si sa combinam rezultatul facand calcule mai simple pentru a afla valoarea finala. 

O modalitate de a calcula m' este urmatorul:-m' = 13^7 mod 33 = 13^(3+3+1) mod 33 = 13^3*13^3 13 mod 33= (13^3 mod 33)*(13^3 mod 33)*(13 mod 33) mod 33= (2197 mod 33)*(2197 mod 33)*(13 mod 33) mod 33= 19*19*13 mod 33 = 4693 mod 33= 7. Acum daca calculam textul cifrat cpentru toate valorile posibile ale lui m (0 ..32), obtinem m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4

m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32

Implementarea Java