Utilizarea Criptosistemelor cu Chei Publice In Crearea Protocoalelor Criptografice

CUPRINS

CUPRINS

INTRODUCERE

I. ASPECTE DE SECURITATE IN REȚELE DE CALCULATOARE

1.1. Criptografia tradiționala

1.2. Cîteva principii practice de criptare

1.3. Rezolvarea problemelor legate de interceptarea, autentificarea si modificarea mesajelor

1.4. Schema de aplicare a unui algoritm simetric

1.5. Schema de aplicare a unui algoritm asimetric

1.6. Semnarea digitala a mesajelor ne criptate

1.7. Problema modificării mesajelor

1.8. Implicații sociale ale problemelor de securitate

1.9. Cîteva protocoale "sigure"

II. UTILIZAREA CRIPTOSISTEMELOR CU CHEI PUBLICE ÎN CREAREA PROTOCOALELOR CRIPTOGRAFICE

2.1. Sisteme de criptare cu chei publice exponențiale

2.2. Cifrul RIVEST- SHAMIR- ADLEMAN (RSA)

2.3. Aspecte de implementare a algoritmilor exponențiali

2.4. Atacuri criptoanalitice posibile la RSA

2.5. Spargerea algoritmului RSA

III. ALGORITMI CRIPTOGRAFICI

3.1. Algoritmul Cezar

3.2. Cifrul lui Polybius

Cifrul de substituție poligramică. Cifrul Playfair

3.3. Cifrul lui Vigenere

CONCLUZII

BIBLIOGRAFIE

INTRODUCERE

Criptografia este știința scrierilor secrete. Ea sta la baza multor servicii si mecanisme de securitate folosite in Internet, folosind metode matematice pentru transformarea datelor, in intenția de a ascunde conținutul lor sau de a le proteja împotriva modificării. Criptografia are o lunga istorie, confidențialitatea comunicării fiind o cerința a tuturor timpurilor. Daca ar trebui sa alegem un singur exemplu al criptografiei “clasice”, acesta ar fi “cifrul lui Cezar”, nu atat datorita celebrității împăratului roman de care se leagă folosirea lui, ci pentru ca principiul sau de baza, al substituției, s-a menționat nealterat aproape doua milenii.

Multa vreme, eforturile criptografilor au fost dirijate spre întărirea cifrurilor prin complicarea algoritmului, combinînd substituii si transpoziții aspra unor simboluri sau aspra unor blocuri. Istoria moderna a criptografiei cunoaște numerose inovații in aceasta privință. Doua sunt elementele ce au marcat insa cotitura semnificativa in dezvoltarea metodelor criptografice.

Primul este legat de dezvoltarea rețelelor de calculatoare, al căror stimulent extraordinar s-a manifestat atît prin presiunea exercitata de tot mai mulți utilizatori cat și prin potențarea gamei de instrumente folosite efectiv in execuția algoritmilor de cifrare. Utilizarea calculatoarelor electronice a permis folosirea unor chei de dimensiuni mai mari, sporindu-se astfel rezistenta la atacuri criptoanalitice. Cînd cheia secreta are dimensiune convenabila si este suficient de frecvent schimbata, devine practic imposibila spargerea cifrului, chiar daca se cunoaște algoritmul de cifrare. Pe aceasta idee se bazează si standardul american de cifrare a datelor – DES (Data Encryption Standard) – larg utilizat de guvernul SUA si de diverse companii internationale. Propus intr-o forma initiala de IBM in 1975, DES a rezistat evaluarii facute de “spargatorii de cifruri” de la U.S. National Security Agency (NSA), care au recomandat doar reproiectarea anumitor componente. DES a fost adoptat ca standard federal in 1977 si a fost folosit intens datorita performantelor de viteza atinse la cifrare (peste 100 milioane biti/secunda). Din pacate, nu se stie cu certitudine daca cei de la NSA sau de la vreo alta organizatie au reușit sau nu sa spargă DES. Experiența a arătat insa ca orice schema criptografica are o viata limitata si ca avansul tehnologic reduce, mai devreme sau mai tîrziu, securitatea furnizata de ea.

Al doilea moment important in evoluția criptografiei moderne l-a constituit adoptarea unui principiu diferit de acela al cifrării simetrice. Whitfield Diffide si Martin Hellman, cercetatori la Universitatea Stanford din California, prin articolul “New Directions in Criptografy”, publicat in 1976 in revista IEEE Tranactions on Information Theory, au pus bazele “criptografiei asimetrice” cu chei publice. In locul unei singure chei secrete, criptografia asimetrica foloseste doua chei diferite, una pentru cifrare, alta pentru descifrare. Deoarece este imposibila deducerea unei chei din cealaltă, una din chei este făcută publica, fiind pusa la îndemîna oricui dorește sa transmită un mesaj cifrat. Doar destinatarul, care deține cea de a doua cheie, poate descifra si utiliza mesajul. Tehnica cheilor publice poate fi folosita si pentru autentificarea mesajelor, fapt care i-a sporit popularitatea. Nu este, deci de mirare ca guvernul SUA a inițiat adoptarea unui standard de semnătura digitala bazat pe conceptul de cheie publica. Acest demers a generat controverse, soldate chiar cu acuze intre organizațiile implicate. Pana in decembrie 1990, Institutul National de Standarde si Tehnologie al SUA (NIST) recomanda pentru adoptare ca standard metoda RSA, prezenta deja in industrie. Dar noua luni mai tarziu, in august in 1991, NIST a avansat un cu totul alt algoritm, bazat pe o metoda cu chei publice, publicata de Taher El Gamal in 1986. Noua propunere denumita DSS (Digital Segnature Standard), a fost dezvoltata de NSA. Ea a dezamagit nu datorita performantelor, ci “gratie” autorului, care este nu doar proiectant, dar si spargator de cifruri, ceea ce a starnit, inevitabil, suspiciuni.

Un cifru se defineste ca transformarea unui mesaj clar sau text clar in mesaj cifrat sau criptograma. Procesul de trasformare a textului clar in text cifrat se numeste cifrare sau criptare, iar transformarea inversa, a criptogramei in text clar, are denumirea de descifrare sau decriptare. Atît cifrarea cat si descifrarea sunt controlate de către una sa mai multe chei criptografice. Criptanaliza studiază metodele de spargere a cifrurilor, adică de determinare a textului clar sau a cheii de cifrare din criptograma.

I. ASPECTE DE SECURITATE IN REȚELE DE CALCULATOARE

1.1. Criptografia tradiționala

Istoria criptografiei este lunga si pitoreasca. Se spune ca la dezvoltarea procedeelor de criptare (codificare) au contribuit: armata, corpurile diplomatice, persoanele care au tinut jurnale si indragostitii. Evident, dezvoltarea tehnicilor de criptare a constiuit o prioritate pentru organizatiile militare, care utilizau frecvent asemenea procedee. inainte de aparitia calculatoarelor, volumul mare de mesaje criptate sau transmise a fost gestionat de un numar mare de functionari "codori". Evident, tehnicile folosite erau limitate de capacitatea codorilor de realizare a transformarilor necesare si de insusirea de catre acestia a unor tehnici criptografice noi. Totusi, pericolul de capturare a codurilor de catre "inamici" facea necesara schimbarea periodica a metodei de criptare.

Modelul clasic de criptare presupune transformarea unui text sursa ("plain text") printr-o functie dependenta de o cheie ("key"), transformare in urma careia rezulta textul cifrat ("ciphertext"). inainte de aparitia retelelor de calculatoare, acesta era transmis printr-un curier sau prin radio. in cazul interceptarii mesajelor cifrate, ele nu puteau fi decodificate prea usor in absenta cheii de criptare. Uneori, "intrusii" puteau nu numai sa asculte canalele de comunicatie (intrusi pasivi), ci si sa inregistreze mesajele si sa le retransmita mai tarziu, sa introduca propriile mesaje sau sa modifice mesajele legitime inainte ca ele sa ajunga la receptor (intrus activ).

Domeniul care se ocupa de spargerea (decodificarea) cifrurilor se numeste criptanaliza ("cryptanalysis") iar conceperea cifrurilor (criptografia) si spargerea lor (criptanaliza) sunt cunoscute global sub numele de criptologie ("cryptology").

intr-o incercare de formalizare matematica a proceselor de criptare si decriptare, se pot folosi urmatoarele notatii: S – textul sursa, CK – functia de criptare, dependenta de o cheie K, R – codul rezultat si DK – functia de decriptare. Cu aceste notatii, criptarea este exprimata prin formula

R = CK(S) iar decriptarea – prin S = DK(R).

Se observa ca DK(CK(S)) = S.

O regula de baza in criptografie stabileste necesitatea cunoasterii metodei generale de criptare de catre orice criptanalist. Acest principiu are la baza constatarea ca pentru a inventa, testa si instala o noua metoda de criptare este necesara o cantitate prea mare de efort pentru ca acest procedeu sa fie practic. in consecinta, cel mai important element devine cheia de criptare.

Cheia consta intr-un sir de caractere care defineste / selecteaza una sau mai multe criptari potentiale. Spre deosebire de metoda generala, care, in mod traditional, se schimba doar la cativa ani, cheia putea fi schimbata oricat de des era necesar.

in concluzie, modelul de baza al criptarii foloseste o metoda generala cunoscuta, care este parametrizata cu o cheie secreta, ce poate fi schimbata usor. in mod paradoxal, publicarea algoritmului de criptare, prin faptul ca da posibilitatea unui numar mare de criptologi sa sparga sistemul, ii poate dovedi stabilitatea, in caz ca dupa cativa ani nici unul din specialistii care au incercat sa-l sparga nu a reusit.

Componenta secreta a criptarii este, in consecinta, cheia, a carei lungime devine foarte importanta. in mod evident, cu cat cheia este mai lunga lunga, cu atat elementele ei sunt mai greu de determinat. De exemplu, pentru o secventa de n cifre (0,…,9), exista 10n posibilitati de a o crea. Astfel, pentru determinarea unei secvente de 6 cifre ar trebui parcurse 1 milion de posibilitati. in cazul in care cheile ar contine litere, numarul de alternative creste fiindca in alfabet exista 26 de litere. Se poate deduce ca lungimea cheii produce cresterea exponentiala a volumului de munca al criptanalistului. O cheie care sa poata tine la distanta adversari profesionisti ar trebui sa aiba cel putin 256 de biti (cel putin 32 de cifre), in timp ce uzual se pot folosi chei de 64 de biti (in jur de 8 cifre).

Cand un criptanalist trebuie sa decodifice un text, el se confrunta cu una din urmatoarele probleme:

• problema textului cifrat ("ciphertext only problem"), cand are la dispozitie o cantitate de text cifrat si nici un fel de text sursa;

• problema textului sursa cunoscut ("known plaintext problem"), cand are la dispozitie un text sursa si textul cifrat corespunzator;

• problema textului sursa ales ("chosen plaintext problem"), daca poate cripta la alegere zone din textul sursa (poate afla criptarea unui anumit text).

in multe situatii, criptanalistul poate ghici unele parti din textul sursa, chiar daca teoretic s-ar gasi in situatia de a rezolva o problema de text cifrat. (De exemplu, initierea unei sesiuni de lucru intr-un sistem multiutilizator va contine uzual cuvantul "LOGIN".) De aceea, pentru a asigura securitatea, criptograful trebuie sa se asigure ca metoda propusa este sigura, chiar daca inamicul sau poate cripta cantitati arbitrare de text ales.

Exista doua metode traditionale de criptare: cifruri cu substitutie si cifruri cu transpozitie. Aceste tehnici de baza sunt folosite, in forme evoluate, si in sistemele moderne de criptare.

Cifrurile cu substitutie. intr-un asemenea cifru, fiecare litera sau grup de litere este inlocuit(a) cu o alta litera sau cu un grup de litere. Cel mai vechi exemplu este cifrul lui Cezar, prin care a devine D, b devine E, …, z devine C. Prin generalizare, alfabetul poate fi deplasat cu k litere in loc de 3. in acest caz, k devine cheia pentru metoda generala a alfabetelor deplasate circular.

O alta metoda de substitutie este inlocuirea fiecarei litere din textul sursa cu o anumita litera corespondenta. Sistemul se numeste substitutie monoalfabetica si are ca si cheie un sir de 26 de litere. Pentru o persoana neavizata, acest sistem ar putea fi considerat sigur fiindca incercarea tuturor celor 26! de chei posibile ar necesita unui calculator 1013 ani alocand 1msec pentru fiecare solutie. Totusi, folosind o cantitate foarte mica de text cifrat, cifrul va putea fi spart cu usurinta.

Abordarea de baza porneste de la proprietatile statistice ale limbajelor naturale. Cunoscand frecventa statistica a fiecarei litere si a fiecarui grup de doua sau trei litere (de exemplu, are litera sau grup de litere este inlocuit(a) cu o alta litera sau cu un grup de litere. Cel mai vechi exemplu este cifrul lui Cezar, prin care a devine D, b devine E, …, z devine C. Prin generalizare, alfabetul poate fi deplasat cu k litere in loc de 3. in acest caz, k devine cheia pentru metoda generala a alfabetelor deplasate circular.

O alta metoda de substitutie este inlocuirea fiecarei litere din textul sursa cu o anumita litera corespondenta. Sistemul se numeste substitutie monoalfabetica si are ca si cheie un sir de 26 de litere. Pentru o persoana neavizata, acest sistem ar putea fi considerat sigur fiindca incercarea tuturor celor 26! de chei posibile ar necesita unui calculator 1013 ani alocand 1msec pentru fiecare solutie. Totusi, folosind o cantitate foarte mica de text cifrat, cifrul va putea fi spart cu usurinta.

Abordarea de baza porneste de la proprietatile statistice ale limbajelor naturale. Cunoscand frecventa statistica a fiecarei litere si a fiecarui grup de doua sau trei litere (de exemplu, in limba romana: ce, ci, ge, gi, oa, ua etc.) intr-o anumita limba, numarul mare de alternative initiale se reduce considerabil. Un criptanalist va numara frecventele relative ale tuturor literelor in textul cifrat si va incerca sa faca asocierea cu literele a caror frecventa este cunoscuta. Apoi va cauta grupurile de litere, incercand sa coroboreze indiciile date de acestea cu cele furnizate de frecventele literelor.

O alta abordare, aplicabila daca exista informatii despre domeniul la care se refera textul, este de a ghici un cuvant sau o expresie probabila (de exemplu, "financiar" pentru un mesaj din contabilitate) si de a cauta corespondentul sau, folosind informatii despre literele repetate ale cuvantului si pozitiile lor relative. Abordarea se poate combina cu informațiile statistice legate de frecventele literelor.

Cifruri cu transpozitie. Spre deosebire de cifrurile cu substitutie, care pastreaza ordinea literelor din textul sursa dar le transforma, cifrurile cu transpozitie ("transposition ciphers") reordoneaza literele, fara a le "deghiza".

Un exemplu simplu este transpozitia pe coloane, in care textul sursa va fi scris litera cu litera si apoi citit pe coloane, in ordinea data de o anumita cheie. Ca si cheie se poate alege un cuvant cu litere distincte, de o lungime egala cu numarul de coloane folosite in cifru. Ordinea alfabetica a literelor din cuvantul cheie va da ordinea in care se vor citi coloanele.

Spargerea unui cifru cu transpozitie incepe cu verificarea daca acesta este intr-adevar de acest tip prin calcularea frecventelor literelor si compararea acestora cu statisticile cunoscute. Daca aceste valori coincid, se deduce ca fiecare litera este "ea insasi", deci este vorba de un cifru cu transpozitie.

Urmatorul pas este emiterea unei presupuneri in legatura cu numarul de coloane. Acesta se poate deduce pe baza unui cuvant sau expresii ghicite ca facand parte din text. Considerand sintagma "saprezinte", cu grupurile de litere (luate pe coloane) "si", "an", "pt", "re", se poate deduce numarul de litere care le separa, deci numarul de coloane. Notam in continuare cu k acest numar de coloane.

Pentru a descoperi modul de ordonare a coloanelor, daca k este mic, se pot considera toate posibilitatile de grupare a cate doua coloane (in numar de k(k-1) ). Se verifica daca ele formeaza impreuna un text corect numarand frecventele literelor si comparandu-le cu cele statistice. Perechea cu cea mai buna potrivire se considera corect pozitionata. Apoi se incearca, dupa acelasi principiu, determinarea coloanei succesoare perechii din coloanele ramase iar apoi – a coloanei predecesoare. in urma acestor operatii, exista sanse mari ca textul sa devina recognoscibil.

Unele proceduri de criptare accepta blocuri de lungime fixa la intrare si genereaza tot un bloc de lungime fixa. Aceste cifruri pot fi descrise complet prin lista care defineste ordinea in care caracterele vor fi trimise la iesire (sirul pozitiilor din textul de intrare pentru fiecare caracter din succesiunea generata).

Problema construirii unui cifru imposibil de spart a preocupat indelung pe criptanalisti; ei au dat o rezolvare teoretica simpla inca de acum cateva decenii dar metoda nu s-a dovedit fiabila din punct de vedere practic, dupa cum se va vedea in continuare.

Tehnica propusa presupune alegerea unui sir aleator de biti pe post de cheie si aducerea textului sursa in forma unei succesiuni de biti prin inlocuirea fiecarui caracter cu codul sau ASCII. Apoi se aplica o operatie logica – de tip Sau exclusiv (operatia inversa echivalentei: 0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1, 1 xor 1 = 0) – intre cele doua siruri de biti. Textul cifrat rezultat nu poate fi spart pentru ca nu exista indicii asupra textului sursa si nici textul cifrat nu ofera criptanalistului informatii. Pentru un esantion de text cifrat suficient de mare, orice litera sau grup de litere (diftong, triftong) va aparea la fel de des.

Acest procedeu este cunoscut sub numele de metoda cheilor acoperitoare. Desi este perfecta din punct de vedere teoretic, metoda are, din pacate, cateva dezavantaje practice:

• cheia nu poate fi memorata, astfel incat transmitatorul si receptorul sa poarte cate o copie scrisa a ei fiindca in caz ca ar fi "capturati", adversarul ar obtine cheia;

• cantitatea totala de date care poate fi transmisa este determinata de dimensiunea cheii disponibile;

• o nesincronizare a transmitatorului si receptorului care genereaza o pierdere sau o inserare de caractere poate compromite intreaga transmisie fiindca toate datele ulterioare incidentului vor aparea ca eronate.

1.2. Cîteva principii practice de criptare

Se recomanda ca informațiile criptate sa contina informatii redundante, adica informatii care nu sunt necesare pentru intelegerea mesajului. Acest principiu constituie o protectie impotriva "intrusilor activi" care incearca trimiterea unor mesaje fictive in locul celor reale, folosind structura de mesaj originala si date eronate. Astfel, o lista de comenzi de produse ale unor clienti ar putea fi inlocuita, de catre o persoana rau-voitoare care cunoaste structura comenzilor, cu o lista generata aleator, pornind de la o lista partiala de nume de clienti. Daca insa mesajele criptate ale comenzilor contin, in afara informatiei utile, zone de informatii redundante, atunci este mult mai putin probabil ca mesajele generate aleator sa contina comenzi corecte.

Pe de alta parte, introducerea de informatie aleatoare poate usura spargerea mesajelor de catre criptanalisti fiindca acestia vor putea distinge mai usor mesajele valide de cele invalide (se simplifica spargerea sistemului de catre intrusii pasivi). De aceea, se recomanda construirea aleatoare a secventelor redundante.

Un alt principiu important urmareste impiedicarea intrusilor activi de a retransmite mesaje vechi ca fiind actuale; in acest scop, se folosesc marcaje numite amprente de timp.

1.3. Rezolvarea problemelor legate de interceptarea, autentificarea si modificarea mesajelor

Avand in vedere faptul ca transmisia de date in Internet este neprotejata, a aparut necesitatea dezvoltarii tehnicilor de criptare in directia automatizarii acestora si a implementării lor in retele de calculatoare. Astfel, utilizarea unor algoritmi pentru criptarea informatiilor transmise va deveni principalul mijloc de rezolvare a problemelor de interceptare in retele.

in descrierea unei transmisii de date prin rețea se obisnuieste sa se numeasca generic "mesaj" un ansamblu de date trimis de un "emitator" unui "receptor". Printr-o metoda de criptare, mesajele vor fi transformate, pe baza unei chei de criptare, astfel incat sa poata fi intelese doar de destinatar.

Unul din principiile mai recent aparute in criptanaliza consta in utilizarea unei alte chei pentru decodificarea mesajului decat cea folosita la codificare; aceasta tehnica este mai eficienta dar complica putin procedeul general si de aceea se prefera cand criptarea / decriptarea se realizeaza automat. Evident, dimensiunea unei chei de criptare (exprimate in general in biti) este o masura a nivelului de securitate dat de acea cheie, ea indicand rezistenta mesajului cifrat la incercarile de descifrare de catre cineva care nu detine cheia de descifrare potrivita.

Principiile de criptare din algoritmii cu cheie secreta au evoluat odata cu aparitia calculatoarelor; ele continua insa sa se bazeze pe metodele traditionale, cum ar fi transpozitia si substitutia. Algoritmii cu cheie secreta sunt caracterizati de faptul ca folosesc aceeasi cheie atat in procesul de criptare, cat si in cel de decriptare (vezi figura de mai jos). Din acest motiv, acesti algoritmi mai sunt cunoscuti sub numele de algoritmi simetrici; pentru aplicarea lor este necesar ca inaintea codificarii / decodificarii, atat emitatorul cat si receptorul sa posede deja cheia respectiva. in mod evident, cheia care caracterizeaza acesti algoritmi trebuie sa fie secreta.

Principalul dezavantaj al algoritmilor simetrici consta in faptul ca impun un schimb de chei private inainte de a se incepe transmisia de date. Altfel spus, pentru a putea fi utilizati, este necesar un canal cu transmisie protejata pentru a putea fi transmise cheile de criptare / decriptare.

1.4. Schema de aplicare a unui algoritm simetric

Ulterior, vor aparea si algoritmi cu cheie publica, caracterizati prin faptul ca criptarea si decriptarea folosesc chei diferite (vezi figura de mai jos). Aceasta caracteristica a dat algoritmilor cu cheie publica si numele de algoritmi asimetrici. in acest caz, una dintre chei poate fi publica (general cunoscuta – poate fi distribuita oricui) iar cealalta va trebui sa privata / secreta (cunoscuta doar de cel care o foloseste). Fiecare dintre aceste chei poate cripta mesajul, dar un mesaj criptat cu o anumita cheie nu poate fi decriptat decat cu cheia sa pereche.

Astfel, in cazul utilizarii unui algoritm asimetric in comunicarea dintre un emitator si un receptor, fiecare dintre acestia va detine cate o pereche de chei – publica si privata. Emitatorul poate cripta mesajul cu cheia publica a receptorului, astfel incat doar acesta sa poata decripta mesajul cu cheia sa privata. in cazul unui raspuns, receptorul va utiliza cheia publica a emitatorului astfel incat decriptarea sa se poata face exclusiv de catre emitator (cu cheia sa pereche, privata).

Cheile algoritmilor asimetrici sunt obtinute pe baza unei formule matematice din algebra numerelor mari, pentru numere prime intre ele, iar din valoarea unei chei nu poate fi dedusa valoarea cheii asociate. Remarcam faptul ca aplicarea in informatica a calculelor modulo numere prime s-a dovedit extrem de benefica pentru multi algoritmi moderni.

1.5. Schema de aplicare a unui algoritm asimetric

Traditional, criptografii foloseau algoritmi simpli asociati cu chei de securitate foarte lungi. Azi se urmareste crearea unor algoritmi de criptare atat de complecsi incat sa fie practic ireversibili, chiar daca un criptanalist achizitioneaza cantitati foarte mari de text cifrat.

O alta caracteristica a criptografiei moderne consta in automatizarea tehnicilor clasice, prin folosirea unor dispozitive special concepute. Transpozitiile si substitutiile vor fi implementate cu circuite simple, de viteza mare, care vor fi conectate in cascada astfel incat dependenta iesirii de intrare devine extrem de complicata si dificil de descoperit.

in 1977, guvernul SUA a adoptat ca standard oficial pentru informațiile nesecrete un cifru produs si dezvoltat de IBM, numit DES (Data Encryption System), care a fost larg adoptat in industrie. DES este cel mai popular algoritm cu cheie secreta; el continua sa stea la baza unor sisteme folosite in mod curent. DES foloseste (uzual) o cheie de 56 de biti; aceasta a fost in cele din urma adoptata in locul uneia de 128 de biti, neagreata de NSA (National Security Agency), agentia "spargatoare de coduri a guvernului", care dorea suprematia in domeniul criptografic.

Din 1977, cercetatorii in criptografie au incercat sa proiecteze masini pentru a sparge DES. Prima asemenea masina (1977) a fost conceputa de Diffie si Hellman, avea nevoie de mai putin de o zi iar costul ei a fost estimat la 20 de milioane de dolari. Dupa aproape 2 decenii, costul unei astfel de masini a ajuns la 1 milion de dolari iar timpul necesar spargerii codului a scazut la 4 ore. Ulterior, s-au dezvoltat si alte metode, cum ar fi folosirea unui cip DES incorporat (loteria chinezeasca).

in scopul decriptarii s-ar mai putea folosi mecanisme soft specifice (cum ar fi algoritmul asimetric Diffie-Hellman) si resursele libere ale unor calculatoare cu destinatie universala. Astfel, s-a demonstrat ca rularea pe mai multe calculatoare a unor programe distribuite de criptare (uzual, pe un numar mare de masini, de ordinul miilor sau chiar zecilor de mii) creste considerabil eficienta procesului de decriptare.

Un alt cifru renumit este IDEA (International Data Encryption Algorithm), realizat de doi cercetatori la Politehnica Federala din Zьrich (ETHZ). Acest algoritm foloseste o cheie de 128 de biti si este inspirat din metodele anterioare – DES si cele imaginate pentru spargerea DES.

Un alt algoritm performant a fost descoperit de un grup de cercetatori de la MIT – Ronald Rivest, Adi Shamir, Leonard Adelman – si s-a numit cu initialele creatorilor lui: RSA. Algoritmul de criptare RSA foloseste o cheie publica.

Se observa ca utilizarea unor astfel de algoritmi de criptare a datelor asigura transmisii confidentiale de date in retele neprotejate, rezolvand problema interceptarii. De fapt, riscul de interceptare / modificare nu dispare cu totul, din cauza ca orice mesaj criptat poate fi in general decriptat fara a detine cheia corespunzatoare, daca se dispune de suficiente resurse materiale si de timp.

Evident, dimensiuni variate ale cheii asigura diferite grade de confidentialitate iar perioada de timp necesara pentru decriptare poate fi prevazuta in functie de marimea cheii utilizate. Totusi, daca procesul de decriptare este lent, este posibil ca in momentul in care s-ar obtine datele dorite, acestea sa nu mai fie actuale sau utile.

Timpul de decriptare depinde in mod natural si de puterea procesoarelor utilizate in acest scop, astfel incat utilizarea distribuita a unui foarte mare numar de procesoare poate duce la o micsorare considerabila a timpului necesar. Din acest motiv, pentru transmisii de date in care este necesara o confidentialitate strica se utilizeaza chei de dimensiuni mult mai mari, chiar pentru algoritmul DES (de 256, 512, 1024 si chiar 2048 sau 4096 de biti), stiut fiind ca timpul necesar decriptarii creste exponential cu dimensiunea cheii de criptare / decriptare.

Pentru utilizatorii obisnuiti ai Internet-ului, cei mai convenabili algoritmi de criptare sunt cei cu cheie publica fiindca folosirea lor nu implica schimbul preliminar de chei pe canale de transmisie protejate, ca in cazul algoritmilor cu cheie secreta. Cheia publica poate fi distribuita fara restrictii pe intranet (reteaua locala) sau Internet, iar mesajele criptate cu aceasta cheie de un emitator vor putea fi decriptate numai utilizand cheia privata, care este detinuta exclusiv de catre destinatar. Astfel, nici macar expeditorul nu ar putea realiza decriptarea mesajului trimis.

1.6. Semnarea digitala a mesajelor ne criptate

Practic, pentru o identificare cat mai riguroasa a expeditorului se utilizeaza un sistem complex, bazat pe certificare, in care fiecare utilizator detine un certificat (ce are atasata o cheie publica si o cheie privata, secreta). Acesta este emis de o autoritate de certificare recunoscuta, in urma examinarii, pe baza de acte, a identitatii reale a persoanei. in momentul in care se doreste identificarea unei persoane, o cautare in baza de date a organizatiei respective va indica indentitatea expeditorului (pe baza cheii publice a acestuia, care este unica in lume).

Acest sistem este implementat sub forma unei structuri in care fiecare autoritate de certificare poate imputernici la randul ei alte organizatii sa emita certificate de autentificare, astfel incat originea unui certificat poate fi verificata in mod complet testand validitatea certificatului, apoi validitatea certificatului detinut de organizatia care a emis certificatului respectiv, si asa mai departe.

Sistemul de certificate digitale este utilizat nu numai pentru protejarea comunicatiilor, ci si pentru certificarea originii programelor. Astfel, prin folosirea unei criptari a programului de instalare cu cheia publica a firmei producatoare, utilizatorul poate verifica relativ usor ca acel program a fost creat intr-adevar de o anumita firma si pentru a decide daca sa instaleze sau nu programul. Aceasta este practic cea mai buna solutie de rezolvare a problemei rularii de programe / coduri daunatoare, enuntata la inceputul acestui capitol.

1.7. Problema modificării mesajelor

Pentru a preveni modificarea unui mesaj, se utilizeaza o tehnica specifica, denumita tehnica hash (sau a rezumatului), care permite construirea unui cod de identificare a datelor transmise, numit "rezumatul datelor". Principiile de baza ale tehnicii hash se aplica in numeroase domenii ale informaticii. Rezumatul unui mesaj se construieste prin aplicarea, in sens unic ("unisens"), a unei functii de transformare (functie "hash") intr-o secventa de biti – de lungime mare, pentru a fi dificil "spart". Sensul unic de transformare asigura faptul ca nu se pot deduce datele de intrare pe baza datelor de iesire.

Datele ce trebuie transmise sunt utilizate ca si date de intrare, obtinandu-se astfel o valoarea de transformare ("hash value"). Daca datele in tranzit sunt modificate, la destinatie se va obtine o alta valoarea de transformare, ceea ce va indica falsificarea datelor.

Valoarea de transformare este in general criptata ulterior prin utilizarea aceleiasi chei secrete ca si pentru criptarea datelor transmise. Astfel, se formeaza o "semnatura digitala" a datelor, care nu mai pot fi modificate fara ca acest lucru sa fie depistat.

Cateva protocoale "sigure"

1.8. Implicații sociale ale problemelor de securitate

Din motive strategice lesne de inteles, dezvoltarea tehnicilor criptografice este o problema delicata si in general politicile guvernamentale incearca sa tina sub control acest domeniu. Evident ca aceasta abordare nu este pe placul cercetatorilor care urmaresc evolutia algoritmilor in primul rand din ratiuni stiintifice si nici al publicului larg, in masura in care s-ar leza libertatile individuale.

Un caz renumit de reactie guvernamentala negativa la distribuirea unui soft criptografic, dezbatut in cele din urma instanta juridica, este cel al sistemului de posta electronica criptata Pretty Good Privacy, creat de Phil Zimmerman si distribuit pe Internet.

in unele tari (de exemplu, Franta), criptografia neguvernamentala este interzisa, cu exceptia cazurilor in care guvernul primeste toate cheile utilizate. De asemenea, interceptarile guvernamentale ale comunicatiilor private s-au practicat pe scara destul de extinsa. De exemplu, guvernul SUA a propus o tehnica de criptare a viitoarelor telefoane digitale care include o caracteristica speciala ce ar permite institutiilor autorizate (si care detin un ordin judecatoresc in acest sens) interceptarea si decriptarea oricarui apel telefonic din SUA. Acest subiect a iscat numeroase discutii contradictorii atat din punct de vedere din punct de vedere tehnologic (au fost propuse chiar metode de contracarare a procedeului), cat si juridic fiindca, pe de o parte, ar putea fi lezate libertatile individuale iar, pe de alta parte, s-ar putea asigura depistarea unor actiuni antisociale.

1.9. Cîteva protocoale "sigure"

Pentru a se asigura aplicarea metodelor de criptare si autentificare anterior descrise, au fost dezvoltate sisteme specifice de transmisii de date, bazate pe un transfer securizat al datelor.

Secured Socket Layer este un sistem dezvoltat de firma Netscape Communications care asigura criptarea pentru comunicarile realizate intre doua orice calculatoare din Internet prin intermediul protocolului universal folosit – TCP/IP. SSL se bazeaza pe criptarea cu cheie publica si functioneaza in doua etape: intr-o prima etapa se stabileste o cheie speciala de sesiune (transmisa intr-o forma criptata folosind cheia publica); aceasta cheie va fi utilizata in cea de a doua faza pentru o criptare rapida a datelor.

SSL asigura:

• autentificarea serverului pe baza certificatelor digitale (care descurajeaza impostorii);

• confidentialitatea transmisiilor (prin criptare);

• integritatea datelor transmise (prin coduri de verificare).

Un alt protocol de transmitere securizata a datelor este SHTTP – Secured HyperText Transfer Protocol, care constituie o varianta "sigura" a protocolului nativ de transfer al paginilor web – HTTP. SHTTP a fost dezvoltat de asociatia CommerceNet si asigura criptarea documentelor web transmise, utilizarea semnaturilor digitale si a unui cod de autentificare pentru integritatea mesajelor.

În mod evident, transferul protejat al datelor in procesul de navigare pe web este de mare interes in comertul electronic si permite realizarea de tranzactii financiare confidentiale si operatii comerciale pe cale electronica.

Implementari similare au fost dezvoltate si pentru sistemele de posta electronica: S/MIME sau PGP/MIME.

II. UTILIZAREA CRIPTOSISTEMELOR CU CHEI PUBLICE ÎN CREAREA PROTOCOALELOR CRIPTOGRAFICE

2.1. Sisteme de criptare cu chei publice exponențiale

Sistemele criptografice cu chei publice sunt de tip asimetric. Ele au fost dezvoltate cu precădere în ultimii ani, pornind de la lucrările de referință ale lui Diffie și Hellman. Ideea care stă la baza acestui concept constă în faptul că procedura (cheia) de cifrare este făcută publică de către fiecare utilizator și poate fi folosită de toți ceilalți utilizatori pentru cifrarea mesajelor ce îi sunt adresate. În schimb procedura (cheia) de descifrare, diferă de prima, – de unde atributul de sistem asimetric – este ținută secretă. Dacă notăm cu {M} mulțimea mesajelor, {C} mulțimea criptogramelor, E – procedura de cifrare și D – procedura de decifrare, un criptosistem cu chei publice trebuie să satisfacă următoarele cerințe:

dacă C = E(M), atunci M = D(C) sau D(C(M)) = M, indiferent de M {M} ;

E și D sunt ușor și rapid aplicabile ;

Dezvăluirea publică a lui E nu trebuie să compromită pe D, ceea ce înseamnă că obținerea lui D din E este matematic imposibilă sau presupune un consum prohibitiv de resurse.

Metoda propusă permite comunicații sigure între utilizatori care nu au stabilit contacte prealabile. De exemplu dacă utilizatorul A dorește să transmită un mesaj confidențial utilizatorului B, A va căuta în fișierul public EB și va transmite la B : C = EB (M). Conform proprietății a treia, B este singurul utilizator care știe să descifreze criptograma C aplicînd DB ținută secretă.

În plus, pentru ridicarea gradului de securitate al transmisiei, Diffie și Hellman propun ca E și D să îndeplinească și următoarea proprietate adițională:

dacă S = D(M), atunci M = E(S) sau E(D(M)) = M pentru oricare M {M}.

În funcționarea sistemelor cu chei publice este necesar un sistem de generare, circulație și autentificare a cheilor folosite de utilizatori. Să ne imaginăm situația cînd o persoana – să zicem Vlad – dorește să se dea drept altcineva ? Dan – și vrea să semneze în fals în numele lui Dan; falsificatorul (Vlad) poate face acest lucru ușor, generîndu-și propria sa pereche de chei și punînd-o pe cea publica în fișierul public, în locul celei autentice a lui Dan. Documente semnate de Vlad cu cheia sa secretă vor fi verificate cu cheia publică ce pare a fi a lui Dan și orice persoană se va înșela de autenticitatea documentelor semnate în numele lui Dan.

Problema fundamentală este deci aceea a încrederii absolute în cheile publice, cele cu care se face verificarea semnăturilor digitale. Acestea trebuie sa fie disponibile în rețea, astfel ca orice client să poată obține cheia publică a unui emitent de document semnat. În acest context, soluția tehnică există: crearea unei infrastructuri internaționale, bazată pe Autorități de Certificare (Certification Authority- CA), care să permită obținerea cu ușurință si într-o maniera sigura a cheilor publice ale persoanelor cu care se dorește să se comunice prin Internet. Aceste autorități urmează să distribuie, la cerere, certificate de chei autentificate.

Un certificat de cheie publică este o structura de date folosită pentru a se putea asocia, în mod sigur, o cheie publică cu un utilizator. Inevitabil, pot exista mai multe autorități de certificare, pe criterii de interes și naționale. Ca urmare, a fost necesar ca ISO să definească, în cadrul standardului X.509, protocoalele de autentificare în rețea și, în special, structura de certificate de chei publice. Fiecare utilizator dispune de un nume distinct, atribuit de către o CA sigură. Aceasta emite persoanei și un certificat ce conține, în principal, numele și cheia publică. În structura certificatului exista următoarele cîmpuri:

– versiunea permite să se facă distincție între versiuni succesive ale formatelor de certificat, identificînd structura acestuia;

– numărul serial identifică în mod unic certificatul, între cele emise de aceeași CA;

– algoritmul de semnătură identifică algoritmul folosit pentru calcularea semnăturii digitale la acel certificat, împreună cu parametrii necesari (de exemplu RSA-MD5);

– emitent conține numele CA care a creat certificatul, garantînd pentru legătura corecta între cheie publică și subiect;

– valabilitatea cuprinde intervalul de timp – data de început și cea de sfîrșit – în care certificatul este valabil;

– subiect conține numele utilizatorului care reprezintă subiectul certificării, proprietarul cheii publice cuprinse în certificat;

– cheie publică Subiect conține cheia publică a subiectului proprietar al certificatului;

– semnătura conține semnătura digitala a certificatului, aplicata de către CA emitenta, folosind cheia să privata; ea poate fi verificata oriunde, folosind cheia publică a autorității emitente, lucru care creează siguranța privind autenticitatea cheii.

Obținerea cheii publice a unui utilizator Subiect consta în validarea semnăturii digitale a certificatului acestuia, care se face cu cheia publică a CA-ului emitent. Însă obținerea cheii publice a CA-ului emitent este o problema similara de validare a certificatului acestuia. Ca urmare, procesul de validare a certificatelor este recursiv și se bazează pe un arbore de certificare.

Să presupunem ca utilizatorul Ana a primit un document semnat de la un alt utilizator, Dan, și dorește verificarea autenticității documentului. Mai întîi, Ana trebuie să obțină cheia publică (certificatul) lui Dan. Apoi, se verifică autenticitatea certificatului. Acest lucru este simplu dacă cei doi folosesc același CA. Ana verifica simplu semnătura autorității (CA) asupra certificatului lui Dan.

Lucrurile se complică în cazul în care cei doi folosesc autorități CA diferite pentru emiterea certificatelor lor. Să imaginăm o ierarhie (arbore) de certificare, în care fiecare CA certifică alte CA-uri și utilizatorii proprii. În rădăcină exista o autoritate master. Fiecare CA are un certificat propriu, semnat de CA-ul de deasupra să. În exemplul considerat, certificatul Anei este certificat de CA1 iar al lui Dan de către CA2. Ana cunoaște cheia publică a autorității sale, CA1. CA3 are un certificat semnat de CA1 , astfel ca Ana îl poate verifica. CA4 are certificatul semnat de CA3 iar CA5 este emis și semnat de CA4 . Și certificatul lui Dan este semnat și emis de către CA4 .

Mutîndu-se în sus în arborele de certificare către un punct comun, în acest caz CA4, și apoi coborînd către Dan, Ana poate verifica fiecare certificat de CA parcurs și, în final, autenticitatea certificatului lui Dan.

Certificatele pot fi memorate în baze de date în diferite puncte din lume. Ele pot fi schimbate între utilizatorii care comunica. Atunci cînd un certificat expiră, el trebuie șters din directoarele corespunzătoare, însă autoritatea CA emitentă trebuie să mențină o copie a certificatului. De asemenea, un certificat poate fi revocat fie datorită compromiterii cheii utilizatorului, a cheii CA-ului emitent său datorită faptului ca CA-ul nu mai dorește certificarea acelui utilizator. Fiecare CA trebuie să dispună de o listă de certificate revocate dar încă neexpirate. Daca, de exemplu, Ana primește un certificat, ea trebuie să verifice, mai întîi, ca acesta nu este revocat, fie într-o baza de date de certificate revocate din rețea fie într-o lista locală.

În concluzie, atunci cînd un utilizator, Ana, dorește să autentifice un document semnat de un alt utilizator, Dan, Ana trebuie mai întîi să apeleze la o bază de date pentru a obține ceea ce se numește o cale de autentificare, adică toate certificatele corespunzătoare caii din arbore, de la Ana la Dan, inclusiv certificatul lui Dan. Folosind această cale de certificare, se poate autentifica documentul (eventual e-mail) primit de către Ana de la Dan.

Valoarea S este numită semnătură digitală și reprezintă o metodă de autentificare reciprocă. În timp ce B poate fi sigur că mesajul recepționat a venit de la adevăratul A, prin semnarea mesajelor sale, A poate fi sigur că nimeni nu va putea să-i atribuie un mesaj fals. Utilizatorul A poate semna mesajul către B astfel:

S = DA(M)

și apoi trimite criptograma:

C = EB(S).

În aceste condiții numai B poate recunoaște pe S din C calculînd:

DB(C) = DB(EB(S)).

Apoi mesajul se obține calculînd:

EA(S) = EA(DA(M)) = M.

Daca însa se dorește semnarea digitala (electronica) a datelor în vederea verificării autenticității, datele sunt prelucrate astfel:

[1] Documentul M este cifrat cu cheia privata a emițătorului, care astfel semnează; în exemplul nostru este vorba de utilizatorul Dan care furnizează, prin intermediul unui card, cheia sa secretă, PRIVDan.

[2] Documentul este trimis la receptor;

[3] Receptorul verifica semnătura prin decriptarea documentului cu cheia publică a emițătorului.

O cheie criptografica este, de fapt, un fișier. Cheia privata "stă" pe calculatorul utilizatorului, pe o discheta personală sau pe un card. În ceea ce privește cheia publică, se pot face nenumărate copii care pot fi distribuite oriunde. Însă este nevoie de amîndouă, ele fiind puternic legate una de alta. Algoritmii de criptare cu cheie publică prezintă o cripto-complexitate foarte mare bazîndu-se, în general, pe operații matematice complexe, cu numere întregi foarte mari (sute de cifre zecimale sau mii de biți), ceea ce conferă o tărie deosebita acestor metode de cifrare.

Protocolul de semnătură electronică satisface mai bine condițiile prezentate anterior:

1. semnătura este autentică deoarece se verifică numai cu cheia publică a emițătorului;

2. semnătura este ne-falsificabilă deoarece numai emițătorul cunoaște cheia secretă proprie;

3. semnătura este ne-reutilizabilă deoarece ea este în funcție de conținutul documentului, cel care este criptat;

4. semnătura este ne-alterabilă deoarece orice alterare a conținutului documentului face ca semnătura să nu mai fie verificabilă cu cheia publică a emițătorului;

5. semnătura este ne-repudiabilă deoarece receptorul documentului nu are nevoie de ajutorul emițătorului pentru verificarea semnăturii.

În concluzie, semnătura digitală (electronică) reprezintă un atribut al unei persoane, fiind folosită pentru recunoașterea acesteia. Semnătura digitală rezolvă atît problema autentificării emițătorului, cît si pe cea a autentificării documentului (numită și integritate).

În implementările practice, algoritmii cu chei publice sunt deseori ineficienți și lenți pentru a se realiza semnătura electronică. Pentru a cîștiga timp, protocolul de semnătură digitală folosește o funcție de hash, cu ajutorul căreia se realizează un rezumat al documentului:

[1] Se face un rezumat al documentului (digest) cu ajutorul unei funcții hash;

[2] Rezumatul documentului este cifrat cu cheia privată a emițătorului, care astfel semnează;

[2] Documentul este trimis la receptor;

[3] Receptorul verifică semnătura în 3 pași:

[3.1] Se creează un nou rezumat al pretinsului document semnat,

[3.2] Se decriptează rezumatul semnat (semnătura documentului) cu cheia publică a emițătorului.

[3.3] Se compară cele 2 rezumate iar în caz de coincidență, semnătura este validată.

Implementările existente de sisteme de semnătura digitala folosesc, cel mai adesea, următorii algoritmi criptografici:

– pentru rezumat: MD2, MD5 (Mesage Digest create de Ronald Rivest), SHA (Secure Hash Algoritm, creată de Institutul de Standarde al SUA -NIST pentru standardul de semnătura DSA).

– pentru semnătura: RSA ( creat de Rivest-Shamir și Adleman), El Gamal și DSA (Digital Signature Algorithm, creat de NIST ca standard de semnătură digitală).

S-au creat, de asemenea, si alte tipuri de protocoale de semnătură digitală, cum ar fi cele de semnătură de grup, semnătură majoritară sau semnături simultane.

Diffie și Hellman sugerează o metodă de implementare practică a conceptului propus. Se indică utilizarea unor funcții greu inversabile ( one – way functions). Ele își au originea în probleme grele din punct de vedere computațional. O funcție este greu inversabilă dacă este inversabilă și ușor de calculat, dar pentru aproape toate valorile y din codomeniu este imposibil computațional să se calculeze x = f-1 (y). Cu alte cuvinte este imposibil computațional să se calculeze f-1 dacă se dispune de o descriere completă a lui f. În concluzie, o funcție este greu inversabilă dacă:

Este ușor să calculez y din x, y = f(x);

Există inversa funcției;

Este computațional imposibilă determinarea inversei funcției.

O funcție greu inversabilă se spune că este cu trapă atunci cînd f-1 este ușor de calculat numai dacă se dispune de o informație numită trapă; necunoașterea acestei informații face ca funcția să fie greu inversabilă. O astfel de pereche de funcții ( f, f-1 ) poate constitui perechea (E, D) a unui criptosistem cu chei publice. În general, pentru procedurile E și D se indică scheme bazate pe operații modulo n cu elemente din inelul claselor de resturi modulo n.

Schema propusă în [DIFF76] își bazează securitatea pe dificultatea calculului logaritmilor modulo număr prim.

Fie q un număr prim și un întreg X, X[1, q-1]. Se poate calcula:

Y = ax (mod q),

unde a este un element primitiv al cîmpului Galois GF(q).

După cum se știe, clasele de resturi modulo q formează un inel; dacă q este un număr prim acestea formează un cîmp Galois GF(q). Într-un cîmp GF(q) există (q-1) numere a care se numesc elemente primitive ale cîmpului.

Dacă a, a2, ………….…., a(q) sunt puterile lui a , acestea au ca resturi mod q pe 1, 2, ………….., (q) , ceea ce înseamnă că un element primitiv generează prin ridicare la putere toate elementele nenule ale cîmpului. S-a notat cu (q) = indicatorul lui Euler, (q) = q-1.

Fiecare utilizator A alege în mod aleator un număr XA , XA {1, 2, ……….., q-1} și calculează YA = YAXB = YBXA = a XAXB (mod q ).

În timp ce utilizatorii A și B pot calcula cheia K AB pornind de la X propriu (secret) și Y public al partenerului, un criptanalist trebuie să calculeze pe K AB pornind de la YA și YB , singurele făcute publice astfel:

K AB = YA log YB (mod q).

Acest lucru face ca sistemul să fie deosebit de greu de spart datorită imposibilității calcului logaritmului modulo q.

Calitatea fundamentală a sistemului este că nu necesită stabilirea în avans a unei chei secrete de cifrare între doi utilizatori ai unei rețele care doresc să comunice date confidențiale; ei fac apel doar la fișierul de chei publice. Descifrarea mesajelor nu se poate face însă pe baza cheilor din fișierul public, ci doar pe baza perechilor lor, ținute secrete de fiecare utilizator. Criptosistemele cu chei publice fac parte din clasa sistemelor criptografice sigure computaționale.

Începînd din anul 1979 s-au căutat o serie de funcții care să satisfacă cerințele impuse de sistemul cu chei publice. Acestea se bazează pe schemele unor probleme foarte greu de rezolvat la nivelul cunoștințelor matematice de azi, cum ar fi factorizarea unui produs de numere prime foarte mari, găsirea logaritmului modulo număr prim într-un cîmp mare, cu respectarea unui element primitiv, problema rucsacului etc.

2.2. Cifrul RIVEST- SHAMIR- ADLEMAN (RSA)

Algoritmul dominant în sistemele oferite de piața de software pentru sistemele de semnătură digitală îl reprezintă algoritmul RSA, considerat un standard de facto în acest domeniu. El își bazează tăria criptografică pe imposibilitatea factorizării unor întregi mari (sute de cifre zecimale). Folosirea acestui algoritm în industrie se face conform unei suite de standarde, cunoscute sub denumirea de PKCS (Public-Key Cryptography Standards), realizate de proprietarul lui RSA, firma RSA Data Security Inc.'s:

– PKCS #1 descrie metoda matematica de cifrare si descifrare RSA precum si implementarea lor pentru realizarea a doua funcții: semnarea electronică si anveloparea digitala a cheilor criptografice simetrice; (PKCS #1 include acum si PKCS #2 si PKCS #4);

– PKCS #3 descrie metoda Diffie-Hellman de distribuție a cheilor criptografice simetrice;

– PKCS #5 descrie metoda de implementare a cifrării simetrice DES-CBC, cu o cheie derivată din parolă;

– PKCS #6 descrie standardul de certificat digital, supra-set al standardului X.509;

– PKCS #7 descrie sintaxa generala a datelor ce urmează a fi criptate sau semnate;

– PKCS #8 descrie sintaxa perechii private a cheilor de criptare (cheie și atribute);

– PKCS #9 descrie atributele tipurilor definite în #6, #7, #8;

– PKCS #10 descrie sintaxa standard pentru cererile de certificat;

– PKCS #11 descrie interfața program numita "Cryptoki", Criptography Tocken API Standard, pentru implementarea unor funcții criptografice în cadrul aplicațiilor;

– PKCS #12 descrie sintaxa pentru memorarea în cadrul software-ului a unor informații criptografice, cum ar fi chei publice, chei secrete, certificate etc.; scopul îl constituie standardizarea unei structuri de fișier ce poate fi folosit de mai multe aplicații.

Acest cifru cu chei publice, realizat de cei trei cercetători de la Massachusetts Institute of Technology, reprezintă standardul de facto în domeniul semnăturilor digitale și al confidențialității cu chei publice. El se bucură de o foarte mare apreciere atît în mediul guvernamental cît și în cel comercial, fiind susținut prin lucrări și studii de comunitatea academică. Sub diferite forme de implementare, prin programe sau dispozitive hardware speciale, RSA este astăzi recunoscută ca cea mai sigură metodă de cifrare și autentificare disponibilă comercial. O serie de firme producătoare de sisteme de programe și echipamente ca DEC, Lotus, Novell, Motorola precum și o serie de instituții importante ( Departamentul Apărării din SUA, National Aeronautics- SUA, Boeing, rețeaua bancară internațională SWIFT, guvernul Belgiei etc.), folosesc acest algoritm pentru protejarea și autentificarea datelor, parolelor, fișierelor, documentelor memorate sau transmise prin rețele.

De exemplu firma Lotus dezvoltă Notes , un nou concept de lucru în comun (groupware) într-o rețea. La o astfel de legătură în comun a numeroase programe și persoane se cere însă o mare încredere în informații cît și o mare confidențialitate, ca urmare Lotus folosește semnătura digitală și secretizarea cu ajutorul criptosistemelor RSA.

În sistemul de operare NetWare, pentru rețele locale, al firmei Novell se folosește curent RSA în mecanismele de autentificare care permit utilizatorilor să acceadă la orice server al rețelei.

Motorola comercializează telefoane sigure care încorporează o serie de metode de confidențialitate și autentificare a utilizatorilor cît și a partenerilor de dialog. Toate acestea se bazează pe algoritmul RSA și se regăsesc atît în variante de uz general cît și în variante pentru comunicații militare, fiind destinate atît transmisiilor de voce cît și de FAX.

Un alt exemplu semnificativ de utilizare a sistemului RSA este rețeaua de poștă electronică a guvernului belgian. Toate protocoalele de asigurare a confidențialității și de autentificare prin semnătură digitală folosesc acest algoritm.

Sistemul RSA este de tip exponențial. În cadrul acestei metode modulul n este obținut prin produsul a două numere prime mari:

n = p*q,

astfel încît indicatorul lui Euler (n) = (p-1)*(q-1), devine mult mai greu de determinat, iar schema poate fi folosită cu succes într-un criptosistem cu chei publice; se vor face publice e și n, iar d va fi ținut secret. În privința metodei se recomandă alegerea unui d relativ prim cu (n) în intervalul [ max(p, q)+1, n-1].

În acest caz e se va calcula astfel:

E = inv (d, (n) ),

putîndu-se utiliza o versiune extinsă a algoritmului lui Euclid.

Securitatea metodei depinde de dificultatea factorizării lui n în p și q. Cel mai rapid algoritm publicat de Schroeppel, cere un număr de pași egal cu:

T = exp (sqrt(ln(n)*ln(n))))

același cu cel al calculului logaritmului în cîmpul GF(n).

Rivest, Shamir și Adleman sugerează utilizarea unor numere prime p și q de 100 cifre, adică a unui n de 200 de cifre, ceea ce cere pentru factorizare mai multe milioane de ani.

Deoarece cifrarea și descifrarea sunt funcții mutuale inverse, metoda RSA poate fi utilizată atît la secretizare, cît și la autentificare. Fiecare utilizator A obține modulul n A și exponenții e A și d B . Apoi A va înregistra într-un fișier public (n A,e A) , în timp ce va ține secretă pe d A .

Un alt utilizator B va putea emite un mesaj secret M utilizînd transformarea de cifrare publică a lui A:

EA(M) = M eA mod n A .

La recepție A va obține mesajul în clar:

DA(EA(M)) = M eAdA mod n A = M.

Utilizatorul A va putea semna un mesaj M către B calculînd:

DA(M) = M dA mod n A ,

iar B va autentifica acest mesaj, utilizînd cheia publică a lui A:

EA (DA(M)) = M dAeA mod n A = M.

Să considerăm un mic exemplu care să ilustreze acest algoritm:

Fie p = 53 și q = 61 două numere prime; produsul acestor două numere ținute secrete este n = 53*62 = 3233 iar (n) = (p-1)*(q-1) = 52*60 = 3120. Fie d = 791 cheia secretă; exponentul e (cheie publică) se calculează ca invers multiplicativ mod 3120 a lui d. Ca urmare e = 71.

Pentru a cifra mesajul, M = RENAISSANCE, acesta se va împărți în blocuri de patru biți fiecare, unde A = 00, B = 01, C = 02,……………., Z = 25 și blanc = 26:

M = RE NA IS SA NC E

=1704 1300 0818 1800 1302 1426.

Primul bloc se va cifra ca 1704 71 mod 3233 = 3106, etc.

Criptograma obținută devine:

C = 3106 0100 0931 2691 1984 2927.

La descifrare, fiecare grup de două litere în clar se obține folosindu-se cheia secretă d:

3106 791 mod 3233 = 1704, etc.

O dificultate în utilizarea criptosistemelor RSA apare atunci cînd este nevoie atît de protecție cît și de autentificare, deoarece este necesar să se aplice transformări succesive cu module diferite. De exemplu, pentru ca A să transmită la B un mesaj semnat și secret, A va calcula:

C = EB (DA(M)).

Dacă n A>n B blocul DA(M) nu mai aparține mulțimii [0, n B-1] corespunzătoare lui EB . Reducerea lui DA(M) mod n B nu rezolvă problema, nemaiputîndu-se apoi obține mesajul original.

Soluția constă în utilizarea unui prag h (de exemplu h = 10 99 ) astfel încît fiecare utilizator să dețină două perechi de transformări: (EA1 ,DA1) pentru semnătură și (EA2 ,DA2) pentru protecție, respectînd condiția:

n A1<h<n B2 .

În acest caz la transmiterea unui mesaj semnat și secretizat la B, A va calcula:

C = EB2 (DA1(M));

Deoarece n A1<h<n B2, problema este rezolvată.

Utilizatorul B va obține pe M verificînd și semnătura:

EA (DB(C)) = EA1(DB2(EB2(DA1(M)))

= EA1(DA1(M))

=M.

O altă soluție în care C = EB(DA(M)) nu este calculabilă, deoarece n A>n B , este indicată de Konfelder. El recomandă să se calculeze C’ = DA(EB(M)), observînd că aceasta este calculabilă. Utilizatorul, B, care cunoaște atît n A, cît și n B , poate obține pe M în două moduri:

dacă n A<n B

EA(DB(C)) = EA(DB(EB(DA(M))))=

= EA(DA(M)) = M.

dacă n A>n B

DB(EA(C’)) = DB(EA(DA(EB(M))))=

= DB(EB(M)) = M.

Cînd apare o dispută între A și B asupra autenticității semnalului lui A un ”judecător” va trebui să fie capabil să stabilească dacă M aparține lui A:

dacă n A<n B , B va aplica transformarea sa secretă asupra lui C și va prezenta ”judecătorului” X = DB(C) și pe M. ”Judecătorul” va calcula M’ = EA(X), folosind transformarea publică a lui A și va verifica dacă M’ = M.

cînd n A>n B , B se va prezenta la ”judecător” cu C’ și M. ”Judecătorul” va calcula:

X = EB(M);

X’ = EA(C’) = EA(DA(EB(M))) și va verifica

X = X’.

Se observă că protocolul nu cere ca A sau B să dea ”judecătorului” cheile (transformările lor secrete). Pentru reducerea dimensiunii semnăturii se sugerează comprimarea mesajului printr-o funcție de hashing și apoi semnarea rezultatului.

2.3. Aspecte de implementare a algoritmilor exponențiali

Proiectarea unor criptosisteme RSA pleacă de la alegerea unor numere prime mari p și q pe baza cărora se calculează modulul n. Dimensiunea acestor întregi este esențială în asigurarea tăriei criptografice a schemei. Următorul tabel, extras din [RIVE78] dă o indicație a legăturii dintre dimensiunea lui n și numărul de operații necesare, în cel mai bun algoritm publicat, pentru factorizarea lui n:

Odată aleasă dimensiunea lui n, cei doi întregi p și q trebuie aleși pseudoaleatori. Teorema numerelor prime arată însă că doar (ln n) întregi pot candida la statutul de numere prime mai mici ca n. Pentru un n de mai multe sute de cifre, numai cîteva sute de candidați trebuie să fie testați pentru a găsi un număr prim.

Pentru o mai bună protecție împotriva factorizării, trebuie luate și următoarele măsuri suplimentare:

p și q trebuie să difere în lungime prin cîțiva biți;

atît (p-1) cît și (q-1) trebuie să conțină factori primi mari;

cmmdc (p-1, q-1) trebuie să fie mic.

Pentru a găsi un număr prim p astfel ca (p-1) să aibă un factor prim mare, se va genera mai întîi un întreg aleatoriu p’, iar apoi se calculează:

p = p’ *i +1, i = 2, 4, 6,……..,

pînă cînd p este prim. O protecție suplimentară se poate obține dacă alegem p’ astfel ca (p’-1) să aibă un factor prim mare.

O altă problemă importantă constă în alegerea exponenților e și d. Avînd aleși întregii p și q, și deci n = p*q, exponenții e și d trebuie să satisfacă condiția:

e*d = 1 mod (n).

Se alege întîi un întreg d > max (p,q) din mulțimea de întregi relativi primi și mai mici ca (n). Este de asemenea necesar ca atît d cît și e să fie mai mari ca log2 n, deoarece acest lucru ar face ca Xe (mod n) = X și astfel cifrul să fie ineficient.

Alegerea lui e, 0 < e < (n) se face astfel încît el să reprezinte inversul multiplicativ mod (n) al lui d. Acest lucru se poate realiza folosind o variație a algoritmului lui Euclid.

Dată fiind complexitatea calculelor impuse de aplicarea algoritmului RSA, o serie de cercetări au vizat implementarea hardware, fie sub forma unor plăci coprocesor, fie ca chip independent [KOCH86] [RIVE80]. Conform datelor publicate, astfel de implementări, realizate în SUA și supuse embargoului la export, ating performanțe foarte bune; de exemplu lucrînd cu operanzi de 512 biți, cifrarea/descifrarea, materializate prin ridicări la putere modulo, se realizează în chipul FAP4 în medie în 100 ms. De asemenea firma CRYPTECH realizează plăci coprocesor RSA care cifrează operanzi de 512 biți cu o rată superioară celei de 12600 bps.

2.4. Atacuri criptoanalitice posibile la RSA

Tăria criptografică a cifrului RSA a făcut obiectivul a numeroase studii în literatura de specialitate. Atacul criptografic constă în încercarea de a determina cheia secretă d din informația care constituie cheia publică (e, n). Aici există mai multe căi posibile.

(a) Factorizarea lui n

Factorizare lui n în componentele sale ar permite calculul lui (n) = (p-1)*(q-1) și apoi determinarea lui d ca invers multiplicativ mod (n) al lui e. Există un număr mare de algoritmi de factorizare [KNUT83]. Cel mai rapid însă, aparținînd lui R. Schroeppel, nepublicat, conduce pentru numere de sute de biți, la valori reprezentînd volume de calcul prohibitive.

În [RIVE85] Rivest și Shamir arată că formula lui Schroeppel privind numărul de pași ca și cea corespunzătoare timpului necesar factorizării pot fi reduse prin deținerea, în procesul criptoanalizei a unor informații colaterale: procedura de generare a întregilor primi p și q; lungimea lui p și q, rădăcinile mod n, semnătura RSA a unui mesaj M utilizînd un modul n corespunzător unui exponent public 3, cei mai puțini semnificativi n/4 biți ai lui p. În plus se demonstrează că dacă criptoanalistul poate pune k întrebări la care să i se răspundă cu da sau nu, are loc o reducere dramatică a timpului de factorizare a lui n (de exemplu dacă k = n/2 sarcina poate deveni banală: el întreabă reprezentarea binară a lui p). Analize asupra securității cifrului RSA sunt făcute și în [SCHN83] [CHAU85] [DESM85].

(b) Calculul lui (n) fără factorizare lui n

Există studii de criptoanaliză a cifrului RSA care își propun determinarea directă a lui (n) fără obținerea în prealabil a celor 2 factori p și q ai lui n. Însă problema, din punct de vedere matematic, nu este cu nimic mai simplă decît factorizarea lui n, deoarece găsirea lui (n) conduce apoi la factorizarea simplă a lui n.

Fie:

x = p+q = n-1-(n)

și

y = (p – q)2 = x2-4*n.

Cunoașterea lui (n) conduce la calculul rapid al lui x și y. Utilizînd x și y, numerele prime p și q pot fi calculate:

p = ½ * (x + SQRT(y))

q = ½ * (x – SQRT(y)).

(c) Determinarea lui d fără factorizarea lui n sau calculul lui (n)

A treia metodă de criptoanaliză constă în calculul exponentului secret d, lucru arătat în [RIVE78] că este computațional la fel de dificil ca factorizarea lui n.

Dacă d este cunoscut, este posibilă calcularea unor multipli ai lui (n):

e*d -1 = K * (n), KN.

Miller a demonstrat că n poate fi factorizat utilizînd multiplii ai lui (n). Oponentul poate determina o mulțime de d’, cu proprietatea că toți d’ diferă prin c.m.m.m.c. ((p-1)*(q-1)) iar dacă se găsește unul, atunci n poate fi factorizat. Determinarea însă a fiecărui d’ este echivalentă computațional cu factorizarea lui n.

(d) Metoda Simmons- Norris

Simmons și Norris arată că cifrul RSA poate fi spart și fără factorizarea lui p și q în cazul unei alegeri mai puțin atente a acestora. Ei arată că pentru anumite chei, recifrarea repetată a unui mesaj-cifrat poate conduce la mesajul clar. Fiind dat mesajul-cifrat:

C0 = Me (mod n)

criptoanalistul poate determina pe M calculînd:

Ci = Cei-1 (mod n), i = 1, 2, 3, …..(nu foarte mare).

Condiția ca acest fel de atac să nu fie posibil este ca alegerea lui p să se facă astfel ca (p-1) să conțină un factor prim mare p’-1 să conțină un factor prim mare p. Dacă acești factori primi sunt mai mari ca 10 99 , probabilitatea unui astfel de atac este cel mult 10-90 .

(e) Atac multiplicativ

Chaun și de Jonge prezintă în] o metodă de atac asupra unei semnături RSA bazată pe redundanța existentă într-o semnătură validă.

Se presupune că B construiește trei mesaje valide M1, M2, M3 astfel încît M3 = (M1*M2) mod n. Dacă B deține semnătura făcută de A asupra lui M1 și M2, B va putea forma produsul mod n al acestor semnături pentru a obține semnătura falsă a lui M3:

SA(M3) = (M1*M2)dAmod nA

= ((M1dA mod nA)*(M2dA mod nA)) mod nA

= SA(M1)* SA(M2) mod nA .

Ca urmare B va putea folosi inversa M-1 sau opusul –M ale mesajului M, plecînd de la cunoașterea versiunii semnate:

SA (M-1 mod nA) = SA (M)-1 mod nA

și

SA(-M) = -SA(M).

Astfel dacă B cunoaște semnătura lui A asupra mai multor mesaje valide Mi, el va putea determina și semnăturile lui Mi și ale lui –Mi iar atacul multiplicativ indicat mai sus îi va permite semnarea oricăror mesaje false care reprezintă produse ale unor semnături SA (Mi), SA (Mi-1) sau SA (-Mi).

Este important de menționat că literatura de specialitate cunoaște și numeroase studii criptoanalitice la adresa lui RSA prin calculul unor logarutmi discreți în cîmpul GF (2n) și care se bazează pe atac cu perechi (text clat, text cifrat) corespondențe.

2.5. Spargerea algoritmului RSA

Atacul a fost întreprins cu succes de cercetătorul Daniel Bleichenbacher de la Bell Laboratories. Bleichenbacher a descoperit că un intrus, care este capabil să pătrundă într-un server SSL și să înregistreze o tranzacție criptată, poate apoi sa transmită spre serverul de Web original un număr foarte mare de mesaje (un milion sau mai multe) construite într-un anumit mod și poate folosi codurile de eroare primite ca răspuns pentru a decripta informația conținută în tranzacția criptată care a înregistrat-o. Intrusul nu încearcă astfel să descopere o cheie secretă, ci doar textul clar corespunzător unui anumit text cifrat ce a fost interceptat. Adică, după ce intrusul trimite victimei un milion de mesaje și analizează reacția acesteia la fiecare, el poate decripta un singur mesaj secret. Daca el dorește să decripteze un alt mesaj, atunci va trebui să trimită încă un milion de mesaje de un anumit tip spre victimă.

Faptul că este necesar un număr atît de mare de mesaje pentru acumularea informației necesare decriptării, face aproape imposibil ca acest tip de atac să treacă neobservat de către administratorii de sistem. Pînă în prezent, în Internet nu s-a raportat nici un alt astfel de atac. Cu toate acestea, compania RSA Data Security (cea care publică standardele de securitate PKCS) și principalii producători de soft au recomandat și distribuit contramăsuri pentru evitarea atacului. IBM, Microsoft, Netscape, Lotus și Consensus Development au publicat, chiar în ziua în care atacul a fost dat publicității, programe ce elimina problema din serverele lor de SSL (clienții SSL nu sunt afectați). De asemenea, RSA Data Security a făcut publică o lista a tuturor producătorilor de soft care lucrau împreună cu această companie la implementări ale standardului PKCS#1.

Problema apare, de fapt, în cazul protocoalelor interactive de stabilire a cheii bazate pe standardul PKCS#1 (Public Key Cryptography Security #1), printre care și protocolul SSL – folosit la scară largă astăzi pentru criptarea tranzacțiilor de comerț electronic în Internet. Această problemă nu afectează însă alte protocoale de comunicare sigură prin mesaje bazate pe standardul PKCS#1, cum ar fi Secure Electronic Transactions (SET) și Secure Multipurpose Internet Mail Extension (SMIME), deoarece acestea nu sunt susceptibile la aceasta vulnerabilitate sau conțin deja mecanisme pentru înlăturarea ei.

Vom încerca sa prezintăm, în prima parte, standardul PKCS#1 și modul în care s-a realizat atacul criptografic, urmînd ca în final să se arate impactul avut de un astfel de atac asupra protocolului SSL și cîteva contramăsuri ce au fost luate pentru eliminarea vulnerabilității.

2.6. Criptarea RSA

Există trei formate pentru blocurile de date: blocurile de tipul 0 si 1 sunt rezervate pentru semnături digitale, iar blocurile de tipul 2 sunt folosite pentru criptare. Deoarece în atacul ce face subiectul acestui articol sunt relevante doar datele reprezentînd informație criptată, în continuare vom lua în considerare doar blocurile de tipul 2.

Daca notam cu D blocul de date (sau textul clar), PKCS#1 definește o metoda de codificare pentru criptarea folosind RSA în care valoarea lui D este convertită la un întreg (pe care îl vom nota cu m) înainte de a fi criptată cu cheia publică RSA. Daca notam cu k numărul de octeți ai modului RSA,s (notat în general cu n) pentru un anumit receptor, metoda de codificare produce un sir de k octeți pornind de la D, în forma următoare:

BC = 00 02 || OU || 00 || D,

unde OU este un sir de octeți nenuli aleatori folosit pentru umplere de lungime k – lungime(D)-3 iar operația || semnifică concatenare. Cel de-al doilea octet 00 separa OU de D.

În continuare, transmițătorul va executa operațiile în vederea criptării blocului de date anterior codificat și transmiterii lui spre receptor.

La "celălalt capăt al firului", receptorul primește mesajul criptat c și îl decriptează folosind algoritmul RSA astfel:

m = cd mod n,

Apoi convertește el întregul m la un șir de octeți BC și verifică daca rezultatul are forma dorită iar dacă este așa, receptorul poate recupera din BC valoarea D (adică textul clar al mesajului).

Receptorul poate face și niște verificări suplimentare asupra lui D, cum ar fi verificarea daca acesta are o anumită lungime sau formă, dar aceste verificări nu sunt cerute explicit de standardul PKCS#1.

Adeseori blocul de date D este chiar cheia de criptare secretă ce va fi folosită ulterior pentru comunicația sigură între transmițător și receptor.

Formatul de codificare folosit de standardul PKCS#1 pentru criptarea cu RSA este destinat, în primul rînd, asigurării confidențialității – adică pentru distribuirea sigură a cheilor de criptare simetrică. Acest format nu este destinat asigurării integrității și, în particular, nu are proprietatea de a fi plaintext-aware (conștient de textul clar inclus). Intuitiv, o schema de criptare este "conștientă de textul clar inclus" daca este imposibil (din punct de vedere computațional) să se construiască un text cifrat valid fără a se cunoaște textul clar corespunzător. În standardul PKCS#1, cu toate că este foarte dificil să se reconstituie valoarea D din textul cifrat c, nu este greu să se construiască textul cifrat c pornind de la valoarea D corespunzătoare.

Integritatea poate fi asigurată prin alte mijloace decît criptarea RSA în cadrul standardului PKCS#1, dar standardul în sine nu specifică exact care pot fi aceste "alte mijloace". Lăsînd alegerea acestor "alte mijloace", la latitudinea implementării pentru fiecare serviciu de securitate în parte, s-au introdus vulnerabilități ce apar în cazul în care integritatea nu este verificată corespunzător.

Detaliile atacului

Cu mulți ani în urma, au existat o serie de rezultate criptografice care au dovedit ca fiecare bit dintr-un text cifrat cu RSA este la fel de sigur ca întregul mesaj. Criptografi de prestigiu, la vremea respectivă, au studiat aceste rezultate și au decis că ele nu erau teribil de folositoare: dacă întregul mesaj criptat cu RSA era sigur, atunci fiecare bit în parte din acel mesaj era sigur. Atacul de față pune în evidență situația inversă: dacă se pot sparge biți individuali dintr-un mesaj criptat cu RSA, atunci se poate sparge întreg mesajul.

În cele ce urmează, vom folosi termenul de intrus (sau atacator) pentru a desemna o persoana/aplicație ce încearcă să intercepteze o comunicație criptată. În general, un intrus poate intercepta, modifica și introduce pachete de informație prin conexiunea pe care o "ascultă". În aceste condiții, un protocol de securitate bine proiectat trebuie să fie capabil sa detecteze aceste modificări și să nu dea posibilitatea intrusului să obțină informații care sa-i permită decriptarea datelor interceptate.

Să presupunem ca un receptor, după ce realizează operația de decriptare PKCS#1, fie produce la ieșire un mesaj de eroare (daca descoperă ca rezultatul nu are forma dorita), fie continuă procesarea (în caz contrar). Un intrus poate determina astfel, din comportamentul receptorului, anumite informații despre decriptarea textului cifrat. De fapt, datorită metodei de codificare din PKCS#1 intrusul poate determina un octet și chiar mai mult din textul cifrat atunci cînd receptorul nu produce la ieșire mesajul de eroare indicînd că textul decriptat nu are forma dorită, deoarece intrusul știe că textul decriptat începe cu octeții 00 02. Astfel receptorul devine un "oracol", în sensul teoretic cunoscut, ce dă posibilitatea unui intrus să determine anumiți biți din decriptarea unui text cifrat arbitrar.

În teoria criptografică s-a demonstrat că, avînd textul criptat cu RSA, deducerea cîtorva biți din textul clar dă posibilitatea deducerii tuturor biților textului clar. Recent, chiar s-a arătat că se pot calcula toți biții textului clar din biții găsiți prin decriptări PKCS#1, reușite ale unor texte cifrate (diferite de textul ce se urmărește a fi decriptat) alese însă într-un anumit mod, numit alegere adaptiva și despre care vom da mai multe detalii în cele ce urmează. Astfel, oracolul deja menționat dă posibilitatea unui intrus să decripteze un anumit text cifrat folosind atacul cu text cifrat ales (chosen-ciphertext attack).

Atacul are forma următoare:

1. Un intrus intră în posesia unui text cifrat c și dorește să îl decripteze, adică să determine textul clar m corespunzător lui c.

2. Intrusul generează o serie de texte cifrate înrudite c1, c2, ? unde:

ci=c rie mod n

r1, r2, ? sunt valori între 1 si n-1, iar (n, e) reprezintă cheia publică a receptorului.

Intrusul alege valorile ri într-un mod adecvat, încercînd să optimizeze probabilitatea de obținere a unor texte cifrate "bune", adică alegînd ri într-un mod care este dependent de textele cifrate anterioare "bune". Un text cifrat se consideră a fi "bun" în contextul acestui atac dacă receptorul nu generează la primirea lui un mesaj de eroare indicînd că formatul textului clar corespunzător nu corespunde standardului PKCS#1 (adică dacă decriptarea lui produce un text clar ce corespunde formatului de codificare PKCS#1).

3. Intrusul trimite textele cifrate c1, c2,? receptorului pentru ca acesta să le decripteze (în cadrul unui protocol care implică PKCS#1) și observă comportamentul receptorului.

4. Pentru textele cifrate "bune" intrusul va deduce cîțiva biți din mesajul corespunzător mi = cid mod n = m ri mod n, pe baza metodei de codificare folosită de PKCS#1

5. Din biții deduși pentru m ri mod n, pentru suficient de multe valori ale lui ri, intrusul este capabil să reducă dimensiunea mulțimii în care trebuie căutat textul clar m (de fapt fiecare text cifrat "bun" reduce, în principiu, mulțimea la jumătate). În concluzie, folosind suficient de multe texte cifrate "bune", intrusul este capabil să determine textul clar m.

Cum poate fi folosit acest atac în diferite implementări

Datorită actualei metode de codificare folosită de standardul PKCS#1, procentajul textelor criptate bune este aproximativ de 1 la fiecare 216 pînă la 218 texte cifrate alese aleator. Se face, de asemenea, presupunerea că numărul de biți ai modulului public n este – de obicei – multiplu de 8 și că lungimea valorii D nu este verificată după decriptare. Un modul public cu o lungime (în biți) ne-divizibilă cu 8 duce la creșterea acestui procentaj, în timp ce verificarea lungimii lui D după decriptare (în loc să se verifice numai primii doi octeți ai lui BC) ar duce la scăderea procentajului.

În mod obișnuit, pentru un modul n de 1024 de biți numărul total de texte cifrate necesare găsirii textului clar este de aproximativ 220 – acesta fiind și numărul de mesaje ce sunt adresate de către intrus receptorului.

Evident, o metoda de codificare "conștientă de textul clar inclus" ar face ca probabilitatea de găsire a unui text cifrat "bun" să devină neglijabilă și ar înlătura posibilitatea unui astfel de atac.

Impactul practic al unui astfel de atac depinde de protocolul vizat. De exemplu, pentru un protocol de criptare a poștei electronice, impactul unui astfel de atac nu este semnificativ deoarece este foarte puțin probabil ca un receptor va dori să proceseze 220 mesaje și este și mai puțin probabil că un astfel de protocol va furniza intrusului informații consistente despre succesul sau insuccesul operației de decriptare.

Totuși, dacă acest atac este folosit împotriva unui protocol interactiv de stabilire a cheii cum este SSL (Secure Sockets Layer), impactul este semnificativ deoarece în acest caz un server va procesa un număr mult mai mare de mesaje și va dezvălui mult mai ușor succesul sau eșecul unei operații. Mai mult, un protocol așa cum este SSL poate să nu ceară autentificarea clientului astfel încît intrusul poate cu ușurință să rămînă anonim.

Atacul întreprins cu succes de cercetătorul de la Bell Laboratories are ramificații și în afara standardului PKCS#1. Multe protocoale vor trebui corectate și multe sisteme vor fi schimbate. Pe de altă parte, mulți oameni nici nu vor ști măcar de existența acestui atac și vor proiecta în continuare implementări nesigure pentru algoritmul RSA.

În continuare vom face o prezentare generală a protocolului SSL, care este cea mai cunoscută implementare a standardului PKCS#1 afectata de atacul lui Bleichenbacher. După o succintă descriere a etapelor protocolului SSL, vom arată unde anume este localizată vulnerabilitatea de securitate și cum poate fi aceasta eliminată dintr-o implementare practică a serverului SSL.

III. ALGORITMI CRIPTOGRAFICI

3.1. Algoritmul Cezar

În criptografie, cifrul lui Cezar, numit și cifru cu deplasare, codul lui Cezar sau deplasarea lui Cezar, este una dintre cele mai simple și mai cunoscute tehnici de criptare. Este un tip de cifru al substituției, în care fiecare literă din textul inițial este înlocuită cu o literă care se află în alfabet la o distanță fixă față de cea înlocuită. De exemplu, cu o deplasare de 5 poziții, A este înlocuit cu D, Ă devine E și așa mai departe. Această metodă este numită așa după Iulius Cezar, care o folosea pentru a comunica cu generalii săi.

Pasul de criptare al cifrului lui Cezar este de obicei încorporat în scheme mai complexe precum Cifrul Vigenère, și încă mai are aplicații moderne în sistemul ROT13. Ca orice alt cifru bazat pe substituții alfabetice, cifrul lui Cezar este simplu de descifrat și în practică nu oferă securitate suficientă.

Exemplu:

Transformarea poate fi reprezentată printr-o aliniere a două alfabete; alfabetul cifrului este alfabetului normal rotat la stânga sau la dreapta cu un număr de poziții. În exemplul de mai jos cifrul folosește o rotație la stânga cu cinci poziții (parametrul de deplasare, aici 5, este folosit drept cheia cifrării):

Normal: AĂÂBCDEFGHIÎJKLMNOPQRSȘTȚUVWXYZ

Cifru : DEFGHIÎJKLMNOPQRSȘTȚUVWXYZAĂÂBC

Pentru a cripta un mesaj se caută fiecare literă a mesajului în linia "Normal" și se scrie litera corespunzătoare din linia "Cifru". Pentru decriptarea unui text cifrat se procedează invers.

Mesaj inițial: ANA ARE MERE DE LA BUNICA SA

Mesaj criptat: DSD DUÎ RÎUÎ IÎ QD GZSMHD VD

Criptarea după cifrul Cezar poate fi reprezentată folosind aritmetică modulară prin transformarea literelor în numere conform schemei A = 0, Ă = 1,…, Z = 30. Astfel, alfabetul devine o secvență de 31 de numere, iar criptarea unei litere cu poziția din alfabet printr-o deplasare spre dreapta cu n poziții poate fi descrisă matematic ca

Decriptarea este făcută în mod similar:

(Există mai multe definiții pentru operația modulo. În operația de mai sus, rezultatul se află în intervalul 0…30. Dacă x+n sau x-n nu se află în intervalul 0…30, atunci prin operația modulo se scad sau se adună 31 de atâtea ori până când condiția este îndeplinită).

Metoda de înlocuire este aceeași pe întreg parcursul mesajului, de aceea cifrul este clasificat ca un tip de substituție monoalfabetică, spre deosebire de substituția polialfabetică.

Istoric

Cifrul Cezar este denumit după Iulius Cezar, care, conform Suetoniu, îl folosea cu o deplasare de 3 pentru protejarea mesajelor cu importanță militară:

Dacă avea ceva confidențial de comunicat, scria încifrat, adică schimba ordinea literelor din alfabet, astfel încât nu se putea înțelege nici un cuvânt. Dacă cineva dorește să descifreze și să înțeleagă, trebuie să înlocuiască a patra literă din alfabet, adică D, cu A, și așa mai departe pentru celelalte. — Suetonius, Viața lui Iulius Cezar 56.

Deși Cezar a fost primul care a fost folosit cifrul într-un mod în care se poate atesta, alte cifruri bazate pe substituție se cunosc ca fiind folosite anterior. Nepotul lui Iulius Cezar, Augustus, a folosit de asemenea cifrul, dar cu o deplasare de unu:

Când scria încifrat, scria B în loc de A, C în loc de B, și restul literelor pe același principiu, folosind AA pentru X. — Suetonius, Viața lui Augustus 88.

Există dovezi cum că Iulius Cezar folosea și sisteme mai complicate, iar un scriitor, Aulus Gellius, referă un tratat (acum pierdut) despre cifrurile lui:

Există chiar și un tratat scris în mod ingenios de către gramaticianul Probus cu privire la semnificația secretă a literelor din compoziția epistolelor lui Cezar. — Aulus Gellius, 17.9.1–5.

Nu se știe cât de util era cifrul Cezar în acel timp, dar este probabil ca el să fie destul de sigur, atât timp cât numai câțiva dintre inamicii lui Cezar erau în stare să scrie și să citească, dar mai ales să cunoască concepte de criptanaliză. Presupunând că un atacator reușea să citească un mesaj, nu există indicii cu privire la existența unor tehnici de soluționare a cifrurilor cu substituție. Primele dovezi cunoscute sunt lucrările din secolul al IX-lea ale lui Al-Kindi, în lumea arabă, o dată cu descoperirea analizei frecvenței.

Un cifru Cezar cu deplasarea de o unitate a fost utilizat la încifrarea numelor lui Dumnezeu pe spatele Mezuzelor. Acest fapt poate fi o rămășiță din vremurile în care evreilor nu le era permis să dețină Mezuze. Înseși literele criptogramei conțin un nume divin, despre care se considera că ține forțele răului la distanță.

În secolul al XIX-lea, secțiunea de anunțuri personale din ziare era folosită pentru schimbarea de mesaje criptate folosind scheme simple de încifrare. Kahn (1967) descrie exemple de îndrăgostiți care comunicau secret folosind cifrul Cezar în The Times. Chiar și în 1915, cifrul Cezar era folosit: armata rusească l-a utilizat ca înlocuitor pentru cifruri mai complicate care s-au dovedit a fi prea dificile pentru ca trupele lor să le folosească; criptanaliștii germani și austrieci nu aveau nici o dificultate în decriptarea mesajelor lor.

Cifrurile Cezar pot fi găsite astăzi în jucăriile pentru copii. O deplasare de 13 este efectuată în algoritmul ROT13, o metodă simplă de alambicare a textului de pe unele forumuri de pe Internet, dar nu ca metodă de criptare.

Cifrul Vigenère folosește un cifru Cezar cu o deplasare diferită la fiecare poziție din text; valoarea deplasării este definită folosind un cuvânt-cheie care se repetă. Dacă o cheie este la fel de lungă ca și mesajul și aleasă aleatoriu, atunci acesta este un cifru care nu poate fi spart atât timp cât cheia este secretă. Cuvintele cheie mai scurte decât mesajul introduc un șablon ciclic care poate fi detectat cu o versiune statistică avansată a analizei frecvenței.

În aprilie 2006, capul mafiot evadat Bernardo Provenzano a fost capturat în Sicilia parțial datorită criptanalizei mesajelor sale scrise într-o variantă a cifrului Cezar. Cifrul lui Provenzano folosea numere, astfel încât "A" era scris ca "4", "B" ca "5" ș.a.m.d.

3.2. Cifrul lui Polybius

Este un cifru de substituție. Literele alfabetului latin sunt așezate într-un pătrat de

dimensiune 5×5. Literele I și J sunt combinate pentru a forma un singur caracter, deoarece alegerea finală (între I și J) poate fi ușor decisă din contextul mesajului. Rezultă 25 de caractere așezate întrun pătrat 5×5 cifrarea oricărui caracter făcându-se alegând perechea potrivită de numere (intersecția liniei și a coloanei) corespunzătoare dispunerii caracterului în pătrat.

Exemplu: Mesajul: ”AM CASTIGAT LUPTA”, se transformă după cifrare în:

”11233111344443221144 1354534411”.

Codul poate fi schimbat prin rearanjarea literelor în pătratul 5×5.

Cifrul de substituție poligramică. Cifrul Playfair

Cifrul de substituție poligramică (polygram substitution ciphers) se obțin substituind blocuri de caractere ale alfabetului primar – numite poligrame – cu alte blocuri de caractere, de exemplu:

ABA → RTQ

SLL → ABB

Cifrurile bazate pe substituția poligramică realizează substituirea unor blocuri de caractere (poligrame) din textul clar, distrugând astfel semnificația, atât de utilă în criptanaliză, a frecvențelor diferitelor caractere.

Considerăm un mesaj și un cifru care prelucrează poligrame de lungime

d. Criptograma rezultată este Fiecare poligramă va fi prelucrată în poligrama prin funcția de substituție fi astfel:

În cazul cifrării literelor singulare frecvența de apariție a acestora în textul cifrat este aceeași cu frecvența de apariție a literelor corespondente din textul clar. Aceast lucru furnizează o cantitate de informație suficientă criptanalistului pentru spargerea sistemului. Pentru minimizarea informației furnizate de frecvența de apariție a literelor s-a procedat la cifrarea grupurilor de litere (n-grame). În cazul în care un grup de n litere este substituit printr-un alt grup de n litere, substituția se numește poligramică; cel mai simplu caz se obține pentru n=2, când diagrama m1m2 din textul clar se substitue cu diagrama c1c2 din textul cifrat. Un exemplu clasic pentru substituția diagramelor este cifrul lui Playfair.

Metoda constă în dispunerea literelor alfabetului latin de 25 de litere într-un pătrat de 5 linii și 5 coloane (i=j) de forma :

De regulă, în prima linie a pătratului se scrie un cuvânt cheie și apoi se completează celelalte linii cu literele alfabetului, fără repetarea literelor din prima linie. Cifrarea se execută după următoarele reguli :

– dacă m1, m2 sunt dispuse în vârfurile opuse ale unui dreptunghi, atunci c1, c2 sunt caracterele din celelalte vârfuri ale dreptunghiului, c1 fiind în aceeași linie cu m1. De exemplu GS devine MN.

– dacă m1 și m2 se găsesc într-o linie, atunci c1 și c2 se obțin printr-o deplasare ciclică spre dreapta a literelor m1 și m2. De exemplu AD devine BF sau CF, DA.

– dacă m1 și m2 se află în aceeași coloană atunci c1 și c2se obțin prin deplasarea ciclică a lui m1, m2 de sus în jos. De exemplu UO devine BW, iar EZ devine FE. Descifrarea se execută după reguli asemănătoare cu cele de cifrare.

3.3. Cifrul lui Vigenere

Cifruri de substituție polialfabetice sunt formate din mai multe cifruri de substituție simple. Au fost inventate de Leon Battista, în 1568. Cifrurile bazate pe substituția polialfabetică constau din utilizarea unor substituții monoalfabetice diferite.

Utilizarea unei secvențe periodice de substitiții ale alfabetului mărește în mod semnificativ securitatea criptogramei prin nivelarea caracteristicilor statistice ale limbii. Aceeași literă din textul cifrat poate reprezenta mai multe litere din textul clar, cu diferite frecvențe de apariție. În acest caz numărul cheilor posibile se mărește de la 26!, câte erau la substituția monoalfabetică, la (26!)n.

CONCLUZII

Dezvoltarea Internet-ului a fost un stimulent extraordinar, prin presiunea exercitată de tot mai mulți utilizatori, a căror dorință obiectivă este păstrarea secretului și a siguranței asupra poștei electronice private, a transferului electronic de documente și de fonduri și a altor aplicații. De asemenea, s-a constatat o potențare a gamei de instrumente folosite efectiv în execuția algoritmilor de cifrare. Utilizarea calculatoarelor electronice a permis folosirea unor chei de dimensiuni mai mari, sporindu-se astfel rezistența la atacuri criptoanalitice. Cînd cheia secretă are o dimensiune convenabilă și este suficient de frecvent schimbată, spargerea cifrului devine practic imposibilă, chiar dacă se cunoaște algoritmul de cifrare.

aceste circumstanțe, securitatea informatică a devenit una din componentele majore ale Internet-ului. Utilizarea serviciilor de poștă electronică, Web, transfer electronic de fonduri și documente etc., se bazează pe un sentiment adeseori fals, de securitate a comunicațiilor, care poate transforma potențialele cîștiguri generate de accesul rapid la informații, în pierderi majore cauzate de furtul de date sau de inserarea unor informații false ori denaturate. Analiștii acestui domeniu au sesizat o contradicție aparentă între nevoia de comunicații și conectivitate, pe de o parte și necesitatea asigurării confidențialității, integrității și autenticității informațiilor, pe de altă parte. Domeniul relativ nou al securității informatice caută soluții tehnice pentru rezolvarea acestei contradicții. În acest context, asistăm la o nouă tinerețe a domeniului străvechi al criptografiei. Datorită aplicațiilor ei în securitatea Internet-ului, criptografia a devenit azi unul dintre cele mai dinamice domenii de cercetare științifică academică. Acoperită multă vreme sub "voalul" utilizărilor militare și diplomatice, criptografia este astăzi din ce în ce mai implicată în activitățile noastre informatice de zi cu zi, unii vorbind deja despre existența unei criptografii "casnice".

BIBLIOGRAFIE

Menezes, P. Oorschot, S. Vanstome, Handbook of Applied Cryptography, 1996

A.Salomaa, Criptografie cu chei publice, Ed. Militară, 1996

R. J. Anderson, Security Engineering: A Guide to BuildingDependable Distributed Systems, Wiley, 2001

T.M. Apostol, Introduction to Analytic Number Theory,Springer-Verlag. 1976

J. Bayne, An Overview of Threath and Risk Assesment, 2002

Computer and Communications Security. D. Stinton, Cryptography, Theory and Practice, Chapman & Hall/CRC, 2002

S. Cook, http : //www.claymath.org/millennium/P vs NP/Official Problem Description.pdf (accesat 12.11.2013)

http://en.wikipedia.org/wiki/Rosetta stone (accesat 08.03.2014)

http://www.win.tue.nl/ gwoegi/P-versus-NP.htm (accesat 15.03.2014)

R. Anderson, E. Biham, L. Knudsen, (1997), SERPENT – ACandidate Block Cipher for the Advanced Encryption Standard, http://www.cl.cam.ac.uk/~rja14/serpent.html. (accesat 15.03.2014)

Curs: MIT, disponibil la http://www.cs.ucsd.edu/users/mihir/papers/gb.html. (accesat 12.04.2014)

BIBLIOGRAFIE

Menezes, P. Oorschot, S. Vanstome, Handbook of Applied Cryptography, 1996

A.Salomaa, Criptografie cu chei publice, Ed. Militară, 1996

R. J. Anderson, Security Engineering: A Guide to BuildingDependable Distributed Systems, Wiley, 2001

T.M. Apostol, Introduction to Analytic Number Theory,Springer-Verlag. 1976

J. Bayne, An Overview of Threath and Risk Assesment, 2002

Computer and Communications Security. D. Stinton, Cryptography, Theory and Practice, Chapman & Hall/CRC, 2002

S. Cook, http : //www.claymath.org/millennium/P vs NP/Official Problem Description.pdf (accesat 12.11.2013)

http://en.wikipedia.org/wiki/Rosetta stone (accesat 08.03.2014)

http://www.win.tue.nl/ gwoegi/P-versus-NP.htm (accesat 15.03.2014)

R. Anderson, E. Biham, L. Knudsen, (1997), SERPENT – ACandidate Block Cipher for the Advanced Encryption Standard, http://www.cl.cam.ac.uk/~rja14/serpent.html. (accesat 15.03.2014)

Curs: MIT, disponibil la http://www.cs.ucsd.edu/users/mihir/papers/gb.html. (accesat 12.04.2014)