Criptare RSA. Descrierea și implementarea algoritmului RSA

Criptarea RSA este unul dintre primele criptosisteme practice cu cheie publică, care este utilizat pe scară largă pentru transmiterea sigură a datelor. Diferența sa principală față de serviciile similare este aceea că cheia de criptare este deschisă și diferă de cheia de decriptare, care este păstrată în secret. În tehnologia RSA această asimetrie Se bazează pe complexitatea practică a factorului de reproducere a două mari numere prime (problema factoring).

Istoria creației

Numele RSA este format din literele inițiale ale numelor de familie Rivest, Shamir și Adleman, oameni de știință care au descris pentru prima dată în mod similar algoritmi de criptare în anul 1977. Clifford Cox, matematician englez care a lucrat pentru serviciile secrete britanice, a dezvoltat pentru prima dată un sistem echivalent în 1973, dar nu a fost declasificat până în 1997.

Utilizatorul RSA creează și publică o cheie publică bazată pe două numere prime prime, împreună cu o valoare auxiliară. Prime numere ar trebui să fie păstrate în secret. Oricine poate folosi cheia publică pentru a cripta mesajul, dar dacă este suficient de mare, numai cineva cu cunoștințe de numere prime poate decoda mesajul. Dezvăluirea cripțiunii RSA este cunoscută drept principala problemă: astăzi rămâne o discuție deschisă despre cât de fiabil este acest mecanism.

RSA este un algoritm relativ lent, motiv pentru care nu este folosit pe scară largă pentru direct criptarea datelor utilizatorului. În cele mai multe cazuri, această metodă este folosită pentru transmiterea în cheia partajată criptat pentru o cheie de criptare simetrică, care, la rândul lor, pot efectua operații de criptare și decriptare în vrac la o viteză mult mai mare.

Când a apărut sistemul criptos în forma modernă?

Ideea unei chei asimetrice criptosisteme este atribuită lui Diffie și Hellman, care au publicat conceptul în 1976, prezentând semnăturile digitale și încercând să aplice teoria numerelor. Formularea lor folosește o cheie secretă comună, creată din exponentierea unui număr modulo un număr prime. Cu toate acestea, ei au lăsat deschis problema implementării acestei funcții, deoarece principiile factoringului nu au fost bine înțelese la momentul respectiv.

Rivest, Adi Shamir și Adleman de la Institutul de Tehnologie din Massachusetts au făcut mai multe încercări pe parcursul anului pentru a crea o funcție unidirecțională dificil de decodat. Rivest și Shamir (ca oameni de știință pe calculator) au oferit multe funcții potențiale, în timp ce Adleman (ca matematician) a căutat "slăbiciunile" algoritmului. Au folosit multe abordări și, în cele din urmă, în aprilie 1977 au dezvoltat sistemul, cunoscut în sfârșit ca RSA.

EDS și cheia publică

Semnătura digitală electronică, sau EDS, face parte integrantă din documentele de tip electronic. Se formează cu o anumită modificare criptografică a datelor. Cu ajutorul acestui atribut este posibil să se verifice integritatea documentului, confidențialitatea acestuia și, de asemenea, să se determine cine îl deține. De fapt, aceasta este o alternativă la semnătura standard obișnuită.

Acest sistem de criptare (criptare RSA) oferă o cheie publică, care diferă de cele simetrice. Principiul funcționării sale este că se folosesc două chei diferite - închise (criptate) și, de asemenea, deschise. Primul este folosit pentru a genera EDS și, ulterior, pentru a descifra textul. Al doilea - pentru criptarea corectă și verificarea EDS.

Utilizarea semnăturii face posibilă o mai bună înțelegere a criptării RSA, exemplul căruia poate fi citat ca un document secret obișnuit, închis de ochii curioși.

Care este esența algoritmului?

Algoritmul RSA constă din patru etape: generarea de chei, distribuirea acestora, criptarea și decriptarea. După cum sa menționat deja, criptarea RSA include o cheie publică și o cheie privată. Deschis pot fi cunoscute de toată lumea și utilizate pentru criptarea mesajelor. Esența este că mesajele criptate cu o cheie publică pot fi decriptate numai într-o anumită perioadă de timp utilizând o cheie privată.

Din motive de securitate, numerele întregi ar trebui să fie selectate aleatoriu și să aibă aceeași dimensiune, dar să difere în lungime cu câteva cifre pentru a face factoringul mai dificil. Aceleași numere pot fi găsite cu ajutorul unui test pentru simplitatea lor, astfel încât criptarea informațiilor trebuie să devină neapărat mai complicată.

Cheia publică constă dintr-un modul și un exponent public. Cel închis constă dintr-un modul și un indicator privat, care trebuie păstrate în secret.

Criptarea fișierelor RSA și a punctelor slabe

Cu toate acestea, există o serie de mecanisme pentru hacking un RSA simplu. Când criptați cu scoruri mici și valori mici ale numerelor, cifrul poate fi ușor deschis dacă selectați rădăcina textului cifrat peste numere întregi.

Deoarece RSA-criptare este un algoritm determinist (de exemplu, nu are nici o componentă aleatoare), un atacator poate lansa cu succes textul selectat atac deschis împotriva Criptosistem prin criptarea plaintexts probabil sub cheia publică și verifică dacă acestea sunt egale ciphertext. Semantically criptosistem securizată este numit în cazul în care un atacator nu poate distinge între cele două criptare unul de altul, chiar dacă el cunoaște textele relevante în forma extinsă. Așa cum este descris mai sus, RSA alte servicii fără padding nu este sigură semantic.

Algoritmi adiționali pentru criptare și protecție

Pentru a evita problemele de mai sus, în implementarea practică a RSA, o formă de umplere structurată, randomizată este de obicei construită înainte de criptare. Acest lucru asigură faptul că conținutul nu se încadrează în raza de texte nesigure și că acest mesaj nu poate fi descoperit prin selectarea aleatorie.

Securitatea sistemului de criptografie RSA și criptarea informațiilor se bazează pe două probleme matematice: problema factorării numărului mare și a problemelor reale ale RSA. Dezvăluirea completă a textului cifru și EDS în RSA este considerată inacceptabilă, presupunând că ambele probleme nu pot fi rezolvate în totalitate.

Cu toate acestea, datorită capacității de a restaura multiplicatori simpli, un atacator poate calcula o cheie secretă dintr-o cheie publică și poate decripta textul utilizând o procedură standard. În ciuda faptului că nu a fost găsită astăzi nici o metodă existentă de factorizare a numerelor mari pe un calculator clasic, nu sa dovedit că nu există.

automatizare

Instrumentul, numit Yafu, poate fi folosit pentru a optimiza procesul. Automatizarea YAFU este o funcție avansată care combină algoritmi de factorizare în metodologia intelectuală și adaptiv, care minimizează timpul pentru a găsi factorii de numere de intrare arbitrare. Cele mai multe implementari algoritm care permite multithreaded Yafu utilizarea deplină a multi- sau mai multe procesoare multi-core (inclusiv SNFS, SIQS și ECM). În primul rând, este un instrument de linie de comandă. Timpul petrecut în căutarea unui factor de criptare utilizând Yafu pe un computer convențional poate fi redus la 103,1746 secunde. Instrumentul procesează fișiere binare cu o capacitate de 320 de biți sau mai mult. Acesta este un software foarte complex, care necesită o anumită cantitate de abilități tehnice de instalat și configurat. Astfel, criptarea RSA poate fi vulnerabilă.

Încercări de rupere în epoca modernă

În 2009, Benjamin Moody folosind cheia RSA-512 biți a fost de lucru pe descifrarea kriptoteksta timp de 73 de zile, utilizând software-ul numai bine-cunoscut (GGNFS) și desktop-ul mediu (dual-core Athlon64 la 1900 MHz). După cum arată experiența, necesară ușor mai puțin de 5 GB de disc și aproximativ 2,5 GB de memorie pentru procesul de „cernere“.

Începând cu 2010, cel mai mare număr RSA factorizat a fost de 768 de biți lungi (232 cifre zecimale sau RSA-768). Descoperirea lui a durat doi ani pe câteva sute de computere la un moment dat.

În practică, totuși, cheile RSA au o lungime lungă - de obicei de la 1024 la 4096 biți. Unii experți cred că cheile de 1024 de biți pot deveni nesigure în viitorul apropiat sau chiar pot fi deja sparte de un atacator bine finanțat. Cu toate acestea, puțini vor susține că cheile de 4096 de biți pot fi dezvăluite și în viitorul apropiat.

perspective

Prin urmare, se presupune, în general, că RSA este sigură dacă numărul este suficient de mare. Dacă numărul principal este de 300 de biți sau mai mic, textul cifrat și semnătura digitală pot fi descompuse pentru câteva ore pe un computer personal folosind software deja disponibil în domeniul public. Cheile cu o lungime de 512 de biți, după cum sa dovedit, ar putea fi deschise în 1999 utilizând câteva sute de calculatoare. În zilele noastre, acest lucru este posibil în câteva săptămâni cu utilizarea hardware-ului public. Astfel, este posibil ca criptarea RSA pe degete să fie dezvăluită cu ușurință în viitor, iar sistemul va deveni depășit fără speranță.

Oficial, în 2003, securitatea cheilor de 1024 de biți a fost pusă la îndoială. În prezent, se recomandă să aibă o lungime de cel puțin 2048 de biți.