RSA (criptare)

RSA
General
Designeri	Ronald Rivest , Adi Shamir , Leonard Adleman
Prima publicație	1977
Detalii
Dimensiunea cheii	De obicei 1024 biți până la 4096 biți (se recomandă cel puțin 2048 biți)
Criptanaliză mai bună
Cernere de câmpuri de număr general pentru computer clasic. Algoritm de factorizare Shor pentru calculatoare cuantice .
Editați datele pe Wikidata · Manual

În criptografie, acronimul RSA indică un algoritm de criptare asimetrică , inventat în 1977 de Ronald Rivest , Adi Shamir și Leonard Adleman, care poate fi folosit pentru a cripta sau semna informații.

În 1976, Whitfield Diffie și Martin Hellman , criptologi americani, au fost primii care au publicat un sistem bazat pe crearea unui cifru „asimetric” compus din „chei publice”; deși James H. Ellis , Clifford Cocks și Malcolm J. Williamson din serviciile secrete britanice s-au gândit deja la asta cu câțiva ani mai devreme, știrea a fost acoperită de secretul militar și a fost dezvăluită abia în 1997. ^[1]

Sistemul de criptare se bazează pe existența a două chei distincte, care sunt utilizate pentru a cripta și decripta. Dacă prima cheie este utilizată pentru criptare, a doua trebuie utilizată în mod necesar pentru decriptare și invers. Problema fundamentală este că, deși cele două chei sunt dependente una de cealaltă, nu este posibilă urmărirea de la una la alta, astfel încât, chiar dacă unul este conștient de una dintre cele două chei, nu este posibil să se urmărească cealaltă , garantând acest lucru asigură integritatea criptării.

Pentru a obține o bună securitate este necesar să utilizați chei binare de cel puțin 2048 biți. Cele de 512 biți pot fi obținute în câteva ore. Tastele de 1024 biți, încă utilizate pe scară largă astăzi, nu mai sunt recomandate. ^[2] Factorizarea numerelor întregi mari, de fapt, a progresat rapid prin utilizarea de hardware sofisticat, până la punctul în care ar putea fi posibil să se factorizeze un număr întreg de 1024 de biți într-un singur an, la un cost de un milion de dolari ( un cost durabil pentru orice organizație mare, agenție sau informații). ^[3] ^[4]

( EN ) "Sper că aplicațiile RSA s-ar fi îndepărtat de securitatea de 1024 de biți în urmă, dar pentru cei care nu au făcut încă: trezește-te".	( IT ) "Sper că aplicațiile RSA au abandonat cheile de 1024 biți de ani de zile, dar pentru cei care nu au, treziți-vă!"
( Bruce Schneier , sbsuneebxu 21 mai 2007 )

Descriere

Luând un exemplu practic, dacă Alice dorește să îi trimită un mesaj lui Bob și nu dorește ca altcineva decât Bob să-l citească, Alice va căuta cheia publică a lui Bob pe listă și cu aceasta poate cripta mesajul. Deoarece Bob este singurul care are cheia privată (prin urmare capabil să decripteze mesajul criptat cu cheia publică), el va fi și singurul care poate decripta mesajul, care va rămâne atât de secret pentru toți ceilalți, inclusiv pentru Alice, care, de vreme ce nu are cheia privată a lui Bob, nu va putea decripta singură mesajul pe care l-a creat. Evident, succesul acestui sistem se bazează pe necesitatea absolută ca Bob să fie singurul care deține cheia sa privată. În caz contrar, având ambele chei, oricine ar putea decripta cu ușurință mesajul.

Cu această metodă de criptare este, de asemenea, posibil să se garanteze originea unui mesaj. Să ne întoarcem la exemplul anterior: Alice de data aceasta, înainte de a cripta mesajul folosind cheia publică a lui Bob, îl va cripta folosind propria cheie privată și abia ulterior o va recifra folosind cheia publică a lui Bob. Când Bob primește mesajul și îl decriptează folosind cheia sa inversă, va primi totuși un mesaj criptat. Acest mesaj dat va avea nevoie apoi de decriptarea cheii publice a lui Alice, asigurându-se astfel că mesajul a fost trimis doar de Alice, singura care are cheia privată cu care a fost criptat mesajul.

Mai simplu, folosind această metodă de criptare, Alice poate trimite mesaje tuturor, garantând originea. De fapt, prin criptarea mesajului cu cheia lor privată, oricine va putea citi mesajul, decriptându-l cu cheia publică, asigurându-se astfel că expeditorul este Alice.

Implementare prin algoritm RSA

În 1978, acest sistem și-a găsit aplicația reală, când cei trei cercetători MIT Ronald Rivest , Adi Shamir și Leonard Adleman au reușit să implementeze această logică folosind proprietăți formale particulare ale numerelor prime cu câteva sute de cifre. Algoritmul pe care l-au inventat, numit RSA din inițialele numelor lor de familie, nu este sigur din punct de vedere teoretic matematic, deoarece există posibilitatea ca prin cunoașterea cheii publice să poată fi descifrat un mesaj; dar cantitatea enormă de calcule și cheltuielile enorme în termeni de timp necesare pentru a găsi soluția fac din acest algoritm un sistem de fiabilitate aproape absolută.

Ronald Rivest , Adi Shamir și Leonard Adleman în 1983 au brevetat algoritmul din Statele Unite de la MIT (brevetul 4.405.829, expirat la 21 septembrie 2000 ); au creat și compania RSA Data Security , protejându-și astfel interesele comerciale. Security Dynamics a achiziționat ulterior compania și a vândut utilizarea algoritmilor unor companii precum Netscape , Microsoft și altele. O variantă a sistemului RSA este utilizată în suita de cifrare Pretty Good Privacy (PGP). Algoritmul RSA constituie baza sistemelor criptografice pe care se bazează sistemele de securitate a computerului utilizate pe internet pentru autentificarea utilizatorilor.

Clifford Cocks , un matematician britanic care lucra pentru un departament de spionaj, GCHQ , a descris un sistem echivalent într-un document intern în 1973 . Documentele au fost ținute sub acoperire și, având în vedere costul relativ ridicat al mașinilor necesare pentru a-l implementa la momentul respectiv, nu au mai existat alte investigații sau teste practice și acest lucru a fost considerat o curiozitate din câte se știe. Descoperirea cocoșilor a fost făcută publică abia în 1997 .

În 2005, o echipă de cercetători a reușit să descompună un număr de 640 de biți (193 zecimale) în două primare de 320 de biți, utilizând un cluster Opteron cu 80 de procesoare de 2,2 GHz timp de cinci luni, decriptând potențial un mesaj codat RSA.

RSA este solicitant din punct de vedere al calculului, mai ales în ceea ce privește o posibilă implementare hardware. În consecință, o utilizare eficientă este de a utiliza RSA pentru a cripta un singur mesaj care conține o cheie secretă; această cheie va fi apoi utilizată pentru schimbul de mesaje printr-un algoritm de cheie simetric, cum ar fi AES .

Astăzi, împreună cu DSA , RSA este unul dintre cei mai utilizați algoritmi pentru criptarea semnăturilor digitale .

Operațiuni

RSA se bazează pe complexitatea de calcul ridicată a factorizării prime . Funcționarea sa de bază este următoarea:

două numere prime sunt alese la întâmplare, $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ suficient de mare pentru a asigura securitatea algoritmului (de exemplu, cel mai mare număr RSA , RSA-2048 , folosește două numere prime mai lungi de 300 de cifre)
se calculează produsul lor $n=pq$ ${\ displaystyle n = pq}$ ${\ displaystyle n = pq}$ , numit modulo (deoarece toate următoarele aritmetice sunt modulul n ) și produsul $\varphi (n)=(p-1)(q-1)$ ${\ displaystyle \ varphi (n) = (p-1) (q-1)}$ $\ varphi (n) = (p-1) (q-1)$ , unde este $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ $\ varphi (n)$ este funcția tozient
considerăm că factorizarea lui n este secretă și doar cei care aleg cele două numere prime, p și q , o cunosc
se alege apoi un număr $Și$ ${\ displaystyle e}$ $Și$ (numit exponent public ), acoperim cu $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ $\ varphi (n)$ și mai mic decât $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ $\ varphi (n)$
se calculează numărul $d$ ${\ displaystyle d}$ $d$ (numit exponent privat ) astfel încât produsul său cu $Și$ ${\ displaystyle e}$ $Și$ este congruent cu $1$ ${\ displaystyle 1}$ $1$ modul $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ $\ varphi (n)$ sau asta $ed\equiv 1{\pmod {\varphi (n)}}$ ${\ displaystyle and \ equiv 1 {\ pmod {\ varphi (n)}}}$ $și \ equiv 1 {\ pmod {\ varphi (n)}}$

Cheia publică este $(n,e)$ ${\ displaystyle (n, e)}$ $(nici)$ , în timp ce cheia privată este $(n,d)$ ${\ displaystyle (n, d)}$ $(n, d)$ . ^[5]

Puterea algoritmului constă în faptul că pentru a calcula $d$ ${\ displaystyle d}$ $d$ din $Și$ ${\ displaystyle e}$ $Și$ (sau invers) cunoașterea $n$ ${\ displaystyle n}$ $n$ dar ai nevoie de număr $\varphi (n)=(p-1)(q-1)$ ${\ displaystyle \ varphi (n) = (p-1) (q-1)}$ $\ varphi (n) = (p-1) (q-1)$ , și că calculul său necesită timpuri foarte lungi; de fapt, luarea în calcul a numerelor prime (adică descompunerea unui număr în divizorii săi primi) este o operație costisitoare din punct de vedere al calculului.

Un mesaj $m$ ${\ displaystyle m}$ $m$ este criptat prin operație $m^{e}{\pmod {n}}$ ${\ displaystyle m ^ {e} {\ pmod {n}}}$ $m ^ {e} {\ pmod {n}}$ transformându-l în mesajul criptat $c$ ${\ displaystyle c}$ $c$ . Odată difuzat, $c$ ${\ displaystyle c}$ $c$ este decriptat cu $c^{d}{\pmod {n}}=m$ ${\ displaystyle c ^ {d} {\ pmod {n}} = m}$ ${\ displaystyle c ^ {d} {\ pmod {n}} = m}$ . Procedura funcționează numai dacă $m<n$ ${\ displaystyle m <n}$ ${\ displaystyle m <n}$ și cheia $Și$ ${\ displaystyle e}$ $Și$ folosit pentru criptare și cheie $d$ ${\ displaystyle d}$ $d$ utilizate pentru a descifra sunt legate între ele $ed\equiv 1{\pmod {\varphi (n)}}$ ${\ displaystyle and \ equiv 1 {\ pmod {\ varphi (n)}}}$ $și \ equiv 1 {\ pmod {\ varphi (n)}}$ , deci atunci când un mesaj este criptat cu una dintre cele două chei, acesta poate fi decriptat numai folosind cealaltă. Algoritmul se bazează pe ipoteza niciodată dovedită (cunoscută sub numele de presupunerea RSA ) că problema calculării ${\sqrt[{e}]{c}}\mod n$ ${\ displaystyle {\ sqrt [{e}] {c}} \ mod n}$ ${\ sqrt [{e}] {c}} \ mod n$ , cu $n$ ${\ displaystyle n}$ $n$ un număr compus ai cărui factori nu sunt cunoscuți, nu poate fi urmărit din punct de vedere al calculului.

Semnătura digitală nu este altceva decât invers: mesajul este criptat cu cheia privată, astfel încât oricine poate, folosind cheia publică cunoscută de toată lumea, să o decripteze și, pe lângă faptul că poate să o citească în text clar, să fie sigur că mesajul este a fost trimis de proprietarul cheii private corespunzătoare celei publice folosite pentru a-l citi.

Din motive de eficiență și comoditate, mesajul este în mod normal trimis în text clar cu semnătura digitală a unui hash al mesajului atașat; în acest fel destinatarul poate citi direct mesajul (care este în text clar), utiliza cheia publică pentru a extrage hash-ul din semnătură și a verifica dacă acesta este același cu cel calculat local pe mesajul primit. Dacă hash-ul utilizat este sigur criptografic , corespondența celor două valori confirmă faptul că mesajul primit este identic cu cel semnat și transmis inițial.

Fundamente matematice

Decriptarea mesajului este asigurată grație unor teoreme matematice; de fapt din calcul obținem:

$c^{d}{\pmod {n}}=(m^{e})^{d}{\pmod {n}}=m^{ed}{\pmod {n}}$ ${\ displaystyle c ^ {d} {\ pmod {n}} = (m ^ {e}) ^ {d} {\ pmod {n}} = m ^ {ed} {\ pmod {n}}}$ $c ^ {d} {\ pmod {n}} = (m ^ {e}) ^ {d} {\ pmod {n}} = m ^ {{ed}} {\ pmod {n}}$

Dar știm asta $ed\equiv 1{\pmod {(p-1)(q-1)}}$ ${\ displaystyle and \ equiv 1 {\ pmod {(p-1) (q-1)}}}$ $și \ equiv 1 {\ pmod {(p-1) (q-1)}}$ , în consecință, avem asta $ed\equiv 1{\pmod {p-1}}$ ${\ displaystyle and \ equiv 1 {\ pmod {p-1}}}$ $și \ equiv 1 {\ pmod {p-1}}$ este asta $ed\equiv 1{\pmod {q-1}}$ ${\ displaystyle and \ equiv 1 {\ pmod {q-1}}}$ $și \ equiv 1 {\ pmod {q-1}}$ .

Deci, prin mica teoremă a lui Fermat :

$m^{ed}\equiv m{\pmod {p}}$ ${\ displaystyle m ^ {ed} \ equiv m {\ pmod {p}}}$ $m ^ {{ed}} \ equiv m {\ pmod {p}}$ Și $m^{ed}\equiv m{\pmod {q}}$ ${\ displaystyle m ^ {ed} \ equiv m {\ pmod {q}}}$ $m ^ {{ed}} \ equiv m {\ pmod {q}}$

De cand $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ sunt diferite și numere prime, putem aplica teorema restului chinezesc , obținând asta

$m^{ed}\equiv m{\pmod {pq}}$ ${\ displaystyle m ^ {ed} \ equiv m {\ pmod {pq}}}$ $m ^ {{ed}} \ equiv m {\ pmod {pq}}$

și prin urmare că

$c^{d}\equiv m{\pmod {n}}$ ${\ displaystyle c ^ {d} \ equiv m {\ pmod {n}}}$ $c ^ {{d}} \ equiv m {\ pmod {n}}$

Exemplu

Iată un exemplu de criptare și decriptare RSA. Numerele alese sunt numere prime deliberat mici, dar în realitate se folosesc numere de ordinul lui $10^{100}$ ${\ displaystyle 10 ^ {100}}$ $10 ^ {{100}}$ .

Generarea cheie

$p=3$ ${\ displaystyle p = 3}$ $p = 3$ Și $q=11$ ${\ displaystyle q = 11}$ $q = 11$
$n=p*q=3*11=33$ ${\ displaystyle n = p * q = 3 * 11 = 33}$ $n = p * q = 3 * 11 = 33$ Și $\varphi (n)=(p-1)(q-1)=2*10=20$ ${\ displaystyle \ varphi (n) = (p-1) (q-1) = 2 * 10 = 20}$ ${\ displaystyle \ varphi (n) = (p-1) (q-1) = 2 * 10 = 20}$
prind $e=7$ ${\ displaystyle e = 7}$ $e = 7$ , de cand $e<20$ ${\ displaystyle e <20}$ $și <20$ și $Și$ ${\ displaystyle e}$ $Și$ este coprimo cu $20$ ${\ displaystyle 20}$ $20$ (nu este necesar ca $Și$ ${\ displaystyle e}$ $Și$ fii primul)
$d=3$ ${\ displaystyle d = 3}$ $d = 3$ ; intr-adevar $ed=7*3=21\equiv 1{\pmod {20}}$ ${\ displaystyle ed = 7 * 3 = 21 \ equiv 1 {\ pmod {20}}}$ $ed = 7 * 3 = 21 \ equiv 1 {\ pmod {20}}$ atâta timp cât $21/20=1$ ${\ displaystyle 21/20 = 1}$ $21/20 = 1$ cu rest $1$ ${\ displaystyle 1}$ $1$ ^[6]

Deci avem cheia privată $(33,3)$ ${\ displaystyle (33,3)}$ $(33,3)$ și cheia publică $(33,7)$ ${\ displaystyle (33,7)}$ $(33,7)$ (faptul că $d$ ${\ displaystyle d}$ $d$ este egal cu $p$ ${\ displaystyle p}$ $p$ este pur întâmplător).

Criptare și decriptare

Să analizăm acum mesajul $m=15$ ${\ displaystyle m = 15}$ $m = 15$ și să-l criptăm pentru a primi mesajul criptat $c$ ${\ displaystyle c}$ $c$ ; evident putem folosi 33 și 7, dar nu 3, care face parte din cheia privată.

$c=m^{e}{\pmod {n}}=15^{7}{\pmod {33}}=27$ ${\ displaystyle c = m ^ {e} {\ pmod {n}} = 15 ^ {7} {\ pmod {33}} = 27}$ $c = m ^ {e} {\ pmod {n}} = 15 ^ {{7}} {\ pmod {33}} = 27$

Și acum să descifrăm $c=27$ ${\ displaystyle c = 27}$ $c = 27$ a obtine $m$ ${\ displaystyle m}$ $m$ ; aici vom folosi 3, componentă esențială a cheii private.

$m=c^{d}{\pmod {n}}=27^{3}{\pmod {33}}=15$ ${\ displaystyle m = c ^ {d} {\ pmod {n}} = 27 ^ {3} {\ pmod {33}} = 15}$ $m = c ^ {d} {\ pmod {n}} = 27 ^ {{3}} {\ pmod {33}} = 15$

Așa că am descifrat în cele din urmă mesajul.

Semnătură oarbă

Există, de asemenea, un format de semnătură digitală bazat pe RSA, în care conținutul unui mesaj este ascuns înainte de a fi semnat, numit o semnătură oarbă .

Notă

^ Trio GCHQ recunoscut pentru cheia securizării cumpărăturilor online , pe bbc.com , BBC, 5 octombrie 2010.
^ Kriptópolis, septembrie 2005.
^ A. Shamir, E. Tromer, On the Cost of Factoring RSA-1024 , 2003. Parametru url gol sau lipsă ( ajutor )
^ Franke și alt., SHARK: Un dispozitiv de cernere hardware realizabil pentru factoring 1024-bit , 2005. Parametru url gol sau lipsă ( ajutor )
^ Deși din punct de vedere matematic simpla cunoaștere a $(n,d)$ ${\ displaystyle (n, d)}$ ${\ displaystyle (n, d)}$ este suficient, din motive de eficiență, este posibil să se rețină în mod explicit cei doi factori $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ , a căror cunoaștere face posibilă utilizarea unei metode de calcul mai rapide pentru criptare / decriptare.
^ d poate fi calculat utilizând algoritmul extins al lui Euclid .

Elemente conexe

linkuri externe

Site-ul companiei comerciale RSA , pe rsasecurity.com .

Portal de criptografie

Portal de securitate IT

[:0-1] Trio GCHQ recunoscut pentru cheia securizării cumpărăturilor online , pe bbc.com , BBC, 5 octombrie 2010.

[2] Kriptópolis, septembrie 2005.

[3] A. Shamir, E. Tromer, On the Cost of Factoring RSA-1024 , 2003. Parametru url gol sau lipsă ( ajutor )

[4] Franke și alt., SHARK: Un dispozitiv de cernere hardware realizabil pentru factoring 1024-bit , 2005. Parametru url gol sau lipsă ( ajutor )

[5] Deși din punct de vedere matematic simpla cunoaștere a $(n,d)$ ${\ displaystyle (n, d)}$ ${\ displaystyle (n, d)}$ este suficient, din motive de eficiență, este posibil să se rețină în mod explicit cei doi factori $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ , a căror cunoaștere face posibilă utilizarea unei metode de calcul mai rapide pentru criptare / decriptare.

[6] te fi calculat utilizând algoritmul extins al lui Euclid .

[1]

[2]

[3]

[4]

[5]

[6]