Algoritmi de criptare

Notiuni generale a criptografiei:

Manuscrisul lui Voynich

Criptografia reprezintă o ramură a matematicii care se ocupă cu securizarea informaţiei precum şi cu autentificarea şi restricţionarea accesului într-un sistem informatic. În realizarea acestora se utilizează atât metode matematice (profitând, de exemplu, de dificultatea factorizării numerelor foarte mari), cât şi metode de criptare cuantică. Termenul criptografie este compus din cuvintele de origine greacă κρυπτός kryptós (ascuns) şi γράφειν gráfein (a scrie).

Criptologia este considerată ca fiind cu adevărat o ştiinţă de foarte puţin timp. Aceasta cuprinde atât criptografia - scrierea secretizată - cât şi criptanaliza. De asemenea, criptologia reprezintă nu numai o artă veche, ci şi o ştiinţa nouă: veche pentru că Iulius Cezar a utilizat-o deja, dar nouă pentru că a devenit o temă de cercetare academico-ştiinţfică abia începând cu anii 1970. Această disciplină este legată de multe altele, de exemplu de teoria numerelor, algebră, teoria complexităţii, informatică.

Criptografia modernă(Criptografia cu chei simetrice)

Criptografia cu chei simetrice se referă la metode de criptare în care atât trimiţătorul cât şi receptorul folosesc aceeaşi cheie (sau, mai rar, în care cheile sunt diferite, dar într-o relaţie ce la face uşor calculabile una din cealaltă). Acest tip de criptare a fost singurul cunoscut publicului larg până în 1976.

Studiul modern al cifrurilor cu chei simetrice se leagă mai ales de studiul cifrurilor pe blocuri şi al cifrurilor pe flux şi al aplicaţiilor acestora. Un cifru pe blocuri este, într-un fel, o formă modernă de cifru polialfabetic Alberti: cifrurile pe blocuri iau la intrare un bloc de text clar şi o cheie, şi produc la ieşire un bloc de text cifrat de aceeaşi dimensiune. Deoarece mesajele sunt aproape mereu mai lungi decât un singur bloc, este necesară o metodă de unire a blocurilor succesive. S-au dezvoltat câteva astfel de metode, unele cu securitate superioară într-un aspect sau altul decât alte cifruri. Acestea se numesc moduri de operare şi trebuie luate în calcul cu grijă la folosirea unui cifru pe blocuri într-un criptosistem.

Data Encryption Standard (DES) şi Advanced Encryption Standard (AES) sunt cifruri pe blocuri care sunt considerate standarde de criptografie de guvernul american (deşi DES a fost în cele din urmă retras după adoptarea AES). În ciuda decăderii ca standard oficial, DES (mai ales în varianta triple-DES, mult mai sigură) rămâne încă popular; este folosit într-o gamă largă de

- 1 -

aplicaţii, de la criptarea ATM la securitatea e-mail-urilor şi accesul la distanţă securizat. Multe alte cifruri pe blocuri au fost elaborate şi lansate, cu diverse calităţi. Multe au fost sparte.

DES ( Data Encryption Standard )

Standardul de Criptare a Datelor (în engleză Data Encryption Standard, DES) este un cifru (o metodă de criptare a informaţiei), selectat ca standard federal de procesare a informaţiilor în Statele Unite în 1976, şi care s-a bucurat ulterior de o largă utilizare pe plan internaţional. Algoritmul a fost controversat iniţial, având elemente secrete, lungimea cheii scurtă şi fiind bănuit că ascunde de fapt o portiţă pentru NSA. DES a fost analizat intens de către profesionalişti în domeniu şi a motivat înţelegerea cifrurilor bloc şi criptanaliza lor.

DES a fost aprobat ca standard federal în noiembrie 1976 şi publicat pe 15 ianuarie 1977 ca FIPS PUB 46, utilizarea sa fiind autorizată pentru toate datele care nu sunt secrete de stat. A fost reafirmat ca standard în 1983, 1988 (revizuit ca FIPS-46-1), 1993 (FIPS-46-2) şi încă o dată în 1998 (FIPS-46-3), ultima variantă recomandând "Triplu DES" . Despre DES se poate spune că a "iniţiat" studiul nemilitar şi dezvoltarea algoritmilor de criptare. În anii 1970 erau puţini criptografi, cu excepţia celor din organizaţii militare sau de inteligenţă, iar studiul academic al criptografiei nu era dezvoltat

Descriere

Figura 1 — Structura Feistel generală din DES

- 2 -

DES este cifrul bloc arhetip — un algoritm care ia un şir de lungime fixă de biţi de text normal şi îl transformă print-o serie de operaţii complexe într-un şir de biţi criptaţi de aceeaşi lungime. În cazul DES, mărimea blocului este de 64 biţi. DES foloseşte de asemenea şi o cheie pentru particularizarea transformării, astfel încât numai cei care cunosc cheia folosită să poată efectua decriptarea. Cheia este formată din 64 de biţi; totuşi, numai 56 dintre ei sunt folosiţi propriu-zis de algoritm. Opti biţi sunt utilizaţi ca biţi de paritate şi nu sunt necesari după acest test. Deci cheia efectivă are doar 56 de biţi, şi aşa este citată de obicei.

Ca şi alte cifruri bloc, DES nu este o cale sigură de criptare folosit de sine-stătător. El trebuie folosit într-un mod de operare. FIPS-81 specifică câteva feluri pentru utilizarea cu DES.

Structură generală

Structura generală a algoritmului apare în Figura 1: sunt 16 paşi identici de procesare, numiţi runde. Există şi câte o permutare iniţială şi finală, numite PI and PF, care sunt funcţii inverse (PI "anulează" acţiunea lui PF şi vice versa). PI şi PF nu au aproape nici o importanţă criptografică, dar au fost incluse pentru a facilita încărcarea şi descărcarea blocurilor folosind hardware-ul din anii 1970.

Înaintea rundelor principale, blocul este împărţit în două jumătăţi, de câte 32 de biţi, şi procesate alternativ; această alternare este cunoscută drept Schema Feistel. Structura Feistel asigură că criptarea şi decriptarea sunt procese foarte asemănătoare — singura dieferenţă este ordinea aplicării subcheilor - invers la decriptare. Restul algoritmului este identic. Acest lucru simplifică implementarea, în special cea hardware, deoarece nu e nevoie de algoritmi separaţi.Simbolul cu roşu denotă operaţia OR exclusiv (XOR). Funcţia F amestecă jumătate din bloc cu o subcheie. Rezultatului funcţiei F este combinat cu cealaltă jumătate de bloc, iar jumătăţile sunt interschimbate înaintea următoarei runde. După ultima rundă, jumătăţile nu sunt schimbate; aceasta este o trăsătură a structurii Feistel care face din criptare şi decriptare procese similare.

Funcţia Feistel (F)

Funcţia F, care apare în Figura 2, operează pe o jumătate de bloc (32 biţi) la un moment dat şi este formată din patru paşi:

Figura 2 — Funcţia Feistel (F) din DES1. Expansiune — jumătatea de bloc de 32 de biţi este extinsă la 48 de biţi folosind funcţia

de expansiune, notată E în diagramă, prin duplicarea unor biţi.

- 3 -

2. Amestecare — rezultatul este combinat cu o subcheie folosind operaţia XOR.

Şaisprezece subchei de 48 de biţi — una pentru fiecare rundă — sunt derivate din cheia principală folosind diversificarea cheilor (descrisă mai jos).

3. Substituţie — după amestecarea cu subcheia, blocul este divizat în opt bucăţi de 6 biţi fiecare înainte de procesarea folosind cutiilor S, sau cutii de substituţie. Fiecare din cele opt cutii S înlocuieşte cei şase biţi de intrare cu patru biţi conform unei transformări neliniare, oferită sub forma unui tabel de căutare. Cutiile S reprezintă securitatea lui DES — fără ele, cifrul ar fi liniar şi uşor de spart.

4. Permutare — în final, cele 32 de ieşiri din matricile S sunt rearanjate conform permutării fixe P.

Alternarea substituţiilor din matricile S şi permutarea biţilor folosind matricea P şi expansiunea E oferă ceea ce se numeşte "confuzie şi difuzie", un concept identificat de către Claude Shannon în anii 1940 ca fiind necesar unui cifru sigur şi practic în acelaşi timp.

Diversificarea cheilor

Figura 3 — Diversificarea cheilor în DES

Figura 3 ilustrează diversificarea cheilor pentru criptare — algoritmul care generează subcheile. Iniţial, 56 de biţi din cheia principală sunt selectaţi din cei 64 prin permutarea PC-1 — ceilalţi 8 biţi sunt ignoraţi sau folosiţi ca biţi de paritate. Cei 56 de biţi sunt apoi împărţiţi în două blocuri de 28 de biţi; fiecare jumătate este tratată ulterior separat. În runde succesive, ambele jumătăţi sunt rotate la stânga cu unul sau doi biţi (specificaţi pentru fiecare rundă), şi apoi sunt selectaţi cei 48 de biţi ai subcheii prin permutarea PC-2 — 24 de biţi din jumătatea stângă, şi 24 din cea dreaptă. Rotaţiile (notate cu "<<<" în diagramă) înseamnă că un set de biţi diferit este folosit în fiecare subcheie; fiecare bit este folosit în circa 14 din cele 16 chei.

Diversificarea cheilor pentru decriptare este similară — trebuie să se genereze subcheile în ordine inversă. Aşadar, rotaţiile sunt la dreapta, şi nu la stânga.

- 4 -

Deşi despre criptanaliza lui DES s-a publicat mai multă informaţie decât despre cea a oricărui alt cifru bloc, atacul cel mai practic rămâne cel prin forţă brută. Diferite proprietăţi criptanalitice minore sunt cunoscute, iar trei atacuri teoretice sunt posibile. Acestea au complexitatea mai mică decât cea a atacului prin forţă brută, dar numărul de texte necesare este nerealist şi de aceea nu sunt fezabile.

Proprietăţi criptanalitice minore

DES deţine proprietatea complementarităţii, adică

unde este complementul pe biţi al lui . denotă criptarea cu cheia . şi sunt textul normal şi, respectiv, textul criptat. Proprietatea complementarităţii înseamnă că munca unui atac prin formţă brută se înjumătăţeşte (un bit) sub prezumpţia unui text ales.

DES are, de asemenea, patru chei slabe. Criptarea (E) şi decriptarea (D) cu o cheie slabă au acelaşi efect (vezi involuţie):

sau echivalent,

Există şi şase perechi de chei semi-slabe. Criptarea cu o pereche de chei semi-slabe, , operează identic cu decriptarea cu o alta, :

sau echivalent,

Este uşor de evitat cheile slabe şi semi-slabe într-o implementare, fie prin testare explicită, fie prina alegerea aleatorie a cheilor; şansele de alegere a unei chei slabe sau semi-slabe sunt neglijabile. Aceste chei nu sunt în realitate mai slabe decât alte chei în nici un fel, pentru că nu avantajează nici un atac.

S-a dovedit că DES nu este un grup, sau mai precis, mulţimea {EK} (a tuturor cheilor posibile ) faţă de compunerea funcţiilor nu este grup, şi nici măcar "aproape" de a fi grup (Campbell şi Wiener, 1992). Aceasta a fost o întrebare pentru un timp, şi dacă aşa era cazul, ar fi fost posibil să se spargă DES, iar modalităţile de criptare multiple, precum Triplu DES nu ar fi mărit securitatea.

Este cunoscut faptul că securitatea criptografică maximă a lui DES este limitată la 64 de biţi, chiar şi când se aleg independent subcheile în locul derivării lor din cheia principală, care ar permite altfel o securitate de 768 de biţi.

- 5 -

3DES ( Triplu DES )

Schemă de principiu a funcţionării 3DES

În criptografie, 3DES, numit şi Triplu DES (în engleză Triple DES) este un cifru pe blocuri format pe baza DES, prin aplicarea acestuia de trei ori.

Algoritm

Când s-a descoperit că cheile pe 56 de biţi folosite de DES nu sunt suficiente pentru a proteja împotriva atacurilor cu forţă brută, 3DES a fost ales ca modalitate simplă de a mări spaţiul cheilor fără nevoia de a trece la un nou algoritm. Utilizarea a trei paşi este esenţială pentru a evita atacurile meet-in-the-middle care sunt eficiente împotriva criptării duble cu DES. Mulţimea funcţiilor de criptare DES cu toate cheile posibile nu formează cu operaţiunea de compunere a funcţiilor o structură matematică de grup; dacă ar fi fost aşa, construcţia 3DES ar fi fost echivalentă cu o operaţiune DES şi astfel, la fel de nesigură ca aceasta.Cea mai simplă variantă de 3DES funcţionează astfel: DES(k3;DES(k2;DES(k1;M))), unde M este blocul în clar iar k1, k2, şi k3 sunt cheile DES. Această variantă este cunoscută sub notaţia EEE deoarece toate cele trei operaţiuni efectuate cu cheile sunt criptări. Pentru a simplifica interoperabilitatea între DES şi 3DES, pasul din mijloc se înlocuieşte de obicei cu decriptarea (modul EDE): DES(k3;DES-

1(k2;DES(k1;M))) şi astfel o singură criptare DES cu cheia k poate fi reprezentată ca 3DES-EDE cu cheile k1 = k2 = k3 = k. Alegerea decriptării pentru pasul al doilea nu afectează securitatea algoritmului.

Securitatea

În general, 3DES cu trei chei diferite are o lungime a cheii de 168 de biţi (cu biţii de paritate, 192): trei chei DES pe 56 de biţi, dar, datorită atacurilor meet-in-the-middle securitatea efectivă pe care o furnizează este de doar 112 biţi. O variantă, numită 3DES cu două chei, foloseşte k1 = k3, reducând astfel lungimea cheii la 112 biţi şi lungimea de sticare la 128 de biţi. Totuşi, acest

- 6 -

mod de funcţionare este susceptibil la unele atacuri cu text clar ales sau cu text clar cunoscut şi astfel este considerat de NIST ca având securitate echivalentă cu doar 80 de biţi.

Cel mai eficient atac asupra 3DES cu trei chei necesită aproximativ 232 texte clare cunoscute, 2113

paşi, 290 criptări DES individuale, şi 288 vlocuri de stocare Acesta este un volum nepractic şi NIST consideră criptarea 3DES cu 3 chei utilizabilă până în 2030. Dacă atacatorul caută să descopere oricare din multiplele chei criptografice, există un atac eficient din punct de vedere spaţial care descoperă una din 228 chei, dacă se dau câteva texte clare alese pentru fiecare cheie, efectuând 284 operaţiuni de criptare.

AES(Advanced Encryption Standard)

AES (de la Advanced Encryption Standard - în limba engleză, Standard Avansat de Criptare), cunoscut şi sub numele de Rijndael, este un algoritm standardizat pentru criptarea simetrică, pe blocuri, folosit astăzi pe scară largă în aplicaţii şi adoptat ca standard de organizaţia guvernamentală americană NIST. Standardul oficializează algoritmul dezvoltat de doi criptografi belgieni, Joan Daemen şi Vincent Rijmen şi trimis la NIST pentru selecţie sub numele Rijndael.

Vincent Rijmen, coautor al algoritmului Rijndael

Deoarece DES devenise vulnerabil din cauza lungimii prea mici a cheii, NIST a recomandat utilizarea 3DES, un algoritm care constă în esenţă în aplicarea de trei ori a DES. Deşi 3DES s-a dovedit a fi un algoritm puternic, el este relativ lent în implementările software, motiv pentru care NIST a lansat în 1997 o cerere de propuneri pentru un algoritm care să-l înlocuiască. S-a pornit de la 21 de propuneri acceptate iniţial, apoi prin eliminări numărul lor a fost redus la 15, şi apoi la 5, din care a fost ales în cele din urmă algoritmul propus de doi criptografi belgieni, Joan Daemen şi Vincent Rijmen. La votarea finală, algoritmul, denumit de autorii săi Rijndael, a învins la vot patru alte propuneri, printre care şi algoritmul RC6, propus de o echipă de criptografi în care se afla şi reputatul informatician Ron Rivest.

Criteriile pe baza cărora au fost evaluate propunerile pentru AES au fost securitatea (rezistenţa la atacuri criptanalitice), costurile (eficienţa computaţională, complexitatea spaţială, precum şi licenţierea liberă şi gratuită) şi particularităţile algoritmului (flexibilitatea, simplitatea, şi uşurinţa de realizare a implementărilor atât software cât şi hardware).[3]

- 7 -

Algoritmul

În propunerea avansată NIST, cei doi autori ai algoritmului Rijndael au definit un algoritm de criptare pe blocuri în care lungimea blocului şi a cheii puteau fi independente, de 128 de biţi, 192 de biţi, sau 256 de biţi. Specificaţia AES standardizează toate cele trei dimensiuni posibile pentru lungimea cheii, dar restricţionează lungimea blocului la 128 de biţi. Astfel, intrarea şi ieşirea algoritmilor de criptare şi decriptare este un bloc de 128 de biţi. În publicaţia FIPS numărul 197, operaţiile AES sunt definite sub formă de operaţii pe matrice, unde atât cheia, cât şi blocul sunt scrise sub formă de matrice. La începutul rulării cifrului, blocul este copiat într-un tablou denumit stare (în engleză state), primii patru octeţi pe prima coloană, apoi următorii patru pe a doua coloană, şi tot aşa până la completarea tabloului.[5]

Algoritmul modifică la fiecare pas acest tablou de numere denumit state, şi îl furnizează apoi ca ieşire. Funcţionarea sa este descrisă de următorul pseudocod:

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end

Aici, Nb este numărul de coloane al stării, în varianta standardizată acesta fiind întotdeauna 4. Se observă din descrierea algoritmului că o anumită secvenţă este realizată iterativ, de un număr de Nr ori. Acest Nr depinde de lungimea cheii şi este 10, 12 sau 14, pentru chei pe 128, 192, respectiv 256 biţi.

Pasul SubBytes

La pasul SubBytes, fiecare octet din blocul state este înlocuit cu un altul, conform unui cifru cu substituţie

Pasul SubBytes este un cifru cu substituţie, fără punct fix, denumit Rijndael S-box, care rulează independent pe fiecare octet din state. Această transformare este neliniară şi face astfel întreg cifrul să fie neliniar, ceea ce îi conferă un nivel sporit de securitate.

- 8 -

Fiecare octet este calculat astfel:

unde bi este bitul corespunzător poziţiei i din cadrul octetului, iar ci este bitul corespunzător poziţiei i din octetul ce reprezintă valoarea hexazecimală 63, sau, pe biţi, 01100011. Maparea octeţilor se poate reţine într-un tabel, explicitat în FIPS PUB 197, în care este specificat rezultatul operaţiei de mai sus efectuată pe fiecare din cele 256 de valori posibile reprezentabile pe un octet.

Pasul ShiftRows

Pasul ShiftRows operează la nivel de rând al matricii de stare state. Pasul constă în simpla deplasare ciclică a octeţilor de pe rânduri, astfel: primul rând nu se deplasează; al doilea rând se deplasează la stânga cu o poziţie; al treilea rând se deplasează la stânga cu două poziţii; al patrulea se deplasează la stânga cu trei poziţii. Rezultatul acestui pas este că fiecare coloană din tabloul state rezultat este compusă din octeţi de pe fiecare coloană a stării iniţiale. Acesta este un aspect important, din cauză că tabloul state este populat iniţial pe coloane, iar paşii ulteriori, inclusiv AddRoundKey în care este folosită cheia de criptare, operaţiile se efectuează pe coloane.

Pasul MixColumns

În pasul MixColumns, fiecare coloană este înmulţită cu un polinom, notat în figură cu c(x)

În acest pas, fiecare coloană a tabloului de stare este considerată un polinom de gradul 4 peste corpul Galois . Fiecare coloană, tratată ca polinom, este înmulţită, modulo x4 + 1 cu polinomul a(x) = 3x3 + x2 + x + 2. Operaţia se poate scrie ca înmulţire de matrice astfel:[12]

unde sunt elementele de pe un vector coloană rezultate în urma înmulţirii, iar si sunt elementele de pe acelaşi vector înaintea aplicării pasului.

- 9 -

Rezultatul are proprietatea că fiecare element al său depinde de toate elementele de pe coloana stării dinaintea efectuării pasului. Combinat cu pasul ShiftRows, acest pas asigură că după câteva iteraţii, fiecare octet din stare depinde de fiecare octet din starea iniţială (tabloul populat cu octeţii mesajului în clar). Aceşti doi paşi, împreună, sunt principala sursă de difuzie în algoritmul Rijndael. Coeficienţii polinomului a(x) sunt toţi 1, 2 şi 3, din motive de performanţă, criptarea fiind mai eficientă atunci când coeficienţii sunt mici. La decriptare, coeficienţii pasului corespunzător acestuia sunt mai mari şi deci decriptarea este mai lentă decât criptarea. S-a luat această decizie pentru că unele din aplicaţiile în care urma să fie folosit algoritmul implică numai criptări, şi nu şi decriptări, deci criptarea este folosită mai des.

Pasul AddRoundKey şi planificarea cheilor

În pasul AddRoundKey, se efectuează o operaţie de sau exclusiv pe biţi între octeţii stării şi cei ai cheii de rundă

Pasul AddRoundKey este pasul în care este implicată cheia. El constă într-o simplă operaţie de „sau” exclusiv pe biţi între stare şi cheia de rundă (o cheie care este unică pentru fiecare iteraţie, cheie calculată pe baza cheii secrete). Operaţia de combinare cu cheia secretă este una extrem de simplă şi rapidă, dar algoritmul rămâne complex, din cauza complexităţii calculului cheilor de rundă (Key Schedule), precum şi a celorlalţi paşi ai algoritmului.

Cheia de rundă este calculată după algoritmul următor:

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk) begin word temp i = 0 while (i < Nk) w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]) i = i+1 end while i = Nk while (i < Nb * (Nr+1)] temp = w[i-1] if (i mod Nk = 0) temp = SubWord(RotWord(temp)) xor Rcon[i/Nk] else if (Nk > 6 and i mod Nk = 4) temp = SubWord(temp) end if w[i] = w[i-Nk] xor temp i = i + 1

- 10 -

end while end

Acest algoritm lucrează pe cheia algoritmului, de lungime Nk cuvinte de 4 octeţi (4, 6 sau 8,

conform standardului), populând un tabel de cuvinte, Nb fiind numărul de cuvinte al blocului (în versiunea standardizată, 4), iar Nr numărul de runde (iteraţii), dependent de lungimea cheii. Algoritmul de planificare a cheilor foloseşte transformarea SubWord, care este o substituţie a octeţilor identică cu cea din pasul SubBytes. RotWord este o rotaţie ciclică la stânga cu un octet a octeţilor dintr-un cuvânt. Cu Rcon[i] se notează în algoritm un cuvânt

format din octeţii . Operaţia de ridicare la putere este aici cea valabilă în corpul Galois .[16] Tabloul w conţine la finalul prelucrării cuvintele de pe coloanele cheilor de rundă, în ordinea în care urmează să fie aplicate.

Securitatea

Rijndael, ca şi toţi ceilalţi algoritmi ajunşi în etapa finală de selecţie pentru standardul AES, a fost revizuit de NSA şi, ca şi ceilalţi finalişti, este considerat suficient de sigur pentru a fi folosit la criptarea informaţiilor guvernamentale americane neclasificate. În iunie 2003, guvernul SUA a decis ca AES să poată fi folosit pentru informaţii clasificate. Până la nivelul SECRET, se pot folosi toate cele trei lungimi de cheie standardizate, 128, 192 şi 256 biţi. Informaţiile TOP SECRET (cel mai înalt nivel de clasificare) pot fi criptate doar cu chei pe 256 biţi.[17]

Atacul cel mai realizabil împotriva AES este îndreptat împotriva variantelor Rijndael cu număr redus de iteraţii. AES are 10 iteraţii la o cheie de 128 de biţi, 12 la cheie de 192 de biţi şi 14 la cheie de 256 de biţi. La nivelul anului 2008, cele mai cunoscute atacuri erau accesibile la 7, 8, respectiv 9 iteraţii pentru cele trei lungimi ale cheii.

RSA ( Rivest , Shamir, Adleman )

În criptografie, RSA este un algoritm criptografic cu chei publice, primul algoritm utilizat atât pentru criptare, cât şi pentru semnătura electronică. Algoritmul a fost dezvoltat în 1977 şi publicat în 1978 de Ron Rivest, Adi Shamir şi Leonard Adleman la MIT şi îşi trage numele de la iniţialele numelor celor trei autori.

Funcţionare

RSA este un algoritm de criptare pe blocuri. Aceasta înseamnă că atât textul clar cât şi cel cifrat sunt numere între 0 şi n-1, cu un n ales. Un mesaj de dimensiune mai mare decât este împărţit în segmente de lungime corespunzătoare, numite blocuri, care sunt cifrate rând pe rând. De asemenea, ca algoritm criptografic cu chei publice, funcţionează pe baza unei perechi de chei legate matematic între ele: o cheie publică, cunoscută de toată lumea, şi una secretă, necunoscută decât de deţinătorul acesteia.

Generarea cheilor

Perechea de chei se generează după următorii paşi:

1. Se generează două numere prime, de preferat mari, p şi q;

2. Se calculează şi

- 11 -

3. Se alege un întreg aleator e, 1 < e < φ astfel încât cmmdc(e, φ) = 1. Perechea (n, e) este

cheia publică. 4. Folosind algoritmul lui Euclid extins, se calculează întregul d, unicul cu proprietatea că

. (n, d) constituie cheia secretă.

Decizia cu privire la care dintre e şi d este cheia publică şi care este cea secretă este, din punct de vedere matematic, arbitrară, oricare dintre cele două numere poate juca oricare dintre roluri. În practică însă, pentru a mări viteza de criptare, şi întrucât dintre cele două numere e este cel ales arbitrar, e este cheia publică iar valoarea sa este aleasă un număr mic, de regulă 3, 17 sau 65537 (216+1). Aceasta conduce la un număr minim de înmulţiri, deci la o performanţă sporită, deoarece toate aceste numere au doar două cifre 1 în reprezentarea lor binară.

Criptarea şi decriptarea

Presupunând că mesajul clar este sub forma unui număr m, mai mic decât n, atunci mesajul cifrat, notat cu c este

unde e este cheia publică a destinatarului mesajului. Pentru a decripta mesajul, destinatarul îşi foloseşte cheia sa secretă d, care are proprietatea foarte importantă că:

Astfel, mesajul clar este recuperat calculând:

Oricine poate cripta mesaje cu cheia publică a destinatarului, dar numai acesta din urmă poate decripta, deoarece trebuie să folosească cheia sa secretă.

Algoritmul poate fi folosit şi pentru semnătura electronică, folosind cheile invers. Dacă o entitate criptează un mesaj (sau mai degrabă un hash al acestuia) cu cheia sa secretă şi ataşează rezultatul mesajului său, atunci oricine poate verifica, decriptând cu cheia publică a semnatarului şi comparând rezultatul cu mesajul clar (sau cu hash-ul acestuia), că într-adevăr acea entitate este autorul mesajului.

Demonstraţia formulei de decriptare

Formula de decriptare este valabilă, deoarece:

şi, fiindcă φ = (p − 1)(q − 1), atunci

şi

şi deci se poate scrie:

ed = k(p − 1) + 1 ed = h(q − 1) + 1

- 12 -

Dar, cum p este prim, şi deci prim cu m, conform micii teoreme a lui Fermat, rezultă că

. Dacă p nu este totuşi prim cu m, atunci înseamnă că m este multiplu al lui p, caz trivial în care m este congruent cu 0 modulo p, şi deci ridicat la orice putere este congruent cu 0 şi deci cu el însuşi.

Analog şi pentru q,

De aici, conform teoremei chinezeşti a resturilor, deoarece p şi q sunt numere prime, rezultă că

Performanţe în implementări

În general, deoarece se bazează pe o operaţie destul de costisitoare din punct de vedere al timpului de calcul şi al resurselor folosite, şi anume exponenţierea modulo n, viteza RSA este mult mai mică decât a algoritmilor de criptare cu cheie secretă. Bruce Schneier estima, pe baza unor calcule efectuate în anii 1990, că o implementare hardware de RSA este de 1000 de ori mai lentă decât o implementare DES, iar în software, RSA este de 100 de ori mai lent.

Există anumite modificări care pot aduce performanţe sporite, precum alegerea unui exponent de criptare mic, care astfel reduce calculele necesare criptării, rezolvând în acelaşi timp şi unele probleme de securitate. De asemenea, operaţiile cu cheia secretă pot fi accelerate pe baza teoremei chinezeşti a resturilor, dacă se stochează p, q şi unele rezultate intermediare, folosite des. Cu toate acestea, îmbunătăţirile nu sunt mari, iar ordinul de mărime al diferenţelor de performanţă faţă implementările algoritmilor cu cheie secretă rămân aceleaşi. De aceea, în sistemele de comunicaţie în timp real, în care viteza de criptare şi decriptare este esenţială (cum ar fi, de exemplu, aplicaţiile de streaming video sau audio securizate), RSA se foloseşte doar la începutul comunicaţiei, pentru a transmite cheia secretă de comunicaţie, care ulterior este folosită într-un algoritm cu cheie secretă, cum ar fi 3DES sau AES.

Securitatea

Problema decriptării unui mesaj criptat cu RSA este denumită problema RSA. Aceasta constă în obţinerea radicalului de ordin e modulo n, unde e şi n au proprietatea că n este produsul a două numere prime mari p şi q, iar e este prim cu produsul dintre p-1 şi q-1. În acest moment, cea mai eficientă metodă de a realiza aceasta este descompunerea în factori primi a lui n, şi obţinerea astfel a cheii secrete d pe baza lui e. Astfel, este demonstrat că dificultatea spargerii unui mesaj criptat cu RSA nu este mai dificilă decât problema factorizării. Nu a fost descoperită încă o altă soluţie generală a problemei RSA, dar nici nu s-a demonstrat matematic că nu există o altă soluţie .Cel mai mare număr factorizat vreodată prin acest algoritm, rulat în anul 2005, de către specialişti de la Agenţia Federală Germană pentru Securitatea Tehnologiei Informaţiei, are 200 de cifre zecimale, iar reprezentarea binară a factorilor primi obţinuţi ocupă 663 de biţi. Cheile de criptare RSA cele mai sigure au lungimi de peste 1024 de biţi.

- 13 -

Atacuri împotriva RSA

Deşi securitatea algoritmului RSA constă în legătura dintre acesta şi factorizarea întregilor, el trebuie folosit cu grijă în implementări, deoarece, în caz de folosire eronată, sistemele bazate pe RSA pot fi atacate în anumite maniere care ocolesc factorizarea efectivă a modulului, atacatorul ajungând să obţină mesajul clar sau cheia secretă.

Concluzie: In urma efectuarii lucrarii de laborator ne-am facut cunoscuti cu algoritmii de criptare in general de la aparitie – pina la criptarea moderna de astazi. Astfel prin criptografia modernă se intelege criptografia cu chei simetrice in care intra mai multi algoritmi asa ca DES, 3DES , AES si RSA cu care ne-am cunoscut mai sus si totodata am analizat avantajele si dezavantajele acestor algoritmi. Dupa parerea mea , eu cred ca fiecare algoritm are ceva specific in felul lui si la timpul de functionare a lui a fost bun , iar inlocuirea unuia cu altu aceasta duce la progresul tehnic si la o securitate mai sporita. Toate aceste schimbari au loc datorita cresterii numarului de utilizatori in retelele internet si a traficului mare de bani virtuali si nu in ultimul rind al rau-facatorilor (hakerii).

Un nou portal informaţional!

Dacă deţii informaţie interesantă si doreşti să te imparţi cu noi atunci scrie la adresa de e-mail : support@sursa.md

- 14 -