RSA (criptosistem)

Utilizarea Chineză restul algorithmEdit

Pentru eficiență multe populare crypto biblioteci (cum ar fi OpenSSL, Java și .NET), se folosesc următoarele optimizare pentru decriptare și semnarea bazat pe Chineză restul teorema. Următoarele valori sunt precalculate și stocate ca parte a cheii private:

Aceste valori permite destinatarului pentru a calcula exponentiala m = cd (mod pq) mai eficient, după cum urmează:

Acest lucru este mult mai eficientă decât calcul exponentiala de cuadratura chiar dacă două modular puteri trebuie să fie calculat., Motivul este că aceste două exponențiări modulare folosesc atât un exponent mai mic, cât și un modul mai mic.

factorizarea numerelor Întregi și RSA problemEdit

securitatea criptosistem RSA se bazează pe două probleme de matematică: problema de factoring număr mare și RSA problema. Decriptarea completă a unui text cifrat RSA este considerată a fi imposibilă pe presupunerea că ambele probleme sunt grele, adică nu există un algoritm eficient pentru rezolvarea lor., Asigurarea securității împotriva decriptării parțiale poate necesita adăugarea unei scheme de umplutură securizată.

problema RSA este definită ca sarcina de a lua rădăcinile eth modulo a composite n: recuperarea unei valori m astfel încât c ≡ me (mod n), unde (n, E) este o cheie publică RSA și c este un text cifrat RSA. În prezent, cea mai promițătoare abordare pentru rezolvarea problemei RSA este factorul modulului n. cu capacitatea de a recupera factorii prime, un atacator poate calcula exponentul secret d dintr-o cheie publică (n, E), apoi decripta c folosind procedura standard., Pentru a realiza acest lucru, un atacator factori n în p și q, și calculează lcm(p − 1, q − 1), care permite determinarea d la e. Nu polinom timp metoda de factoring numere întregi mari pe un calculator clasic a fost încă găsit, dar nu s-a dovedit că nu există. A se vedea factorizare întreg pentru o discuție a acestei probleme.sita polinoame pătratice Multiple (MPQS) pot fi folosite pentru a factor modulul public n.,

prima factorizare RSA – 512 din 1999 a folosit sute de calculatoare și a necesitat echivalentul a 8.400 de ani MIPS, pe un timp scurs de aproximativ șapte luni. Până în 2009, Benjamin Moody ar putea factor o cheie de biți RSA-512 în 73 de zile folosind doar software public (GGNFS) și computerul său desktop (un Athlon64 dual-core cu un procesor de 1,900 MHz). Au fost necesare doar mai puțin de cinci gigabyte de stocare pe disc și aproximativ 2, 5 gigabyte de memorie RAM pentru procesul de cernere.,Rivest, Shamir și Adleman au remarcat că Miller a arătat că-presupunând adevărul Ipotezei Riemann extinse-găsirea d de la n și e este la fel de grea ca factorizarea n în P și q (până la o diferență de timp polinomială). Cu toate acestea, Rivest, Shamir și Adleman au remarcat, în secțiunea IX/D a lucrării lor, că nu au găsit o dovadă că inversarea RSA este la fel de grea ca factoringul.

începând cu 2020, cel mai mare număr RSA facturat public a fost de 829 biți (250 cifre zecimale, RSA-250). Factorizarea sa, printr-o implementare distribuită de ultimă generație, a durat aproximativ 2700 de ani de procesor., În practică, cheile RSA au de obicei 1024 până la 4096 biți. În 2003, RSA Security a estimat că cheile de 1024 biți ar putea deveni crackable până în 2010. Începând cu 2020, nu se știe dacă astfel de chei pot fi crăpate, dar recomandările minime s-au mutat la cel puțin 2048 biți. În general, se presupune că RSA este sigură dacă n este suficient de mare, în afara calculului cuantic.dacă n este de 300 de biți sau mai scurt, acesta poate fi luat în câteva ore într-un computer personal, folosind software-ul deja disponibil gratuit., Cheile de biți 512 s-au dovedit a fi practic rupte în 1999, când RSA-155 a fost luat prin utilizarea a câteva sute de computere, iar acestea sunt acum luate în câteva săptămâni folosind hardware comun. Exploatările care utilizează certificate de semnare a codului pe 512 biți care ar fi putut fi luate în considerare au fost raportate în 2011. Un dispozitiv hardware teoretic numit TWIRL, descris de Shamir și Tromer în 2003, a pus sub semnul întrebării securitatea tastelor de 1024 biți.,în 1994, Peter Shor a arătat că un computer cuantic-dacă s – ar putea vreodată să fie creat practic în acest scop-ar fi capabil să ia în considerare timpul polinomial, rupând RSA; vezi algoritmul lui Shor.

generare de taste Defecteedit

Găsirea de numere prime mari p și q se face de obicei prin testarea numere aleatoare de dimensiunea corectă cu probabilistic primality teste care elimina rapid, practic, toate de nonprimes.

numerele p și q nu ar trebui să fie „prea aproape”, ca nu cumva factorizarea Fermat pentru n să aibă succes., Dacă p-q este mai mică decât 2N1 / 4 (n = P * q, care, chiar și pentru valori mici 1024-biți de n este 3×1077) rezolvarea pentru P și q este banal. Mai mult, dacă fie p − 1, fie q − 1 are doar factori prime mici, n poate fi luat rapid prin algoritmul P − 1 al lui Pollard și, prin urmare, astfel de valori ale P sau q ar trebui eliminate.este important ca exponentul privat d să fie suficient de mare. Michael J. Wiener a arătat că dacă p este între q și 2q (ceea ce este destul de tipic) și d < n1/4/3, atunci d poate fi calculat eficient din n și e.,

nu există un atac cunoscut împotriva exponenților publici mici, cum ar fi e = 3, cu condiția să se utilizeze căptușeala corespunzătoare. Atacul Coppersmith are multe aplicații în atacarea RSA în mod specific dacă exponentul public e este mic și dacă mesajul criptat este scurt și nu este căptușit. 65537 este o valoare frecvent utilizată pentru e; această valoare poate fi considerată ca un compromis între evitarea potențialelor atacuri exponente mici și încă permite criptări eficiente (sau verificarea semnăturii)., NIST Publicație Specială privind Securitatea informatică (SP 800-78 Rev 1 August 2007) nu permite publice exponenți e mai mic decât 65537, dar nu a stat un motiv pentru această restricție.în octombrie 2017, o echipă de cercetători de la Universitatea Masaryk a anunțat vulnerabilitatea ROCA, care afectează cheile RSA generate de un algoritm încorporat într-o bibliotecă de la Infineon cunoscută sub numele de RSALib. Un număr mare de carduri inteligente și module de platformă de încredere (TPMs) s-au dovedit a fi afectate. Chei RSA vulnerabile sunt ușor de identificat folosind un program de testare echipa a lansat.,

Importanța puternic de numere aleatoare generationEdit

Un criptografic puternic generator de numere aleatorii, care a fost în mod corespunzător însămânțate cu adecvate de entropie, trebuie să fie utilizate pentru a genera numere prime p și q. O analiză compararea milioane de chei publice s-au adunat de pe Internet a fost realizată la începutul anului 2012, prin Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung și Christophe Wachter. Ei au fost capabili să factor de 0,2% din Cheile folosind doar Euclid ” s algoritm.

ei au exploatat o slăbiciune unică pentru criptosisteme bazată pe factorizare întreagă., Dacă n = pq este o cheie publică și n ‘=p ‘ q ‘este alta, atunci dacă din întâmplare p = p’ (dar q nu este egal cu q’), atunci un calcul simplu al gcd(n, n’) = p factori atât n cât și n’, compromițând total ambele chei. Lenstra și colab. rețineți că această problemă poate fi minimizată prin utilizarea unei semințe aleatorii puternice de lungime de biți de două ori nivelul de securitate prevăzut sau prin utilizarea unei funcții deterministe pentru a alege q dat p, în loc să aleagă P și q independent.Nadia Heninger a făcut parte dintr-un grup care a făcut un experiment similar. Au folosit o idee despre Daniel J., Bernstein a calcula CMMDC de fiecare cheie RSA n împotriva produs de toate celelalte chei n’ au găsit (o 729 de milioane de cifre), în loc de calcul fiecare cmmdc(n,n’) separat, obținându-se astfel o foarte semnificativă speedup deoarece după o divizie mare, GCD problema este de dimensiuni normale.

Heninger spune pe blogul ei că rău cheile au avut loc aproape în întregime în aplicații embedded, inclusiv „firewall-uri, routere, VPN, dispozitive, remote server administration aparate, imprimante, proiectoare și telefoane VOIP” de peste 30 de producători., Heninger explică faptul că cea de-a împărtășit-prim problemă descoperit de către cele două grupuri rezultate din situațiile în care generatorul de numere pseudoaleatoare este slab însămânțate inițial, și apoi este semănat între generația de prima și a doua numere prime. Utilizarea semințelor de entropie suficient de ridicată obținute din temporizările cursei cheie sau zgomotul diodei electronice sau zgomotul atmosferic de la un receptor radio reglat între stații ar trebui să rezolve problema.generarea puternică a numerelor aleatorii este importantă în fiecare fază a criptografiei cheilor publice., De exemplu, dacă un generator slab este utilizat pentru tastele simetrice care sunt distribuite de RSA, atunci un interceptor ar putea ocoli RSA și ghici direct cheile simetrice.Kocher a descris un nou atac asupra RSA în 1995: dacă atacatorul Eve cunoaște hardware-ul lui Alice suficient de detaliat și este capabil să măsoare timpii de decriptare pentru mai multe ciphertexte cunoscute, Eve poate deduce rapid cheia de decriptare D. Acest atac poate fi aplicat și împotriva schemei de semnătură RSA., În 2003, Boneh și Brumley demonstrat o mai practic de atac capabil de a recupera RSA factorizările pe o conexiune de rețea (de exemplu, dintr-o Secure Sockets Layer (SSL)-activat serverul web) Acest atac a profita de scurgeri de informații de către Chinezi restul teorema de optimizare folosit de multe RSA implementări.o modalitate de a contracara aceste atacuri este să vă asigurați că operația de decriptare durează o perioadă constantă de timp pentru fiecare text cifrat. Cu toate acestea, această abordare poate reduce semnificativ performanța., În schimb, majoritatea implementărilor RSA folosesc o tehnică alternativă cunoscută sub numele de orbire criptografică. RSA orbitoare face uz de proprietatea multiplicativă a RSA. În loc să calculeze cd (mod n), Alice alege mai întâi o valoare aleatorie secretă r și calculează (rec)d (mod n). Rezultatul acestui calcul, după aplicarea teoremei lui Euler, este rcd (mod n) și astfel efectul lui r poate fi îndepărtat prin înmulțirea cu inversul său. O nouă valoare a lui r este aleasă pentru fiecare cifrtext. Cu orbirea aplicată, timpul de decriptare nu mai este corelat cu valoarea textului cifrat de intrare și astfel atacul de sincronizare eșuează.,în 1998, Daniel Bleichenbacher a descris primul atac practic adaptiv de text cifrat ales, împotriva mesajelor criptate RSA folosind schema de umplutură PKCS #1 V1 (o schemă de umplutură Randomizează și adaugă structură unui mesaj criptat RSA, astfel încât este posibil să se determine dacă un mesaj decriptat este valid). Datorită defectelor cu schema PKCS #1, Bleichenbacher a reușit să monteze un atac practic împotriva implementărilor RSA ale protocolului Secure Socket Layer și să recupereze cheile de sesiune., Ca urmare a acestei lucrări, criptografii recomandă acum utilizarea unor scheme de umplutură sigure, cum ar fi o umplutură optimă de criptare asimetrică, iar RSA Laboratories a lansat noi versiuni ale PKCS #1 care nu sunt vulnerabile la aceste atacuri.

atacuri de analiză a canalelor Lateraleedit

a fost descris un atac al canalelor laterale folosind analiza de predicție a sucursalelor (BPA). Multe procesoare folosesc un predictor de ramură pentru a determina dacă o ramură condiționată în fluxul de instrucțiuni al unui program este probabil să fie luată sau nu. Adesea, aceste procesoare implementează, de asemenea, multithreading simultan (SMT)., Atacurile de analiză de predicție a sucursalelor utilizează un proces de spionaj pentru a descoperi (statistic) cheia privată atunci când este procesată cu aceste procesoare.analiza simplă de predicție a sucursalelor (SBPA) susține că îmbunătățește BPA într-un mod non-statistic. În lucrarea lor, „despre puterea analizei simple de predicție a ramurilor”, autorii SBPA (Onur Aciicmez și Cetin Kaya Koc) susțin că au descoperit 508 din 512 biți ai unei chei RSA în 10 iterații.

un atac de eroare de putere asupra implementărilor RSA a fost descris în 2010., Autorul a recuperat cheia modificând tensiunea de alimentare a procesorului în afara limitelor; acest lucru a cauzat mai multe defecțiuni de alimentare pe server.