Algoritm RSA | algoritm usted pentru criptarea și decriptarea mesajelor

Concepte utilizate

RSA utilizează o serie de concepte din domeniul criptografiei:

• O funcție unidirecțională care este ușor de calculat; găsirea unei funcții care să o inverseze sau calcularea acestei funcții este foarte dificilă.
• RSA utilizează un concept numit logaritm discret. Acesta funcționează la fel ca logaritmul normal: Diferența constă în faptul că se folosesc numai numere întregi și, în general, este implicată o operație de modul. De exemplu, a^x =b, modulo n. Logaritmul discret constă în găsirea celui mai mic x care satisface ecuația, atunci când sunt furnizate a b și n
• Acesta este potențial contracarat de algoritmul lui Shor.

 

Generarea cheilor

Cheile pentru algoritmul RSA sunt generate în felul următor:

1. Alegeți două numere prime aleatoare mari și diferite p {\displaystyle p} și q {\displaystyle q} . Acest lucru trebuie păstrat secret.
2. Calculați n = p q {\displaystyle n=pq} .
• n {\displaystyle n} este modulul pentru cheia publică și cheile private.
3. Calculați totientul: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
4. Alegeți un număr întreg e { {\displaystyle e} astfel încât 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} , iar e {\displaystyle e} este co-primă cu ϕ ( n ) {\displaystyle \phi (n)} .
   adică: e {\displaystyle e} și ϕ ( n ) {\displaystyle \phi (n)} nu au în comun alți factori decât 1 {\displaystyle 1}. : gcd ( e , ϕ ( n ) ) = 1 {\displaystyle \gcd(e,\phi (n))=1} ; A se vedea cel mai mare divizor comun.
• e {\displaystyle e} este lansat ca exponent al cheii publice.
5. Calculați d {\displaystyle d} pentru a satisface relația de congruență d e ≡ 1 ( mod ϕ ( n ) ) {\displaystyle de\equiv 1\!\!\!\!\!\!\pmod {\phi (n)}}} .
   adică: d e = 1 + x ⋅ ϕ ( n ) {\displaystyle de=1+x\cdot \phi (n)} pentru un număr întreg x {\displaystyle x} . (Pur și simplu să spunem: Se calculează d = ( 1 + x ⋅ ϕ ( n ) ) / e {\displaystyle d=(1+x\cdot \phi (n))/e} pentru a fi un număr întreg)
• d {\displaystyle d} este păstrat ca exponent al cheii private.

Observații privind etapele de mai sus:

• Pasul 1: Numerele pot fi testate probabilistic pentru primalitate.
• Pasul 3: modificat în PKCS#1 v2.0 în λ ( n ) = l c m ( p - 1 , q - 1 ) {\displaystyle \lambda (n)={\rm {lcm}}(p-1,q-1)} în loc de ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
• Pasul 4: O alegere populară pentru exponenții publici este e = 2 16 + 1 = 65537 {\displaystyle e=2^{16}+1=65537} . Unele aplicații aleg valori mai mici, cum ar fi e = 3 {\displaystyle e=3}. , 5 {\displaystyle 5} sau 35 {\displaystyle 35} . Acest lucru se face pentru ca criptarea și verificarea semnăturilor să fie mai rapide pe dispozitive mici, cum ar fi cardurile inteligente, dar exponenții publici mici pot duce la riscuri de securitate mai mari.
• Etapele 4 și 5 pot fi realizate cu algoritmul Euclidian extins [en]; a se vedea aritmetica modulară.

 Cheia publică
este formată din modulul n {\displaystyle n\,} și exponentul public (sau de criptare) e {\displaystyle e\,} . Cheia personală
este formată din p,q și exponentul privat (sau de decriptare) d {\displaystyle d\} , care trebuie păstrat secret.

• Pentru eficiență, se poate stoca o formă diferită a cheii private:
• p {\displaystyle p} și q {\displaystyle q} : numerele prime de la generarea cheii;
• d mod ( p - 1 ) {\displaystyle d{\bmod {(}}p-1)} și d mod ( q - 1 ) {\displaystyle d{\bmod {(}}q-1)} : adesea numite dmp1 și dmq1;
• q - 1 mod p {\displaystyle q^{-1}{\bmod {p}}} : adesea numit iqmp.
• Toate părțile cheii private trebuie să fie păstrate secrete în această formă. p {\displaystyle p\,} și q {\displaystyle q\,} sunt sensibile, deoarece sunt factorii lui n {\displaystyle n\,} și permit calcularea lui d {\displaystyle d\,} dat fiind e {\displaystyle e\,} . În cazul în care p {\displaystyle p\,} și q {\displaystyle q\,} nu sunt stocate în această formă a cheii private, atunci acestea sunt șterse în siguranță împreună cu alte valori intermediare de la generarea cheii.
• Deși această formă permite decriptarea și semnarea mai rapidă prin utilizarea teoremei chinezești a restului (CRT), este considerabil mai puțin sigură, deoarece permite atacuri prin canal lateral [en]. Aceasta este o problemă deosebită dacă este implementată pe carduri inteligente, care beneficiază cel mai mult de eficiența îmbunătățită. 
  (Începeți cu y ≡ x e ( mod n ) {\displaystyle y\equiv x^{e}\!\!\!\!\!\!{\pmod {n}}}}. și lăsați cardul să decripteze asta. Deci, calculează ( y d mod p ) {\displaystyle (y^{d}{\bmod {p}})} sau ( y d mod q ) {\displaystyle (y^{d}{\bmod {q}})} , ale căror rezultate dau o anumită valoare z {\displaystyle z} . Acum, induceți o eroare în unul dintre calcule. Atunci gcd ( z - x , n ) {\displaystyle \gcd(z-x,n)} va dezvălui p {\displaystyle p} sau q {\displaystyle q} ).

 

Criptarea mesajului

Alice îi dă cheia sa publică ( n , e ) {\displaystyle (n,e)} lui Bob și își păstrează secretă cheia privată. Bob dorește să trimită mesajul M {\displaystyle M} către Alice.

În primul rând, el transformă M {\displaystyle M} într-un număr m {\displaystyle m} mai mic decât n {\displaystyle n} prin utilizarea unui protocol reversibil convenit, cunoscut sub numele de schemă de umplere. El calculează apoi textul cifrat c {\displaystyle c\,} care corespunde:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}}

Acest lucru se poate face rapid folosind metoda exponențializării prin ridicarea la pătrat. Bob trimite apoi c {\displaystyle c\,} către Alice.

 

Decriptarea mesajului

Alice poate recupera m {\displaystyle m\,} de la c {\displaystyle c\,} folosind cheia sa privată d {\displaystyle d\,} în următoarea procedură:

Dat fiind m {\displaystyle m\,} , ea poate recupera numerele prime distincte originale, aplicând teorema restului chinezesc la aceste două congruențe rezultă

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Astfel,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Prin urmare:

m = c d m o d n {\displaystyle m=c^{d}\ mod\ n}

Un exemplu de lucru

Iată un exemplu de criptare și decriptare RSA. Numerele prime utilizate aici sunt prea mici pentru a ne permite să criptăm ceva în siguranță. Puteți utiliza OpenSSL pentru a genera și examina o pereche de chei reală.

1. Alegeți două numere prime aleatoare p {\displaystyle p} și q {\displaystyle q\,} :

p = 61 {\displaystyle p=61} și q = 53 {\displaystyle q=53\,} ;

2. Calculați n = p q {\displaystyle n=pq\,} :

n = 61 × 53 = 3233 {\displaystyle n=61\ ori 53=3233\!} ;

3. Calculați totienul ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} :

ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120\!} ;

4. Alegeți e > 1 {\displaystyle e>1} coprimă cu 3120 {\displaystyle 3120\,} :

e = 17 {\displaystyle e=17\,} ;

5. Alegeți d {\displaystyle d\,} pentru a satisface e d ≡ 1 mod ϕ ( n ) {\displaystyle ed\equiv 1{\bmod {\phi (n)}}} :

d = 2753 {\displaystyle d=2753\,} , cu 17 × 2753 = 46801 = 1 + 15 × 3120 {\displaystyle 17\times 2753=46801=1+15\times 3120} .

 Cheia publică este ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Pentru un mesaj umplut m {\displaystyle m\,} funcția de criptare c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}}} devine:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}}233\,}

Cheia privată este ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Funcția de decriptare m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} devine:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}}233\},}

 De exemplu, pentru a cripta m = 123 {\displaystyle m=123} , se calculează

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}}233=855}}

Pentru a decripta c = 855 {\displaystyle c=855} , se calculează

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}}233=123}

Ambele calcule pot fi efectuate rapid și ușor cu ajutorul algoritmului pătrat și înmulțire pentru exponențierea modulară.

 

Derivarea ecuației RSA din teorema lui Euler

RSA poate fi ușor de derivat folosind teorema lui Euler și funcția de totizare a lui Euler.

Începând cu teorema lui Euler,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}}

trebuie să arătăm că decriptarea unui mesaj criptat, cu ajutorul cheii corecte, va da mesajul original. Dat fiind un mesaj umplut m, textul cifrat c se calculează astfel

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}}

Înlocuind în algoritmul de decriptare, avem

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}}}

Vrem să arătăm că această valoare este, de asemenea, congruentă cu m. Valorile lui e și d au fost alese pentru a satisface,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

Adică, există un număr întreg k, astfel încât

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\ ori \phi (n)+1}

Acum înlocuim mesajul criptat și apoi decriptat,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{k\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}}

Aplicăm teorema lui Euler și obținem rezultatul.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}}

 

Scheme de umplere

Atunci când este utilizat în practică, RSA trebuie combinat cu o anumită formă de schemă de umplere, astfel încât nicio valoare a lui M să nu conducă la texte cifrate nesigure. RSA utilizat fără padding poate avea unele probleme:

• Valorile m = 0 sau m = 1 produc întotdeauna texte cifrate egale cu 0 sau, respectiv, 1, datorită proprietăților exponențializării.
• Atunci când se criptează cu exponenți de criptare mici (de exemplu, e = 3) și valori mici ale lui m, rezultatul (nemodular) al lui m e {\displaystyle m^{e}} poate fi strict mai mic decât modulul n. În acest caz, textele cifrate pot fi decriptate cu ușurință prin luarea rădăcinii etice a textului cifrat, fără a se ține seama de modul.
• Criptarea RSA este un algoritm de criptare determinist. Acesta nu are nicio componentă aleatorie. Prin urmare, un atacator poate lansa cu succes un atac de tip "chosen plaintext" împotriva criptosistemului. Acesta poate crea un dicționar prin criptarea unor plajexuri probabile sub cheia publică și stocarea textelor cifrate rezultate. Atacatorul poate apoi să observe canalul de comunicare. De îndată ce vede textele cifrate care se potrivesc cu cele din dicționarul lor, atacatorii pot folosi acest dicționar pentru a afla conținutul mesajului.

În practică, primele două probleme pot apărea atunci când se trimit mesaje ASCII scurte. În astfel de mesaje, m poate fi concatenarea unuia sau mai multor caractere codate ASCII. Un mesaj format dintr-un singur caracter ASCII NUL (a cărui valoare numerică este 0) ar fi codificat ca m = 0, ceea ce produce un text cifrat de 0, indiferent de valorile lui e și N utilizate. De asemenea, un singur caracter ASCII SOH (a cărui valoare numerică este 1) ar produce întotdeauna un text cifrat de 1. Pentru sistemele care utilizează în mod convențional valori mici ale lui e, cum ar fi 3, toate mesajele cu un singur caracter ASCII codificate folosind această schemă ar fi nesigure, deoarece cel mai mare m ar avea o valoare de 255, iar 255³ este mai mic decât orice modul rezonabil. Astfel de texte în clar ar putea fi recuperate prin simpla extragere a rădăcinii cubice a textului cifrat.

Pentru a evita aceste probleme, implementările practice RSA integrează de obicei o formă de umplutură structurată și aleatorie în valoarea m înainte de a o cripta. Această umplutură garantează că m nu se încadrează în intervalul de plagiate nesigure și că un anumit mesaj, odată umplut, va fi criptat într-unul dintre numeroasele texte cifrate posibile. Această din urmă proprietate poate crește costul unui atac prin dicționar dincolo de capacitățile unui atacator rezonabil.

Standarde precum PKCS au fost concepute cu atenție pentru a proteja mesajele înainte de criptarea RSA. Deoarece aceste sisteme umplu textul clar m cu un anumit număr de biți suplimentari, dimensiunea mesajului M neumplut trebuie să fie ceva mai mică. Schemele de umplere RSA trebuie să fie proiectate cu atenție pentru a preveni atacurile sofisticate. Acest lucru poate fi facilitat de o structură previzibilă a mesajului. Primele versiuni ale standardului PKCS foloseau construcții ad-hoc, care s-au dovedit ulterior vulnerabile la un atac practic de tip adaptive chosen ciphertext. Construcțiile moderne utilizează tehnici sigure, cum ar fi OAEP (Optimal asymmetric encryption padding), pentru a proteja mesajele, prevenind în același timp aceste atacuri. Standardul PKCS are, de asemenea, scheme de procesare concepute pentru a oferi o securitate suplimentară pentru semnăturile RSA, de exemplu, schema de semnătură probabilistică pentru RSA (RSA-PSS).

 

Semnarea mesajelor

Să presupunem că Alice utilizează cheia publică a lui Bob pentru a-i trimite un mesaj criptat. În mesaj, ea poate pretinde că este Alice, dar Bob nu are nicio modalitate de a verifica dacă mesajul provine într-adevăr de la Alice, deoarece oricine poate folosi cheia publică a lui Bob pentru a-i trimite mesaje criptate. Așadar, pentru a verifica originea unui mesaj, RSA poate fi folosit și pentru a semna un mesaj.

Să presupunem că Alice dorește să trimită un mesaj semnat lui Bob. Ea produce o valoare hash a mesajului, o ridică la puterea lui d mod n (la fel ca atunci când decriptează un mesaj) și o atașează ca "semnătură" la mesaj. Când Bob primește mesajul semnat, el ridică semnătura la puterea lui e mod n (la fel ca la criptarea unui mesaj) și compară valoarea hash rezultată cu valoarea hash reală a mesajului. Dacă cele două corespund, Bob știe că autorul mesajului a fost în posesia cheii secrete a lui Alice și că mesajul nu a fost modificat de atunci.

Rețineți că schemele de umplere securizată, cum ar fi RSA-PSS, sunt la fel de esențiale pentru securitatea semnării mesajelor ca și pentru criptarea mesajelor și că nu trebuie folosită niciodată aceeași cheie atât pentru criptare, cât și pentru semnare.