RSA-criptare. Descrierea și punerea în aplicare a algoritmului RSA

RSA-criptare este una dintre primele criptosistemele practice publice-cheie, care este utilizat pe scară largă pentru transmiterea de date securizate. Principala diferență sa de servicii similare este faptul că cheia de criptare este deschis și diferit de cheia de decriptare, care este păstrată secretă. Tehnologia RSA , această asimetrie se bazează pe dificultatea practică de factoring redarea a două numere prime mari (problema de factoring).

Istoria creației

RSA Numele este format din literele inițiale ale prenumelui Rivest, Shamir si Adleman - oamenii de stiinta primul care a descris în mod public acești algoritmi de criptare în 1977. Klifford Koks, un matematician englez, care a lucrat pentru serviciile de informații britanice, primul care a dezvoltat un sistem echivalent în 1973, dar nu a fost declasificat până în 1997

utilizator RSA creează și apoi publică cheia publică bazată pe două numere prime mari, împreună cu valoarea auxiliară. Numerele prime ar trebui să fie ținute secrete. Oricine poate utiliza cheia publică pentru a cripta un mesaj, dar dacă este suficient de mare, atunci numai cineva cu cunoștințe de numere prime poate decoda mesajul. dezvăluire criptarea RSA este cunoscută ca principala problemă astăzi este o discuție deschisă cu privire la modul în care un mecanism de încredere.

RSA algoritm este relativ lent, motiv pentru care acesta nu este utilizat pe scară largă ca pentru a direct cripta 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.

Atunci când a existat o criptosistem în forma sa actuală?

Ideea de chei criptografice asimetrice atribuite Diffie și Hellman, care a publicat conceptul în 1976, introducerea de semnături digitale, și încercând să aplice teoria numerelor. Formularea lor folosește o cheie secretă partajată generat dintr-un anumit număr de exponentiere modulo un număr prim. Cu toate acestea, au lăsat deschisă problema de realizare a acestei funcții, deoarece principiile de factoring nu a fost bine înțeleasă la momentul respectiv.

Rivest, Adi Shamir, și Adleman la MIT au făcut mai multe încercări de-a lungul anilor pentru a crea o functie de modul in care este dificil de a decoda. Rivest și Shamir (ca oameni de știință de calculator) au propus mai multe funcții potențiale, în timp ce Adleman (cum ar fi matematica) pentru a căuta „puncte slabe“ ale algoritmului. Ei au folosit o mulțime de abordări și, eventual, să dezvolte un sistem de final, acum cunoscut sub numele de RSA în aprilie 1977.

semnătura electronică și cheia publică

semnătură digitală sau semnătură electronică, este o parte integrantă a tipurilor de documente electronice. Acesta este format într-un anumit modificări de date criptografice. Cu acest atribut posibil pentru a verifica integritatea documentului, confidențialitatea acestuia, precum și pentru a determina cine deține. De fapt, o alternativă la semnătură standard ordinare.

Acest criptosistem (RSA-criptat) oferă cheia publică, spre deosebire de simetrice. Principiul său de funcționare este faptul că cele două chei diferite sunt folosite - închise (criptat) și în aer liber. Primul este utilizat pentru a genera semnătura digitală și apoi să fie capabil să decripteze textul. În al doilea rând - pentru criptarea efectivă și semnătura electronică.

Utilizarea de semnături pentru a înțelege mai bine criptarea RSA, un exemplu care poate fi redusă ca un secret normal „închis de ochii indiscreti,“ documentul.

Care este algoritmul?

RSA Algoritmul este format din patru etape: generarea de chei, distribuție, criptare și decriptare. După cum sa menționat deja, RSA-criptare include o cheie publică și o cheie privată. În aer liber poate fi cunoscut tuturor și este folosit pentru a cripta mesaje. Esența ei constă în faptul că mesajele criptate cu cheia publică poate fi decriptat numai într-o anumită perioadă de timp, folosind o cheie secretă.

Din motive de siguranță, întregilor care urmează să fie ales la întâmplare și să fie identice ca mărime, dar diferă în lungime de câteva numere pentru a face mai dificil de factoring. același număr Același lucru poate fi găsit în mod eficient printr-un test în simplitatea lor, astfel încât criptarea informațiilor trebuie să fie neapărat complicată.

Cheia publică constă din modulul și exponentul public. Unitatea interioară și constă dintr-o figură privată, care ar trebui să fie păstrate secrete.

criptarea RSA a fișierelor și a punctelor slabe

Cu toate acestea, există o serie de mecanisme simple de hacking RSA. Atunci când criptarea cu valori scăzute și mici de numere de cod pot fi ușor de deschis, în cazul în care ciphertext alege rădăcină 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 de criptare suplimentare și protecție

Pentru a evita problemele de mai sus, în punerea în practică a RSA sunt, de obicei inserate în unele forme de umplere structurat, randomizat, înainte de criptare. Acest lucru asigură că conținutul nu se încadrează în intervalul de plaintexts nesigure, și că acest mesaj nu poate fi rezolvată prin selecție aleatorie.

Securitatea RSA criptosistem și criptare bazată pe două probleme matematice: problema de factoring număr mare și problema reală RSA. Dezvăluirea completă a ciphertext și semnătura în RSA este considerată inadmisibilă pe presupunerea că ambele aceste probleme nu pot fi rezolvate în mod colectiv.

Cu toate acestea, cu capacitatea de a recupera factori de prim, un atacator poate calcula exponent secret al cheii publice și apoi decripta text utilizând procedura standard. În ciuda faptului că astăzi nici o metodă existentă pentru factoring numere întregi mari pe un computer clasic nu poate fi găsit, nu a fost dovedit că el 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 multithread algoritm care permite Yafu utilizarea deplină a multi- sau mai multe procesoare multi-core (inclusiv SNFs, SIQS și ECM). În primul rând, este controlată de instrument de linie de comandă. Timpul petrecut în căutarea factorului de criptare Yafu folosind un calculator convențional, poate fi redus la secunde 103.1746. Instrumentul procesează binar capacitate de 320 biți sau mai mult. Acesta este un software foarte complex, care necesită o anumită cantitate de competențe tehnice pentru a instala și configura. Astfel, RSA-criptare pot fi vulnerabile C.

Hacking încercări în ultimul timp

În 2009, Bendzhamin Mudi folosind chei 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“.

Din 2010, cel mai mare număr a fost factorizat RSA 768 biti (232 cifre zecimale, sau RSA-768). dezvăluirea lui a durat doi ani, la câteva sute de calculatoare dintr-o dată.

În practică, cheile RSA sunt lungi - 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 mai mult poate fi sparta atacatori foarte bine finanțate. Cu toate acestea, puțini ar argumenta că cheile de 4096 biți pot fi, de asemenea, dezvăluite în viitorul apropiat.

perspective

Prin urmare, de regulă, se presupune că RSA este sigur dacă numerele sunt suficient de mari. În cazul în care numărul de bază de 300 de biți sau mai scurte, și semnătura digitală ciphertext poate fi descompus în câteva ore pe un calculator personal folosind software-ul disponibil deja în domeniul public. O cheie de 512 biți lungime, așa cum se arată, poate fi deschis încă din 1999, cu utilizarea de câteva sute de calculatoare. In zilele noastre este posibil în câteva săptămâni, folosind un hardware la dispoziția publicului. Astfel, este posibil ca în buduschembudet prezentat cu ușurință RSA-criptat pe degete, iar sistemul va deveni iremediabil depășite.

Oficial, în 2003, a fost pusă sub semnul întrebării siguranța cheilor 1024-bit. În prezent, este recomandat să aibă o lungime minimă de 2048 biți.