Algoritmul RSASorin PetrusMaster TM , an II11. IntroducereAlgoritmul RSA a fost publicat pentru prima oar n 1977 de R. Rivest, A. Shamir i L. Adleman n revista Scientific American i se compune din calcule numerice n inelulnZ. Sistemeledetipul RSAfacpartedincategoriasistemelor criptograficecucheiepublic. Securitatea algoritmului se bazeaz pe problema factorizrii numerelor foarte mari. Algoritmul poate fi utilizat att pentru criptare, ct i pentru autentificare (semnturi digitale) i este foarte larg rspndit la ora actual. El este ntlnit n servere i browsere de web, n clieni i servere de e-mail, reprezentnd practic coloana vertebral a sistemului de pli electronice prin card-uri de credit.Algoritmul funcioneaz dup cum urmeaz: Se genereaz dou numere prime p i q, de lungime 2n bii (de exemplu 512, 1024, 2048 bii lungime). Deoarece mulimea numerelor prime este suficient de dens, numerele prime pot fi generate alegnd aleator numere ntregi de 2nbii i testndu-le cu ajutorul unui test probabilistic. Apoi, fie N=p*q, de lungime n bii. Numrul e trebuie ales astfel nct s ndeplineasc urmtoarele condiii: 1 < e < N iar e i(p - 1) * (q - 1) s fie relativ prime, sau altfel spus, s nu aib factori primi n comun. Se calculeaz dcu ajutorul algoritmului euclidian extins, astfel nct acesta s fie multiplul invers al lui e sau altfel spus d * e - 1 s fie divizibil cu (p-1) * (q-1). n practic, d sepoate obine foarte simplu cutnd rezolvarea ecuaiei eq p xd1 ) 1 ( * ) 1 ( * + astfel nct d i x s fie numere ntregi. Valorile diesunt numite exponentul privat, respectiv exponentul public al algoritmului. Funciadecriptare/semnarearatastfel: N M Cemod , undeMreprezintmesajul de criptat (un ntreg pozitiv mai mic dect N). Funcia de decriptare/verificare arat astfel:N M Cdmod , unde C reprezint textul criptat. Cheiapublicestereprezentat deperechea(N, e), iar cheiaprivat deperechea(N, d). Numruld mai este cunoscut i sub numele de trap door, deoarece cunoaterea sa permite inversarea rapid a funciei RSA.Viteza algoritmului RSA depinde n mare msur de lungimea cheilor utilizate, de tipul deimplementare, deprocesorul pecareseruleazaplicaia, darideprotocolulcetrebuie implementat. Deseori, pentruaobineovitezsporitnaplicaiilepractice, sunt utilizai exponeni publici mici, acest fapt implicnd ns i riscuri corespunztoare. Exist chiar grupuri ntregi de utilizatori care folosesc acelai exponent public, doar modulul N fiinddiferit. n acest caz exist ns reguli stricte ce trebuiesc respectate pentru cele dou numere prime p i q, astfel nct sigurana algoritmului s nu fie periclitat. Utiliznd, cum spuneam, exponeni publici mici, se obine o vitez mai mare de criptare i verificare n comparaie cu procesele inverse de decriptare i semnare a datelor. Utiliznd algoritmii generali de calcul ai exponenialului, operaiile cu cheie public consum un timp proporional cu O(n), iar operaiile cu cheie privat necesit aproximativ O(n), unde n reprezint numrul de bii ai lui N. Tehnicile de multiplicare rapid, necesit de obicei mai puini pai, sunt ns destul de rar folosite datorit complexitii lor, i a faptului c pentru lungimi tipice de chei, ele sunt totui mai lente. Dac comparm viteza algoritmului RSA cu cea a unui algoritm cu cheie simetric (DES de exemplu), putem observa c n funcie de implementare (HW sau SW) cel din urm este cu pn la aproximativ 1000 de ori mai rapid dect RSA. Cu toate acestea, utilizarea RSA n algoritmi de distribuire de chei (simetrice) sau n alte aplicaii, n care viteza este mai puin important, prezint avantaje de netgduit.2Securitatea sistemelor RSA se bazeaz pe presupunerea c funciaN M Cemod esteunidirecional, fiind computaional dificil de a se gsi mesajul iniial Mn absena exponentului de decriptare d. Exist ns posibilitatea, cel puin teoretic, de a ncerca factorizarealui Nprinmetodaforei brutesauprinaltemetode, faptcearducelaaflarea numerelorpiq. Apoi utilizndalgoritmul euclidianextinssepoatecalculaexponentul de decriptare d, ceea ce ar duce la compromiterea cheii private i la descifrarea textului criptat. nc de la publicarea sa, algoritmul RSA a fost studiat de o mulime de cercettori, fiind supus la nenumrate teste. Cu toate c de-a lungul celor mai bine de 25 de ani de utilizare au rezultat diverse vulnerabiliti, algoritmul s-a dovedit suficient de rezistent (pn n prezent) pentru a putea oferi un grad ridicat de securitate. Metodele de atac rezultate nu fac dect s ilustreze nc o dat pericolul utilizrii RSA n condiii necorespunztoare, programarea unei versiuni sigure de RSA nefiind deloc o problem simpl.2. Metode de analiz i atac. O clasificare general a acestora.Dificultatea de a inversa funcia RSA pentru mesaje aleatoare duce la concluzia c, dat fiind tuplul (N, e, C), un atacator nu va putea obine mesajul criptat M. Cu toate acestea, se pot obine diverse informaii despre M, astfel nct RSA nu este un sistem sigur din punct de vedere semantic(datefiindN, e, C, sepotobinerelativuorproprieti alelui Mdeexemplu simbolul Jacobi al lui M peste N). RSA poate fi fcut ns sigur din punct de vedere semantic dac se adaug informaie aleatoare n procesul de criptare [1].O clasificare a metodelor de atac este relativ dificil de fcut, cu toate acestea se poate aborda problema din dou direcii. n primul rnd se poate ncerca clasificarea metodelor de atac dup impactul pe care l au asupra algoritmului. Astfel, se pot identifica dou categorii de atacuri:atacuri ce compromit cheia privat, compromind practic ntreaga securitate a sistemului; atacuri ce compromit unsingur mesaj criptat, cheia privat putndfi ns utilizat n continuare.Dinprima categorie putemenumerametoda forei brute,atacul exponentului privat mic etc. Atacurile din cea de a doua categorie sunt n general mult mai subtile, folosind metode relativ complicate deaflareamesajului. Cu toate acestea,timpul utilizat pentru aflarea unui mesaj trebuie s fie mult mai mic dect timpul necesar metodei forei brute, pentru ca atacul s aib o anumit relevan. Totodatsuntimportante i condiiile ce trebuiesc ndeplinite astfel nct metoda s poat fi aplicat. O alt metod de a aborda o eventual clasificare a metodelor de analiz i atac o reprezint imprirea acestora pe categorii dup proprietile utilizate n cadrul atacului. Putem enumera astfel: metode elementare de atac; metoda exponentului privat mic; metodele exponentului public mic; atacuri ndreptate mpotriva diverselor implementri.3. Factorizarea numerelor ntregiO metod de a ataca algoritmul RSA este aceea de a ncerca factorizarea modulului N.Aceasta mai este numit i metoda forei brute. Dac factorizarea lui N reuete, este foartesimplude asecalcula apoi(p-1)*(q-1) i de a se gsi exponentul de decriptare. n practic aceasta nsemn compromiterea cheii private, permind atacatorului att citirea mesajelor, ct i falsificareasemnturilor. Operioaddetimps-acrezut csecuritateaRSAestedirect proporional cu problema factorizrii numerelor prime, dar cercetri recente au dezvluit faptul c spargerea unui sistem RSA nu este echivalent cu factorizarea lui N. Cu alte cuvinte, s-a 3dovedit c a sparge un sistem RSA cu exponent privat mic este mai simpl dect rezolvarea problemei factorizriilui N. Aceastans nu nsemn neaprat gsirea unei vulnerabiliti a algoritmului [2]. Securitatea RSA arfi puternic afectat dac s-ar reui gsirea unei metode uoare de factorizare a numerelor mari i foarte mari. Doar avansurile tehnologice n domeniul hardware(nparticular vitezacrescutdeprocesare) nupot ducelaoameninarereala algoritmului, deoarece prin alegerea unor chei cu lungime tot mai mare, aceast problem se rezolvdelasine. Denotat estei faptul calgoritmul cel mai rapiddefactorizareeste General Number Field Sieve, care ruleaz pe numere denbii lungime n ) log * * )) 1 ( ) exp((3 / 2 3 / 1n n O c+ , unde c < 2.De aceea, pentru ca un sistem criptografic de tip RSA s fie sigur se recomand ca n practicN s aib o lungime de cel puin 1024 de bii, dat fiind faptul c n ultima vreme s-au obinut rezultate bune n rezolvarea factorizrii lui N (cu mijloacele actuale s-a reuit factorizarea unor numere N de lungime de 512 bii). O alt metod de a ataca RSA, dar care nu este echivalent cu problema factorizrii numerelor prime, este gsirea unei metode rapide de calcul a rdcinii la e. DeoareceN M Cemod , acest atac ar permite oricui decriptarea datelor i falsificarea semnturilor, chiar i n absena cheii private. Nu se cunoate ns o aplicaie practic n care aceast metod s fi fost folosit cu succes, dar n anumite cazuri, dac se folosete un exponent publicmic, esteteoreticposibilaplicareaei i decriptareaunormesaje. Celedoumetode descrise anterior suntmetode cu ajutorul crora se pot recupera toate mesajele criptate cu o anumit cheie. Exist ns i metode ce au ca int aflarea textului unui singur mesaj criptat. Un succes n aceast direcie nu va permite ns atacatorului s decripteze i alte mesaje criptate cu aceeai cheie. Dac, deexemplu, metodafactorizrii ducepracticlacompromitereacheii private, nu acesta este rezultatul n cazul altor tipuri de atac.4. Metode elementare de atacExistunnumr demetodeelementaredeatac, caredei nuauorelevanmare, demonstreaztotuicfolosireadiletant a sistemului poate duce la compromiterea ideii de securitate. Cel mai simpluatacdeacest genestencercareadeaghici textul. Atacatorul presupune textul i l cripteaz cu cheia public pentru a verifica dac rezultatul obinut este acelai cu mesajul criptat. Metoda cea mai simpl de a prentmpina acest atac este adugarea unor bii aleatori n mesajul original.O alt metod relativ banal o reprezint metoda modulului comun N. Pentru a evita generarea unor numere prime mari pentru fiecare utilizator, s-a ncercat, de exemplu, utilizarea aceluiai modul Npentruungrupdeutilizatori. Oautoritatecentral distribuienaceast situaie perechile) , (i id epentru fiecare utilizator. La o analiz atent se poate observa ns faptul c fiecaremembrualgrupuluipoateutiliza perechea sa) , (i id e,pentruafactoriza N.OdatN factorizat, utilizatorul poate restaura orice cheie privat a unui alt membru al grupului. De aici rezult i concluzia c modulul N nu trebuie folosit niciodat n comun de ctre membrii unui grup. O alt metod clasic, numit blinding, faciliteaz obinerea unei semnturi false asupra unui mesaj M. Cel ce dorete obinerea semnturii produce un mesajN M r Memod *' , apoi ltrimitespresemnarevictimei. ncazulncaredestinatarulsemneaz mesajul iltrimite napoi,nu a fcutaltcevadect sproduc o semnturN M S modd ' ' . Falsificatorul nu trebuie dect s calculeze S = S' /r mod N pentru a obine semntura pentru mesajul M. De obicei ns semnturile se aplic asupra amprentei unui mesaj (obinut prin aplicarea unui hash unidirecional), i nu direct asupra mesajului, caz n care atacul i pierde nsemntatea. Aceast proprietateaRSAestetotui foarteimportantpentruimplementareaaceeacesenumete anonymous digital cash (atunci cnd identitatea persoanei ce semneaz nu trebuie dezvluit).5. Metoda exponentului privat mic4Aceastmetoddeatac seconcentreaz asupracazului n care sefolosete un exponentde valoaremic. Alegerea unui exponent privat ct mai micarelocatunci cndsedorete reducerea timpului de decriptare, sau a celui de semnare a datelor. n acest caz se poate observa o mbuntire a performanei algoritmului cu un factor de ordinul de mrime 10. M. Wiener a demonstrat c, tocmai naceste cazuri, sistemul RSAprezint ovulnerabilitateexcesiv, atacatorul putnd afla exponentul d. El a formulat teorema ce st la baza acestei metode de atac:Fie N=p*q astfel nct q 0. Dat fiind perechea (N, f), se pot afla ntr-un timp eficient toi ntregii X x