Lect. Constantinescu Nicolae [620962]
UNIVERSITATEA DIN CRAIOVA
FACULTATEA DE ȘTIINȚE
SPECIALIZAREA INFORMATICĂ
LUCRARE DE LICENȚĂ
Sisteme Asimetrice de Criptare
Coordonator științific:
Lect. Constantinescu Nicolae
Absolvent: [anonimizat]
2017
2 Cuprins
1. Introducere 4
1.1 Termeni Criptografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Istoria criptografiei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2. Criptosisteme clasice 24
2.1 Cifrul lui Caezar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.1 Descriere generală . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2 Descriere matematică . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.3 Algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.4 Exemplu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Cifrarea afină . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1 Descriere generală . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2 Descriere matematică . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.3 Algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Codul Hill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.1 Descriere generală . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2 Descriere matematică . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.3 Algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3. Criptosisteme simetrice 31
3.1 Cifrare de tip flux (stream) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.1 Codul Vernam sau One Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.2 SEAL – Software Encryption Algorithm . . . . . . . . . . . . . . . . . . . . . . 36
4. Sisteme de criptare prin chei publice (asimetrice) 40
4.1 Schimbul de chei Diffie -Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Sistemul RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Semnătura digitală . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Sisteme de certificare a cheilor publice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.5 Infrastructura cheilor publice (PKI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6.1 Algoritmul DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6.2 Variante de DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.6.3 Algoritmul AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.6.4 Algoritmul LUCIFER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3 4.6.5 Algoritmul Blowfish . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.6.6 Dubla criptare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.6.7 Tripla criptare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.6.8 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5. Aplicație. Algoritmul RSA și implementarea lui 69
5.1 Codul RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.1.1 Descriere generală . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.1.2 Operații . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Bibliografie 75
4 Capitolul 1
Introducere
1.1 Termeni Criptografici
Scenariul cel ma i des întâlnit în criptografie, dar și în viața reală presupune că există două
persoane sau entități care doresc să comunice dar se află la ca petele unui canal de comunicație
nesigur. Și anume o terță persoană poate intercepta și ulterior avea acces la in formații care nu
îi sunt destinate. În acest scenariu părțile comunicante (pentru a fi în concordanță cu toate ma –
terialele din domeniu) se numesc Alice (expeditorul mesajelor) și Bob (des tinatarul), cea de -a
treia entitate o vom numi Eve și singurul ei s cop în acest scenariu este de a afla secretele celor
doi, Alice și Bob. Pentru a transmite informații Alice are mai întâi nevoie de un canal de
comunicație. Acesta poate fi o rețea informatică, o rețea telefonică sau pur și simplu clasicul
sistem poștal. Caracteristica principală care reunește toate aceste canale de co municație este
faptul ca ele nu sunt sigure, informația poate fi interceptată sau și mai rău poate fi modificată
în timp ce parcurge drumul de la Alice la Bob. Unul din obiectivele criptogra fiei este de a
produce mijloace prin care să se prevină astfel de atacuri.
Obiectivul fundamental si clasic al criptografiei este de a pune la dispo ziția entităților
precum Alice și Bob posibilitatea de a comunica confidențial folosind metode criptografic e.
Adesea mesajul care se trimite este denumit text în clar și el poate fi un text obișnuit, un șir de
numere, sau un program executabil. Alice înainte de a trimite mesajul lui Bob criptează
textul în clar pt și obține textul criptat tc. Textul criptat est e cel ce va fi trimis lui Bob, acesta
pentru a decripta mesajul si a obține textul in clar va avea nevoie de o cheie de decriptare.
Eve, denumită și adversarul sau atacatorul are în conti nuare posibilitatea de a intercepta
mesajul însă criptarea textului ar trebui să garanteze faptul că Eve nu va putea citi mesajul,
adică nu va putea obține textul în clar din textul criptat, cunoscând chiar și algoritmul folosit
pentru criptare. Se spune adeseori că puterea unui criptosistem stă în puterea cheii și nu în
păstrarea secretului asupra algoritmului folosit.
Pe lângă obiectivul prezentat mai sus metodele criptografice trebuie să prezinte soluții
pentru încă trei probleme de importanță cel puțin egală cu păstrarea secretului asupra
informațiilor transmise:
1. Autent ificarea: destinatarul unui mesaj trebuie sa dispună de modalități de a verifica
identitatea expeditorului și originea mesajului. Să presu punem ca Bob primește un
mesaj, el trebuie să se convingă de faptul că mesajul primit vine intr -adevăr de la Alice.
2. Integritatea datelor: destinatarul trebuie să dispună de modalități de verificare a
integrității mesajului primit. După ce a verificat că mesajul primit este de la Alice, Bob
5 vrea să se asigure că mesajul este complet și nu au fost erori de transmisie sau
modificări voite din partea unui atacator, Eve.
3. Non-repudierea: după transmisia mesajului, trebuie ca expeditorul să nu poată nega
faptul că mesajul a fost intr -adevăr trimis de el sau des tinatarul să nu poată nega faptul
că a citit intr -adevăr mesajul. Al ice nu poate nega faptul că a trimis mesajul după
primirea mesajului de către Bob, iar acesta nu poate nega faptul că a citit mesajul din
moment ce a trimis un răspuns.
Definiția 1.1.1. Criptografia este o știință matematică folosită pentru a asigura
confidențialitatea datelor prin înlocuirea lor (textului în clar) cu o versiune schim bată,
obținută în urma unui proces de criptare, și din care versiune se pot obține datele inițiale utilizând
algoritmul criptografic potrivit și cheia necesara decriptării.
Definiția 1.1.2. Criptanaliza sau analiza criptografică este știința care se ocupă cu regăsirea de
informații valide din informații cifrate fără ca entitatea care dorește accesul la informație să aibă
acest drept. În urma proceselor criptanalitice se pot expune eventuale slăbiciuni ale algoritmului
de criptare folosit sau ale cheii.
Definiția 1.1.3. Criptologia este știința care se ocupă cu studiul criptografiei și criptanalizei.
Criptarea informației este făcută prin intermediul unei funcții E care trans formă textul, sau
informația pt folosind o cheie k în textul criptat tc(neinteligibil pentru eventualii adversari).
Altfel spus Alice pentru a tri mite un mesaj către Bob va aplica funcția E de parametri pt și k și
va obține textul tc:
E(pt, k) = tc
Textul astfel obținut va fi trimis prin intermediul canalului de comunica ție și prelucrat la
primire de către Bob, care va utiliza o funcție D pentru decriptare și o cheie k’ astfel:
D(k', tc) = pt
Formalizând putem defini acest sistem de asigurare a confidenți alității in formației astfel:
Definiția 1.1.4. Un criptosistem este un tuplu (P,C,K,E,D) care îndeplinește ur mătoarele
condi ții:
1. P este un set finit de posibile texte în clar
2. C este un set finit de posibile texte cifrate
3. K este un set finit de posibile c hei de cifrare
4. Pentru fiecare k e K există o regulă de criptare ek
E și o regulă cores punzătoare de
6 decriptare dk
D. Fiecare ek : P —► C și dk : C —► P funcționează astfel încât:
dk(ek(pt)) = p t
pentru oricare text în clar pt
P
Criptosistemele se deosebesc în funcție de modul în care este folosită cheia de
criptare/decriptare, astfel putem distinge două sisteme criptogra fice:
1. Cu cheie simetrică unde se folosește aceeași cheie pentru a mbele proceduri, criptare și
decriptare. Adesea aceste sisteme sunt numite cripto -sisteme cu cheie privata sau criptosisteme
cu o singură cheie deoarece cheia folosită trebuie să rămână cunoscută exclusiv parților
comunicante și k = k! .
2. Cu cheie publică unde se folosesc două chei pentru criptare, respectiv decriptare. Aceste
criptosisteme mai sunt numite și criptosisteme asime trice. Cheile folosite se numesc cheie
publică și respectiv cheie privată.
Criptosistemele cu cheie simetrică se împart în două c ategorii în funcție de modul în care
se face criptarea: algoritmi de tip stream sau algoritmi de tip block. Criptarea de tip stream
presupune generarea unei secvențe de biți cu o înfățișare cât de aleatoare posibil pe baza unei
chei. Secvența de biți este deci obținută în urma criptării bit cu bit a textului în clar (biții
textului în clar sunt adunați cu cei ai cheii). Este esențial pentru criptările de tip stream ca
două mesaje să nu fie criptate cu același stream al cheii de criptare, în acest sens se ia măsuri
speciale. Exemple de algoritmi de tip stream: SEAL (Software -optimised Encryption
Algorithm), RC4, A5, LEVIATHAN, Sober. Algoritmii de tip block presupun împărțirea
textului în clar în blocuri de biți care sunt criptate, criptarea blocurilor făcând u-se în mai
multe runde. Majoritatea algoritmilor cu cheie simetrică sunt de tip block cipher și folo sesc
diferite metode pentru a opera criptarea textului:
• modul ECB (Electronic Code Book) presupune criptarea fiecărui bloc separat și
independent de celel alte
• modurile CBC (Cipher Block Chaining) și CFB (Cipher Feed Back ) presupun
dependențe între blocurile criptate la runda anterioară ș i cele de la runda curentă în
funcție de un vector de inițializare.
• modul OFB (Output Feedback Mode) poate fi interpreta t că folosește o cifrare de tip
block pentru a genera un stream care este apoi adunat bit cu bit cu textul în clar.
Unii dintre algoritmi , spre exemplu DES (Data Encryption Standard) folosesc S -box-uri
sau tabele, denumite și Substitution -box pentru a obț ine textul criptat, folosirea numelui de
substituție este mai degrabă nepotrivită din moment ce o astfel de "cutie" poate avea mai
multe intrări decât ieșiri sau mai multe ieșiri decât intrări. Un exemplu de S -box poate fi
transforma rea identică
7 (0 → 0,1 → 1,2 → 2,…) care în mod evident nu are nici un efect, în timp ce alte tipuri de
transformări au anumite efecte, cantitatea și calitatea fiind diferite pentru fiecare. Efectele cel
mai des menționate includ efectul de avalanșă ș i nonliniaritatea funcție i Booleene. Desigur
este de așteptat ca structuri de cifrare diferite să dispună de caracteristici diferite ale tabelelor,
de aceea discuții despre puterea S -box-urilor apar de fiecare dată la construirea unui nou cifru.
Avalanșa este o proprietate a algor itmilor de tip block construiți în mai multe runde,
respectând o mică schimbare a datelor de intrare. Schimba rea unui singur bit produce după o
rundă multiple schimbări la nivel de bit, mai multe schimbări se produc după încă o rundă,
până când în cele di n urmă aproximativ jumate din bloc va fi schimbat, aceasta ca o analogie
asupra unei avalanșe naturale unde un mic efect inițial produce un rezultat neașteptat.
"Pe măsură ce datele de intrare trec prin straturi succesive, modelul care produce cifra 1
este amplificat și rezultă o avalanșă imprevizibilă. La final, rezultatul va conține, în medie,
jumate cifre 0 și jumate cifre 1. .. " Feistel, H. 1973. Cryptography and Computer Privacy.
Scientific American. Din punct de vedere matematic, în criptografia cu c heie publică, fiecare
entitate participantă la transmisia și recepția de mesaje are o cheie personală k = (pk, sk) care
este formată din două părți, pk este cheia publică sau cheia de criptare și este făcută cunoscută
tuturor celor care vor să trimită mesa je deținătorului cheii sk. Cheia sk este ținută secretă ș i va
fi folosită de către cel ce o deține pentru a decripta mesajele care ii sunt trimise. Să spunem că
Alice dorește să ii trimită un mesaj lui Bob, atunci ea va obține de la el, sau o terță persoa nă
de încredere, cheia lui publică, va cripta mesajul cu cheia lui Bob, pk, și îl va trimite. Bob va
folosi cheia sa secretă sk pentru a decripta și citi mesajul, avem deci:
D (sk , E(pk , pt)) = pt
Criptarea cu cheie publică are nevoie de computații complex e și este mai puțin eficientă decât
criptarea cu cheie simetrică, astfel criptările simetrice sunt folosite pentru volume mari de
date. Înainte ca Alice și Bob să comu nice, știind că au un volum mare de informații pe care
vor să -l transmită ei vor fi nevo iți să schimbe o cheie simetrică, pentru aceasta criptarea cu
chei publice este ideală. Acest tip de criptare mai este cunoscut și ca funcție one -way cu
trapdoor deoarece oricine poate foarte ușor folosi cheia publica pk pentru a cripta un mesaj,
însă numa i cel ce deține cheia privată sk îl poate decripta.
Definiția 1.1.5. O funcție one -way cu trapdoor este o funcție f(x) = y pentru care y este foarte
ușor de calculat, dar având pe y și cunoscând funcția f este greu de calculat x. Cunoscând insă o
informaț ie secretă k (denumită cheie) și având pe y sau valoarea lui f(x) este foarte ușor să se
calculeze x.
Un alt tip de funcție one -way este one-way hash function care mai are multe alte nume,
8 printre care: funcție de compresie, funcție de contracție, message digest, fingerprint,
cryptographic checksum, verificarea integrității mesajului (message integrity check, MIC), si
cod pentru detectarea manipu lării mesajului (manipulation detection code, MDC). Funcțiile
de hash există de mult timp în criptografie și fac parte din pilonii principali în construcția
multor protocoale criptografice.
Definiția 1.1.6. O funcție de hash este o funcție, matematic ă sau de alt ă natur ă, care ia ca
argument un șir de mărime variabil ă ș i întoarce ca rezultat un șir de mărime fix ă denumit
valoare hash .
Ideea din spatele funcțiilor hash este aceea de a produce reprezentare exactă de mărime
fixă a unor date de intrare ca apoi după ce datele au fost transmise printr -un canal de
comunicație, la capătul la care se află destina tarul să se poată spune dacă datele au fost
modificate de -a lungul canalului de comunicație. Acest lucru se poate face aplicând din nou
funcția de hash datelor primite și compararea rezultatului cu cel obținut înaintea transmite rii.
O funcție de hash trebuie de asem enea să producă o valoare unică de ieșire pentru o
singură valoare de intrare, adesea spunem că o func ție hash nu are coliziuni. Semnăturile
digitale sunt folosite în combinație cu metodele criptografiei cu cheie publică. La fel ca în
viata obișnuită, semn ăturile digitale trebuie să asigure non -repudierea, care este o trăsătură de
bază în cazul în care spre exemplu se folosește o astfel de metodă pentru a semna contracte,
sau alte acte oficiale. Să presupunem ca Alice vrea să semneze un contract pe care Bob i l-a
propus, ea va aplica atunci algoritmul S, folosind cheia secretă sk pentru a obține semnătura
S(sk, pt).La primirea semnăturii Bob va utiliza algoritmul V pentru a verifica semnătura V
(pk, s, pt) = ok. Este de preferat a nu se semna întreg textul î n clar ci numai valoarea rezultată
în urma aplicării unei funcții hash asupra textului.
Definiția 1.1.7. Un atac este o cale generală pe care un criptanalist o poate urma pentru a
"sparge" sau descoperi secretele protejate de un cifru sau sistem criptogra fic. Atacurile nu
sunt algoritmi preciși ci mai degrabă moduri de abordare pentru construirea unor algoritmi
care să spargă un sistem criptografic. Atacurile criptografice pot beneficia de constrângeri
informaționale care pot reduce strategiile de atac ce pot fi folosite, atacatorul dispune de unele
din informațiile de mai jos și poate alege strategia care se potrivește cel mai bine informațiilor
pe care le deține:
• numai text criptat atacatorul dispune numai de text criptat, adesea informațiile statistice
rezultate din textul criptat pot oferi detalii care pot conduce la spargerea cifrului. Dacă o
metodă criptografică nu poate rezista acestui tip de atac este complet nesigură. Chiar dacă Eve
9 nu poate folosi metode criptanalitice complicate Alice trebuie să presupună ca Eve poate să
intercepteze mesajele.
• text în clar cunoscut atacatorul dispune de un volum considerabil de text în clar și textul
criptat corespunzător. La o primă vedere s -ar părea că un astfel de fapt e imposibil de realizat,
insă spre exem plu în cazul unor mesaje cu format standard Eve poate cunoaște acest format.
• text în clar definit atacatorul poate trimite text în clar arbitrar și poate obține textul criptat
corespunzător. Un text în clar bine ales poate dezvălui anumite detalii de int eres pentru
atacator. În acest caz se presupune că Eve are acces cel puțin o dată la mașina de criptare
înainte de a putea criptanaliza sistemul.
• text criptat definit atacatorul poate trimite text criptat și apoi să obțină versiunea decriptată.
• cheie a leasă atacatorul poate specifica schimbări ale unui bit din cheie sau
anumite relații intre cheile de criptare folosite.
• cronometrare atacatorul poate cronometra duratele operațiilor de criptare și poate folosi
aceste informații pentru a afla detalii des pre cheie sau datele criptate.
• analiza greșelilor atacatorul poate include greșeli arbitrare în mașinăria care execută
criptarea și poate folosi aceste greșeli pentru a expune detalii despre cheia folosita la criptare.
• man in the middle (intermediarul) se presupune că atacatorul poate in tercepta mesajele
transmise și poate pretinde că este destinatarul me sajelor venite de ambele parți. Eve
interceptează mesajele atât de la Alice, cât și de la Bob și întotdeauna pretinde a fi una din
părți.
Adeseori o strategie de atac este ușor de ales și urmat dându -se constrân gerile
informaționale enunțate mai sus. Iată câteva strategii de atac:
• Brute Force sau căutarea exhaustivă a cheii presupune căutarea unei chei de decriptare
până atunci când textul rezultat în urma decriptării cu una dintre chei are sens.
• CodeBook sau abordarea clasică a spargerii codurilor presupune colecționarea de
transformări din text în clar în text cifrat și reciproc.
• Criptanaliză diferențială atacatorul trebuie să găsească diferenț e statistice intre valorile
cheilor și transformările asupra textului criptat, iar apoi trebuie să utilizeze suficient text în
clar pentru a putea recupera cheia de criptare.
• Criptanaliza liniară atacatorul trebuie să găsească o aproximație liniară a S-box-urilor care
au utilizat biți din cheia unui cifru și să o folosească pentru a descoperi cheia.
• Programarea cheii atacatorul alege chei care produc efecte cunoscute în runde diferite ale
criptării.
• Birthday attack atacatorul folosește paradoxul zilei de naștere, ideea este că atacatorul va
găsi mai ușor 2 valori care se potrivesc decât o valoare care să se potrivească unei valori date.
10 • Codificare formală atacatorul trebuie să construiască ecuații pentru cheie folosind textul în
clar și pornind de la designul algoritmului. După ce ecuațiile sunt construite atacatorul trebuie
să le rezolve.
• Corelații de obicei la cifrările de tip stream atacatorul trebuie să distingă datele de
elementele de confuzie.
• Dicționar este o îmbunătățire la atacul de tip b rute force. Atacatorul trebuie să formeze o
listă de chei probabile și să le testeze una câte una.
• Reluare atacatorul trebuie să păstreze bucăți de mesaje criptate și să le trimită parților
comunicante când consideră oportun.
Definiția 1.1.8. Un protoco l criptografic este o serie bine definită de pași care com bină mai multe
primitive criptografice, cum ar fi algoritmi de criptare/decriptare, funcții hash, sau
generatoare pseudo -aleatoare de numere, pentru îndeplinirea unei sarcini.
După cum se obișnuieș te într -un protocol este necesar să existe cel puțin două părți
implicate. Pentru a întări această afirmație considerăm o schemă pentru generarea unei
semnături digitale. Mai întâi partea implicată tre buie să aplice o funcție de hash mesajului
după care v a folosi cheia privată pk pentru a semna valoarea hash obținută. Ambii pași sunt
efectuați de o singură persoană, astfel nu putem numi această operație un protocol crip –
tografic. Situații tipice de utilizare a protocoalelor criptografice sunt cele în care este nevoie
să se facă o autentificare a utilizatorilor. Abordarea tradițională este aceea de a avea câte un
nume de utilizator și o parolă pentru fiecare din părțile implicate. Daca se procedează așa,
atunci când Ali ce va dori o autentificare va trebui să trimită numele de utilizator și parola
către Bob, nu este nevoie să mai spunem ca acest tip de autentificare este sus ceptibil atacului
de tipul "man in the middle", și anume Eve poate asculta comunicația între cei doi și poate
afla numele de utilizator ș i parola lui Alice.
Un simplu protocol de tip "challenge -and-response" poate rezolva cu succes problema expusă
mai sus. Protocolul se bazează pe criptarea asimetrică ș i presupunem că Bob deține un set de
"cereri" suficient de mare pentru a nu repeta aceea și cerere, în vreme ce Alice are o cheie k =
(pk, sk) pentru a se identifica. Protocolul decurge după cum urmează:
1. Bob alege la întâmplare o cerere c pe care o trimite către Alice
2. Alice semnează cererea c folosind cheia secretă sk și funcția S pentru semnă tură S(sk, c) =
s, apoi va trimite răspunsul s înapoi la Bob.
3. Bob va accepta răspunsul primit dacă funcția de verificare V va returna un mesaj afirmativ
în urma verificării semnăturii V(pk, s,c) = ok
Protocolul nu este totalmente sigur însă rezolvă prob lema unui atac de tipul man -in-the-
11 middle, o asigură pe Alice că nimeni nu îi cunoaște cheia secretă sk, nici Bob, cel care verifică
semnătura, Eve nu poate căpăta nici un fel de informație utilă în urma ascultării canalului de
comunicație deoarece cererea c face parte dintr -o mulțime rezonabil de mare încât să nu se
repete, și în plus cererea este aleasă aleator.
1.2 Istoria criptografiei
Criptografia este denumită "știința scrierii secrete", însă în egală măsură este o artă. Având
această natură duală criptografia a apărut ca răspuns la nevoia oamenilor de a păstra anumite
lucruri secrete, departe de eventuali dușmani, adversari sau opozanți puși a face rău părților
comunicante. Dez voltarea ei însă nu a avut un ritm susținut, mai întâi era nevoie ca o amenii
să dobândească un anumit grad de cunoaștere, în special în domeniul ling vistic, în ceea ce
privește atât limba scrisă dar și vorbită. Odată atins acest grad criptografia a apărut în mod
spontan. Desigur, acolo unde există se crete există și oameni dispuși să le afle, astfel o știință, să
spunem inversă criptografiei a apărut, și anume analiza criptografică, al cărei obiect de stu diu
este descifrarea mesajelor. Inventarea criptografiei nu a ținut în mod deosebit și nu a fost
limitată la o singură ci vilizație sau formă de guvernare. Oricând nevoia de confidențialitate a
apărut, criptografia a fost calea aleasă pentru a rezolva problema confidențialității. Odată cu
trecerea timpului, noțiunea de "cel mai bun sistem criptografic" a suferit multe modific ări și
adeseori civilii au fost cei care au adus îmbunătățiri esențiale acestei noțiuni. În următoarele
pagini vom încerca să redăm o scurtă istorie a criptografiei.
Istoria cunoscută a criptografiei începe acum aproximativ 4000 de ani când un scrib
egipte an folosește pentru prima dată hieroglife ușor modifi cate pentru a ilustra povestea
stăpânului său. Prin aceasta el deschide dru mul către "scrierea secretă", deși sistemul folosit
de el pentru a scrie hierogli fele respective nu poate fi considerat un si stem criptografic în
accepțiunea modernă a acestei noțiuni. Inscripțiile făcute de el în jurul anului 1900 î.e.n. în
camera mormântului nobilului Khnumhotep se întind pe aproximativ 20 de coloane din cele
222, care sunt incluse într -o secțiune care enumera monumentele ridicate de stăpânul său în
numele faraonului Amenemhet II. Este posibil ca intenția sa să nu fi fost aceea de a folosi o
scriere secretă ci mai degrabă de a atașa o oarecare notă de importanță lucrurilor înfăptuite de
nobilul său stăpân. Tot uși prin faptul că a modificat forma hieroglifelor, scribul a produs o
transformare deliberată a scrierii, aceasta fiind o trăsătură esențială a criptografiei. Pe măsură
ce a trecut timpul scrierea s -a dezvoltat și mormintele ce venerau pe cei dispăruți au devenit
locuri unde hieroglifele transformate au devenit din ce în ce mai complicate. Uneori
înlocuirea for melor uzuale ale hieroglifelor, cum ar fi o față reprezentând /r/ printr -o formă
diferită cum ar fi o față din profil, era folosită. Uneori sunetel e hie roglifelor erau diferite, dar
12 imaginile lor se asemănau. Iar uneori era folosit principiul rebusului, și anume o imagine
reprezenta o literă, de exemplu o navă cu pânze, "kenthey", reprezintă un alt cuvânt egiptean
khentey care înseamnă "cel ce condu ce la", aceasta făcând parte din titlul care i se dădea
zeului Amon, "cel ce conduce la Karnak". Dacă se adaugă la aceasta ele mentul secretizării se
obține al doilea element al criptografiei. În cazul egip tenilor însă elementul secretizării venea
din dor ința lor de a face scrierea necunoscută trecătorilor și de a -i opri pentru moment din
drumul lor pen tru a reflecta asupra epitafurilor înscrise pe pietrele mormintelor. În Egipt însă
la acea vreme exista un interes sporit pentru viața de apoi, oamenii au început, după primele
schimbări ale formelor hieroglifelor, să fie tot mai puțin interesați de acestea, astfel textele
gravate pe pereții mormintelor în cep să devină ușor criptice, asemeni unor ghicitori. Desigur
aceste prime semne ale criptografiei nu po t fi comparate cu știința exactă care este acum
criptografia, însă toate lucrurile mari au un început modest.
În Mesopotamia este găsită o tabliță care datează din anul anul 1500 î.e.n. și care conține o
formulă criptată pentru fabricarea sticlei pentru va se. Mesopotamia a mers pe un drum
oarecum paralel cu Egiptul în ceea ce pri vește criptografia, urmând însă sa se desprindă odată
cu primii scribi care își scriau numele folosind cifre. Aceasta se pare a fi însă mai degrabă o
formă de amuzament sau de mând rie decât una de cifrare exactă.
Primul sistem criptografic cu întrebuințare militară a fost inventat însă de spartani, cei mai
războinici dintre greci. În secolul 5 î.e.n. ei au inventat un dispozitiv denumit "skytale",
primul aparat inventat pentru a fi folosit în criptarea prin transpoziție. Modul de funcționare
era simplu, dar totuși ingenios. Se folosea un cilindru pe care se înfășura pergamentul sau
pielea pe care se dorea să se scrie, scrierea se făcea normal de la stânga la dreapta de -a lungul
înălțimii cilindrului, pergamentul era apoi îndepărtat și mesajul trimis. Pentru recompunerea
mesajului inițial trebuia folosit un cilindru de aceeași grosime.
Figura 1.1: Skytale, dispozitivul folosit de spartani pentru criptarea mesaje lor
Polybius, un scr iitor grec, a inventat un sistem care a fost mai apoi adop tat pentru
transmiterea la distanță a mesajelor folosind torțe. El a aranjat toate literele într -un pătrat,
13 numerotând liniile și coloanele. Pătratul său arăta în forma următoare, desigur el a folo sit
literele grecești:
Fiecare literă este acum identificată prin 2 cifre, de exemplu f=21, b=12, aceste numere se
doreau transmise prin intermediul torțelor, astfel 2 torțe în stânga și una în dreapta ar fi
însemnat f. Polybius nu a spus niciodată pentru ce anume era folosit acest sistem de criptare
prin substituție.
Figura 1.2: Pătratul lui Polybius
Un sistem criptografic prin substituție îi este atribuit lui Iulius Cezar, acest fapt ne este
relatat de Suetonius care spune că Iulius Cezar obișnuia sa -i scrie lui Cicero și altor apropiați
ai săi folosind un cifru în care literele erau înlocuite cu alte litere care începeau cu 3 poziții
mai la dreapta în alfabet. Astfel a devenea d , b devenea e etc. Până și astăzi un astfel de cifru
se numește "cifrul lu i Cezar" chiar dacă literele sunt deplasate cu mai mult de 3 poziții.
În următorii aproximativ 1000 de ani criptografia a stagnat, majoritatea textelor se limitau
la substituția literelor, scrierea lor pe verticală, înlocui rea punctelor cu vocale etc. Nic i una
dintre scrierile apărute în această perioadă nu conținea o metodă complexă de cifrare.
Anul 1518 aduce cu el apariția primei cărți tipărite de criptologie. Ea aparținea unui
călugăr benedictin ale cărui cercetări în științe oculte și alchi mie au făc ut din el o figură
marcantă a vremurilor în care a trăit. Numele său era Johannes Trithemius, iar cartea sa,
Polygraphiae libri sex, loannis Trithemii abbatis Peapolitani, quondam Spanheimensis, ad
Maximilianum Caesarem ("Șase volume despre poligrafie de J ohannes Trithemius, abate de
Wurzburg, fost de Spanheim, pentru Împăratul Maximilian"), tipărită cu caractere gotice,
conținea o formă elementară de substituție polialfabetică, deoarece alfabe tele după care se
făcea criptarea erau expuse pe mai multe lini i, fiecare rând oferind un nou alfabet de criptare.
Fiecare linie alfabetul era deplasata la dreapta cu câte o poziție, tabloul pe care îl forma era un
pătrat deoarece nu puteau fi mai multe linii decât numărul de litere din alfabet. Tabloul in –
ventat de J ohannes Trithemius produce pentru fiecare literă criptată un nou alfabet, acest
alfabet este însă la bază tot "cifru Cezar". Johannes Trithe mius a folosit acest tabel în cea mai
14
simplă formă posibilă, el codifica prima literă a textului în clar cu primul alfabet, a doua literă
cu al doilea alfabet, etc.
Figura 1.3: Tabloul lui Johannes Trithemius
Charles Wheatstone a fost unul din oamenii geniali ai secolului 19, lui i se datorează ceea
ce e azi cunoscut sub numele de cifrul Playfair și ace asta datorită faptului că prietenul său
Lyon Playfair l -a prezentat mai multor oficiali în Ianuarie 1854. Cifrul este primul din istoria
criptografiei care folosește două litere astfel încât rezultatul să depindă de ambele. Un pătrat
care conținea literele alfabetului a fost special construit pentru acest cifru, pătratul se bazează
pe cuvântul PALMERSTON, acesta fiind numele unuia dintre oficialii cărora le -a fost
prezentat cifrul. Pătratul conținea 5×5 celule, iar după PALMERSTON literele rămase sunt
așeza te alfabetic. Metoda de criptare este următoarea: mai întâi se desparte textul în clar în
grupuri de câte 2 litere, acolo unde există 2 litere alăturate identice ele vor fi despărțite și se
Figura 1.5: Așezarea literelor în pătratul Playfair
15 va scrie un x între ele. Literele i și j sunt privite ca fiind aceeași literă. Perechile de litere pot fi
în una din 3 situații: literele se află pe aceeași linie, coloană sau nu se întâmplă niciuna din
cele două. Pentru situația în care literele se află pe aceeași linie, ele vor fi înlocuite cu literele
imediat următoare spre dreapta, spre exemplu a și m , ele vor fi criptate prin L și E, os = NT,
le=MP Dacă literele se găsesc pe aceeași coloană ele vor fi înlocuite prin litere imediat
următoare de sub ele, de exem plu ac=SI, fy=QM, br=HB, etc. Dacă literele textului în clar nu
apar în niciuna din situațiile anterioare atunci să presupunem că avem de textul în clar ao , se
ia litera apărută la intersecția liniei lui a cu coloana lui o , anume M, care va fi prima lite ră a
textului criptat, a doua literă se obține mergând pe coloana literei a și pe linia lui o, vom avea
a doua literă a textului criptat care este S. Decripta rea mesajului este asemănătoare criptării,
daca ac=SI atunci SI=ac. Această nouă metodă introdusă de Playfair și Wheatstone avea tot
dreptul să ge nereze entuziasm atât autorilor cât și diplomaților și oficialilor care urmau să o
utilizeze. Punctele forte erau: rezistența sporită la analiza frecvenței literelor, prin criptare se
înjumătățea numărul el ementelor disponibile ana lizei frecvenței asupra textului criptat. De
exemplu un text de 100 de litere producea 50 de diagrafe criptate.
Sistemul ADFGVX este poate unul dintre cele mai faimoase sisteme crip tografice din
istoria criptografiei. Numele său provine de la faptul că numai acele 6 litere apăreau în textul
criptat, deși la început, când primele mesaje au fost interceptate, 5 martie 1918, codul nu
conținea decât 5 litere, ADFGX. Germania începuse să înțeleagă că dacă războiul avea să mai
dureze un rezultat favorabil avea tot mai puține șanse. Comandamen tul German nu putea să
nu recunoască valoarea incalculabilă a elementului surpriză, astfel pentru a -și spori șansele de
victorie într -o conferință a experților germani în criptologie cifrul ADFGVX avea să fie ales.
Responsabi litatea spargerii lui i -a revenit lui Georges Painvin, cel mai bun criptograf al
Bureau de Chiffre al Franței, care a primit primele mesaje în varianta cu 5 caractere a codului.
A pornit de la ideea că textul criptat nu putea f i rezul tatul unui tablou polialfabetic, deoarece
ar fi fost o abordare stângace, mai putea să verifice doar ideea unui tabel de substituție supus
unei transpozi ții. Painvin nu avea o cantitate satisfăcătoare de text criptat pentru a realiza o
analiză a f recvenței, pentru a determina dacă se folosea o cheie diferită în fiecare zi. Altfel
spus nu avea nici una din informațiile de bază asupra mesajelor criptate. Primele încercări de
decriptare au fost descurajatoare, analiza frecvenței indica schimbarea chei i tabelului în
fiecare zi. După 1 aprilie francezii au interceptat un număr de 18 mesaje ADFGX totalizând
512 grupuri de câte 5 litere. Două dintre mesaje fuse seră transmise în câte 3 părți, primele
două părți ale mesajelor aveau mici bucăți de text ident ice, acest fapt fiind observat de
Painvin în data de 4 apri lie. Această identitate putea proveni de la faptul că se utilizase aceeași
cheie pentru tabelul de transpoziție și bucățile de text erau literele de pe liniile de sus ale
16 tabelului. Painvin a împă rțit criptogramele în segmente care deve neau astfel coloanele
tabelului de transpoziție. Observând că unele coloane erau mai lungi Painvin a presupus că ele
fuseseră așezate în stânga tabe lului și numerele indicate de coloanele respective trebuie să fi
fost primele din cheia de transpoziție. Se puteau face acum primele aproximări asupra cheii.
Alăturând coloanele și numărând perechile de litere, Painvin nu a putut distinge caracteristici
importante în majoritatea cazurilor cercetate. Dar în unele cazuri r ezultatele obținute indicau o
substituție monoalfabetică, aceasta datorită faptului că unele coloane fuseseră alăturate. După
48 de ore Painvin a reușit să decripteze primele mesaje. Din punctul de ve dere al germanilor
criptarea era foarte ușor de realiza t și deși textul criptat era dublul celui în clar prin faptul că
se utilizau doar 5 caractere viteza de transmisie a mesajelor creștea. Succesul repurtat de
Painvin avea să fie în trerupt de o schimbare adusă de germani sistemului de criptare. Începând
cu 1 iunie ei au adăugat o a 6 -a literă extinzând tabloul de criptare la dimen siunea 6×6.
Painvin a început să lucreze la noul cifru în aceeași zi de la ora 17:00, ocupându -se de trei
mesaje aparținând aceluiași interval orar și care fuseseră transmise de ac elași expeditor.
Observând că două dintre mesaje diferă doar prin 2 caractere , unul având 106 caractere,
celălalt 108, Painvin a presupus că textele în clar puteau fi identice, diferențiindu -se doar prin
o modificare asupra adresei interne a celui din urm ă. În continuare era ne voie de un
aranjament al coloanelor astfel încât din coloanele tabelului de criptare să rezulte identitatea
criptogramelor.
Painvin a terminat decriptarea mesajelor la ora 19:00 pe 2 iunie , dar "mesajul cel mare"
nu fusese încă des cifrat, el urma să apară pe 3 iunie.
Figura 1.7: Tabelul cifrului ADFGVX descoperit de Painvin
Acesta a fost un succes însemnat pentru Painvin, el mărturisind bucuria pe care a
simțit -o descifrând mesajul german și recu noscând că nimic nu se comp ară cu momentul
decriptării unui mesaj de o asemenea importanță. Desigur un asemenea efort l -a lăsat pe
Painvin exte nuat, el slăbind aproximativ 15 kilograme în timpul evenimentelor mai sus
menționate, singurul efort depus fiind să stea la biroul său.
Arthur Scherbius este inventatorul faimoasei mașini criptografice Enigma, folosită de –
17 a lungul celui de -al doilea război mondial de către naziști. Enigma era o mașină care îngloba
atât componente mecanice cât și electrice. Partea mecanică era com pusă în prim ele versiuni
din 3 rotoare care erau fixate pe un ax, iar meca nismul intern producea mișcarea celor 3
discuri, care în funcție de rotațiile lor, stabilite după o formulă produceau diferite transformări
criptografice după fiecare apăsare de tastă. Transfor marea criptografică în sine era
determinată prin intermediul unui circuit electric care atunci când era activat aprindea un led
care indica litera rezultată în urma procesului de criptare. Spre exemplu dacă un operator
dorea să cripteze cuvântul "an" el tr ebuia să apese A pe tastatura mașinii și ca rezultat ledul
corespunzător literei S pu tea să se aprindă. Totul depindea de cheia de intrare folosită, care
era fixată de fiecare dată pe rotoare, înainte ca operatorul să înceapă tastarea mesaju lui.
Fiecare rotor avea o cablare complexă, curentul circulând de la un rotor la altul către un
dispozitiv denumite reflector responsabil cu devierea curen tului înapoi prin rotoare, dar pe o
altă rută, iar în final către un led care indica litera rezultată în urma cri ptării (primele aparate
Enigma nu dispu neau de un reflector ). Elementul principal al Enigmei era rotorul, mai precis
Figura 1.8: Funcționarea mecanismului reflector
sistemul de rotoare. Un rotor conținea cele 26 de litere ale alfabetului și era înconju rat de un
inel pentru a se putea fixa ușor prima literă din cheie. Fiecare rotor avea aproximativ 10 cm
diametru, fiind un disc făcut dintr -un material temo -rezistent care era traversat de o serie de
pini. Pe cealaltă față a discului pinii formau contacte electrice. Rotoarele erau montate pe un
ax astfel încât alăturate pinii să fie în contact cu celalalt disc și să formeze un circuit electric.
Enigma fusese proiectată să fie un dispozitiv sigur chiar dacă circuitul electric format de
rotoare era cunoscut u nui inamic.
Pentru a se evita implementarea unui simplu algoritm de substituție, unele rotoare se
întorceau numai la apăsări consecutive ale tastelor. Se asi gura astfel transformarea
criptografică diferită pentru fiecare poziție a ro toarelor producându -se o substituție
polialfabetică. Fiecare rotor avea un inel zimțat care în anumite momente era blocat,
18 permițând astfel ca următorul rotor să poată fi incrementat la apăsarea unei taste. La sistemele
care aveau numai un inel zimțat rotirea celui de -al doil ea rotor se producea după 26 de
caractere ale rotorului din stânga sa, în mod similar se rotea și roto rul din dreapta. Rotorul din
mijloc se mai putea roti simultan cu rotorul din dreapta, deci rotorul din mijloc făcea "dublu
pas" rezultând o perioadă red usă după care textul criptat putea începe să se repete. Istoric
vorbind me sajele criptate cu Enigma s -au limitat la mai puțin de 200 de caractere, nee xistând
astfel posibilitatea de a se repeta textul criptat. Cu excepția primelor 2 modele, ultimul rotor
era urmat de un reflector invenție brevetată și pre zentă doar la aparatele Enigma. Mașinile
Enigma dispuneau și de un panou vertical care conținea intrări ce reprezentau literele
alfabetului, astfel încât dacă două astfel de intrări erau conectate printr -un fir cele două litere
erau transpuse. Spre exemplu dacă A și B erau conectate atunci A și B erau in terschimbate
atât la intrare cât și la ieșire. În general 10 perechi de litere erau schimbate pentru a face mai
grea munca criptanaliștilor care descope riseră o metodă ușoară de spargere a cifrului
aparatelor care nu dispuneau de acest panou.
Folosirea Enigmei implica divizarea armatei naziste într -un anumit nu măr de rețele fiecare
dispunând de propriile configurări ale aparatelor Enigma. Pentru fiecare astfel de rețea
criptarea și decriptarea mesajelor era stabilită de un cod special. Codul se refera la ordinea
rotoarelor, modul lor de selectare, configurarea mesajelor (în unele rețele exista un rotor în
plus a cărui poziționare era schimbată la fiecare mesaj) și conexiunile de pe pa noul vertical al
Enigmei.
Toate aceste caracteristici trebuiau să fie identice pentru ca expeditorul și destinatarul
să poată comunica. Operatorii apa ratelor Enigma primeau în fiecare lună o carte care conținea
configurările necesare. Spre exemplu, unele rețele utilizau un sistem de 5 rotoare din care cu
aparatul se foloseau doar 3, o astfel de carte ar fi putut conține numerele rotoarelor și ordinea
în care trebuiau așezate pe ax. O altă configurare s -ar fi putut referi la l itera care trebuia să fie
litera curentă de pe rotor în mo mentul începerii criptării sau decriptării. Toate aceste
configurări pentru un aparat care avea în total 6 rotoare din care se utilizau numai 3 simultan
și care puteau fi așezate în 6 poziții difer ite (permutări) conduceau la 105,456 posibile
alfabete de criptare. Să nu uităm că fiecare rotor putea fi blocat de o setare a inelului, iar
aceasta adăuga mai multe variații. Descrierea matematică a algoritmului poate fi specificată
prin intermediul permu tărilor, transformările literelor fiind un produs de permutări.
Considerăm un apa rat Enigma cu 3 rotoare aparținând forțelor armate aeriene naziste.
Fie P transformarea produsă de panoul vertical, U transformarea produsă de re flector, S,M,D
transformări le produse de rotorul din stângă, mijloc, dreaptă. Atunci criptarea E poate avea
următoarea formulă:
19 E = PDMSUS-1M-1D-1P-1
După fiecare apăsare a unei taste rotoarele își modifică poziția, schimbând transformarea. De
exemplu dacă rotorul D se rotește i poziții transformarea devine piDp-i unde p este permutarea
ciclică, ea transformă A în B , B în C și așa mai departe. În mod similar rotorul din stânga și
din mijloc pot fi reprezentate prin j și k rotații, funcția de criptare devenind:
E = P(piDp-i)(pjMp-j)(pkSp-k)U(piD-1p-i)(pjM-1p-j)(pkS-1p-k)P-1
Utilizarea criptografiei în perioada interbelică nu s -a limitat numai la do meniul militar,
primele exemple care susțin acest lucru pot fi cazurile anche tate de Paza de Coastă americană
în timpul prohibiției din a nii 1920, 1930. Criptografia a fost utilizată în acea perioadă de
contrabandiștii de alcool ca element de ascundere a activităților lor ilegale. Începuturile
criptografiei pe acest domeniu al contrabandei sunt modeste, inițial se utilizau pentru
codificare a mesajelor codurile comerciale uzuale cum ar fi ABC Code, ediția 6. Pe măsură ce
rețelele își sporeau activitatea era normal să fie adoptate alte proceduri de comunicație, astfel
după 1930 aproape fiecare navă de pe coasta Pacificului avea propriul cod. Traficul de mesaje
realizat în acei ani era foarte mare pentru perioada aceea de timp. Consolidated Exporters
Corporation, o companie care reușise să -și elimine competiția și să stabilească filiale în
locurile strategice din pacific, transmitea peste două sute de me saje zilnic către navele sale. Pe
coasta de est situația era asemănătoare, aici se înregistrau undeva între 20 și 50 de mesaje
zilnic în zonele portuare New York și Florida. Modul de operare al contrabandiștilor
presupunea criptarea mesajelor î n 5 pași:
1. Textul în clar era criptat folosind un cod comercial, ABC Code, sau Acme.
2. Se adăuga 1000 la valorile obținute.
3. Valorile obținute erau căutate în alt cod comercial
4. Erau transcrise noile valori.
5. Textul obținut era criptat din nou folosind o substit uție monoalfabtică.
Responsabilă cu descifrarea mesajelor contrabandiștilor era Elizabeth S. Friedman, soția lui
William Friedman, care intr -un raport menționează: "Unele dintre acestea [criptograme] sunt
de o complexitate care nu a fost nici încercată de nici un guvern pentru cele mai secrete
mesaje ale sale". Pe de o parte complexitatea mesajelor se datora rețelelor complicate în care
erau implicați contrabandiștii, iar pe cealaltă codurile folosite de ei erau de o diversitate
demoralizantă.
Era criptogra fiei moderne începe cu adevărat odată cu publicarea lucrării "Communication
Theory of Secrecy Systems" de către Claude Elwood Shannon în jurnalul tehnic al Bell
Systems în anul 1949, cu această lucrare practic se pun bazele matematice ale criptografiei.
La foarte scurt timp după apariția acestei cărți Shannon publică împreună cu Warren Weaver,
20 "Mathematical Theory of Communication" și cu aceasta criptografia dispare din privirile
publicului, și se mută pe terenul organizațiilor guvernamentale și al altor or ganizații care
preferă să nu publice rezultatele muncii lor. Anii 1960 sunt marcați de lucrul echipei conduse
de Dr. Horst Feistel la primul "block cipher", denumit Lucifer. Se pare că numele provenea de
la un joc de cuvinte, sistemul la care lucra Feistel înaintea lui Lucifer se numea "Demon" și
era o prescurtare a cuvântului englezesc "Demonstration" deoarece siste mul de operare folosit
nu accepta nume mai mari. Acest sistem criptografic a fost dezvoltat la laboratoarele Watson
Research Lab din cadrul IB M și mai târziu a dus la dezvoltarea DES. Lucifer face parte din
grupul de criptosisteme care folosesc Feistel rounds pentru criptarea datelor, adică se aplică
un pas de criptare de mai multe ori unui bloc de biți. În principiu acest cifru este o rețea
substituție -permutare care folosește s -boxes de 4 biți care sunt selectate în funcție de cheia de
criptare. S -a demonstrat că prima versiune a cifrului era susceptibilă atacurilor criptanalitice
care foloseau texte în clar alese. O versiune ulterioară a fost propusă, aceasta folosea blocuri
de 64 de biți și cheia de criptare de 56 de biți, această versiune fiind special conce pută pentru
a rezista criptanalizei diferențiale. Una din variantele propuse ale cifrului Lucifer este varianta
propusă de Arthur Sorkin în Cryptologia 8 (1984). Aceasta folosește 16 runde de criptare, iar
cheia și blocul de text în clar au ambele 128 biți. Funcția Feistel corespunzătoare operează pe
un bloc de 64 biți ai textului în clar, 64 biți ai cheii și 8 biți de control ai interschi mbării.
Blocul de 64 biți corespunzător textului în clar este tratat ca o serie de 8 octeți, iar dacă bitul
de control corespunzător unu octet particular al blo cului textului în clar este 0 atunci
jumătățile de câte 4 biți ale octetului sunt interschimbat e, altfel dacă bitul de control este 1
jumătățile sunt lăsate neschimbate. Se operează apoi asupra fiecărui octet cu un s -box de
dimensiuni 4×4 (4 biți la intrare 4 la ieșire), pentru această operație este nevoie de două s -box-
uri S0 și S1, S 0 operează pe primii 4 biți ai octetului iar S1 pe ultimii 4. Rezultatele operațiilor
sunt apoi concatenate și se aplică un XOR folosind subcheia. Urmează o etapă de permutări
desfășurată în două părți, prima parte presupune permutarea fiecărui byte după o permutare
fixată iar apoi biții sunt schimbați intre octeți. Folosirea de subchei presupune un algoritm de
programare a cheii care este foarte simplu, cei 128 biți ai cheii sunt intro duși într -un registru,
iar la fiecare rundă se extrag din partea stângă primii 64 de biți ai subcheii și 8 biți pentru biții
de control ai interschimbării, după încheierea rundei registrul este shiftat la stânga cu 56 de
biți.
Urmașul direct al algoritmului Lucifer este DES ( Data Encryption Stan dard ) care a fost
propus în urma unui stud iu al National Bureau of Stan -dards (NBS) redenumit actualmente
National Institute of Standards and Te chnology (NIST) studiu ce arăta că USA are nevoie de
un standard pentru criptarea comunicațiilor guvernului, comunicații ce aveau ca obiect
21 informații se nsibile însă nu strict secrete. Astfel pe 15 Mai 1973 după o consultare prealabilă
cu National Security Agency (NSA), NBS a lansat o cerere oficială pentru propuneri din
partea societății civile a unui cifru ce avea să îndeplinească cerințe stricte, niciun a din
propunerile primite nu s -a dove dit viabilă. Ca urmare o a doua cerere a fost lansată la 27
August 1974 , de această dată IBM a răspuns cererii cu un cifru bazat pe Lucifer, dezvoltat de
o echipă de criptanaliști ce includea pe Dr. Horst Feistel, Wal ter Tuchman, Don Coppersmith,
Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn
Smith, și Bryant Tuckerman. Implicarea NSA în dezvoltarea DES a creat multe suspiciuni.
Aceste suspiciuni au fost susținute și de către pionierii criptografiei cu cheie publică Martin
Hellman și Whitfield Diffie care susțineau că scurtarea cheii de criptare și modificarea s -box-
urilor de către NSA, dădea agenției americane posibilitatea de a citi mesajele criptate fără
efort. Aceste afirmații erau susținute de faptul că unul din membrii echipei IBM care crease
algoritmul declarase că s -box-urile fu seseră trimise la Washington și se întorseseră sub o cu
totul altă formă. Pe de altă parte se căutau dovezi că algoritmul ar fi fost special modificat
astfel încât sa nu reziste unui atac brute force din partea NSA despre care se credea că ar fi
putut face acest lucru cu câțiva ani înaintea comunității acade mice. Spargerea DES a costat
220.000$, aceasta fiind realizată în anul 1998 cu ajutorul unui super -calculator care a reușit să
spargă cifrul în mai puțin de 3 zile. Acesta a fost momentul hotărâtor când NIST a solicitat
algoritmi criptografici din partea publicului, deși în paralel cu DES exista triple -DES o
variantă îmbunătățită care cripta de 3 ori te xtul în clar. Cererea NIST a avut ca rezultat, după
doi ani de analiză și dezbateri alegerea algoritmului Rijndael, care devenea Advanced
Encryption Standard (AES), înlocuitorul DES.
Anul 1976 avea sa marcheze începutul criptografiei cu cheie publică. Așa cum s -a
întâmplat în multe alte cazuri din lumea științifică mai mulți cer cetători lucrau în mod
independent la un sistem criptografic prin care se urmărea schimbul de informații criptate fără
a fi nevoie ca părțile comuni cante să dispună de cunoștințe a nterioare. Echipele cunoscute în
literatura de specialitate erau Whitfield Diffie și Martin Hellman de la Universitatea Stanford
și Ralph Merkle de la Universitatea California din Berkeley. Cele două grupuri se ocupau
fiecare de criptarea cu cheie publică respectiv distri buția de chei publice când au aflat fiecare
despre progresele celeilalte părți au decis să conlucreze după cum spune Martin Hellmann:
"Fiecare aveam o parte cheie a puzzle -ului și este adevărat că atunci când unul din noi spunea
prima dată X, altul spunea prima dată Y și așa mai departe, a fost combina ția dintre avansări
și regrese care a permis apariția descoperirii." Lucrarea care enunță primele idei cu privire la
criptografia cu cheie publică sau crip tografia asimetrică este "New direc tions în
cryptogtaphy", îi avea ca autori pe Diffie și Hellman și a apărut în noiembrie 1976 în ediția
22 IEEE Transactions on Information Theory. Lucrarea conținea referiri la ideile lui Merkle,
concepte ale criptografiei cu cheie publică, incluzând semnătur ile digitale și exemple de
algoritmi care urmau să fie implementați. Publicarea ideilor lor a revoluționat cercetarea în
criptografie care până la acea dată fusese supusă multor restricții atât reale cât și presupuse
din partea guvernului american și a age nțiilor guvernamentale. Implicarea guvernului în
sistemele crip tografice nu se limitează numai la statul american, un exemplu de astfel de
implicare este reliefat într -un articol din ziarul New York Times. Conform unui document
publicat pe site -ul său de internet de Government Commu nications Headquarters, o
organizație britanică, descrie rolul pe care l -a avut în descoperirea sistemelor cu cheie publică.
Documentul detaliază cum trei angajați ai guvernului britanic au descoperit sistemul de
criptare cu ch eie publică cu câțiva ani înaintea lui Hellman și Diffie. James Ellis este autorul
documentului, matematician și criptograf, decedat cu mai puțin de o lună înaintea apariției
articolului din New York Times. Ellis susține că o abordare mai practică a fost p ropusă de
Clifford Cocks, dar care în esență se asemăna mult cu algoritmul propus de Rivest, Shamir și
Adleman, de asemenea un algoritm asemănător cu cel propus de Diffie și Hellman a fost
descoperit de Malcolm Williamson. Cu siguranță istoricii vor cercet a aceste afirmații, însă în
ultimă instanță scrierea unei cărți corecte din punct de vedere istoric pe această temă ține de
declasificarea informațiilor deținute de mai multe guverne.
Inspirați de ideile revoluționare ale lucrării Diffie -Hellman, Ronald Ri vest, Adi Shamir și
Len Adleman au discutat posibilitatea realizării unui sistem criptografic care să realizeze
criptarea cu cheie publică. Într -o zi de aprilie Ronald Rivest a avut ideea criptosistemului, el a
notat totul pe o foaie pe care a trimis -o în ziua următoare colegilor săi. Astfel a luat naștere
criptosistemul RSA, conceput de ce trei care erau profesori la MIT la acea dată. RSA este un
cifru ce utilizează o pereche de chei, una publică și una privată (secretă) și se bazează pe
problema logaritm ului discret, adică pe dificultatea extragerii logaritmului dintr -un număr
foarte mare. Algoritmul i -a fost prezentat lui Martin Gardner pentru a fi publicat în revista
Scientific American , articolul publicat includea și o ofertă din partea autorilor, oric ine era
interesat de detaliile tehnice ale algoritmului era invitat să trimită un plic auto -adresat, timbrat
pentru a primi un raport complet asupra algorit mului. S -au primit mii de cereri din toate
colțurile lumii. NSA nu a fost desigur mulțumită de aces t lucru deoarece îl considera o
posibilă amenin țare la adresa siguranței naționale a SUA și a cerut oprirea imediată a
trimiterilor poștale. Însă ulterior s -a dovedit ca NSA nu avea nici o susținere legală pentru
cererea sa și trimiterile au continuat.Ca răspuns din partea societății civile la acest incident au
fost apoi înființate două ziare interna ționale care aveau ca obiect noutățile criptografice,
Cryptologia și The Journal of Cryptology. Publicarea algoritmului RSA nu a avut ca scop
23 evidențierea con strângerilor ce veneau din partea agențiilor guvernamentale ci mai de grabă
faptul că autorii doreau să -și facă ideea cunoscută, acest lucru având sa fie în detrimentul lor
deoarece nu au putut obține un brevet de invenție internațional asupra algoritmului .
24 Capitolul 2
Criptosisteme clasice
2.1 Cifrul lui Caezar
2.1.1 Descriere generală
Pentru a putea comunica informații private, oamenii au găsit adesea me tode de la cele
mai simple până la cele mai complexe. Pentru a face o ast fel de metodă să func ționeze este
nevoie ca partenerii de comunicație să se pună deacord asupra unei metode de secretizare a
informației transmise. Spre exemplu dacă un mesaj codificat ajunge la destinatar și acesta nu
cunoaște o metodă prin care să -l poată decodifica și citi informația care îi este transmisă,
atunci mesajul îi este complet inutil. Una dintre formele cele mai simple de codificare a
mesajelor despre care se spune că ar fi fost folosită de împăratul roman, Iulius Caesar, pentru
a comunica cu generalii săi este d eplasarea la dreapta sau stânga a alfabetului cu un număr de
poziții, fiecare literă fiind transformată în litera anterior existentă pe poziția respectivă. În
cazul de față se spune că Iulius Caesar folosea o deplasare cu 3 poziții la dreapta a alfabetulu i,
producând astfel o transformare care a fost foarte efi cientă în vremea aceea deoarece foarte
puțini dintre inamicii săi puteau citi sau scrie, fără să mai luăm în calcul metodele
criptanalitice. Presupunând că Caesar ar fi avut un dușman care nu ar fi fost analfabet, acesta
ar fi avut destul de puține șanse pentru a rezolva cifrul fiindcă din câte se știe cele mai vechi
metode criptanalitice descoperite în care se relatează despre metoda analizei frecvenței
datează din jurul anului 1000 e.n. și au fost descoperite în lumea arabă. În ciuda faptului că
este un cifru relativ ușor de "spart" a supraviețuit o perioadă destul de îndelungată, fiind
folosit de ar mata rusă până în jurul anului 1915, aceasta refuzând înlocuirea lui cu alte metode
mai complexe da torită faptului că soldații ruși nu puteau stăpâni foarte bine aceste metode.
Desigur, criptanaliștii germani și austrieci nu au întâmpinat dificultăți deosebite în descifrarea
mesajelor secrete ale armatei ruse. O complicare a acestui cifru ar putea fi tr ansformarea sa
într-un cifru de tip substituție polialfabetică în care după criptarea unei litere alfabetul folosit
să fie din nou deplasat cu un număr de poziții.
2.1.2 Descriere matematică
Acest mod de criptare poate fi definit și reprezentat în aritm etica modulo n,
transformând mai întâi literele alfabetului în cifre după cum urmează:
A = 0, B = 1,…, Z = 25.
Definiția 2.1.1. Fie a și b doi întregi și n un întreg pozitiv. Atunci scriem a = b(mod n)
daca n | (b — a). Fraza a = b(mod n) este numit ă congruen ță și va fi citită "a este congruent cu
b modulo n", întregul n fiind numit modul.
25 Dacă vom divide pe a și b prin n, vom obține un cât și un rest unde res tul va fi între
1,0n
, de aici stabilim următoarele relații a = q 1 n + r1 și b = q 2n + r 2, unde r1 și r2 între
1,0n
, iar conform definiției, trebuie să aibă loc relația r1 = r 2.
Expresia a mod n este interpretată ca fiind reducerea lui a modulo n. Arit metica modulo n
(adunarea(+), multiplicarea(*)) este definită analog ca în Z cu diferența că rezultatul este
redus modulo n. Următoarele proprietăți pot fi demonstrate foarte ușor:
1.
a, b
Zn, a + b
Zn
2.
a, b
Zn, a + b = b + a
3.
a, b,c
Zn, (a + b) + c = a + (b + c)
4. 0 este element neutru pentru adunare, adică
a
Zn, a + 0 = 0 + a = a
5. există un invers pentru fiecare a
Zn care este m-a. Astfel a+(m -a) = (m – a) + a = 0
6.
a,b
Zn, a*b
Zn
7.
a, b
Zn, a * b = b * a
8.
a, b,c
Zn, (a * b) * c = a * (b * c)
9. 1 este element neutru pentru multiplicare, adică
a
Zn,a*1 = 1*a = a
10. multiplicarea este distributivă față de adunare
a, b,c
Zn, (a+b) *c = a * c + b * c
Pentru a defini codul lui Caesar vom considera cazul alfabetului engle zesc care conține 26
de caractere și din acest motiv se va lucra în Z 26.
Definiția 2.1.2. Un sistem ciptografic bazat pe deplasare în Z26 este definit astfel: P = C = K =
Z26. Pentru 0 < K < 25 , definim:
ek(x) = (x + K)mod 26
dk(y) = (y — K)mod 26
unde x,y e Z26 și x reprezint ă textul în clar și y textul criptat.
2.1.3 Algoritm
Pentru criptarea efectivă a unui text se va face mai întâi o conversie de forma a
0,
b
1, c
2,…, z
25 și trecerea valorilor într -un vector de întregi care va reprezenta
mesajul, fie el în forma în clar sau forma criptată.
Algoritmul 2.1.1. Criptarea cu cifrul lui Caezar
1. criptare_Ca esar( Mn,k)
2. i
0
3. while (i<=n)
3.1. Ci ←M i +k
3.2. i++
4. return Cn
26 Algoritmul 2.1.2. Decriptarea cu cifrul lui Caezar
1. decriptare_Caesar( Cn,k)
2. i ← 0
3. while (i<=n)
3.1. Mi ←C i -k
3.2. i++
4. return Mn
2.1.4 Exemplu
Exemplul 2.1.1. Criptarea cu cifrul lui Caezar
Text în clar: ATACATI FLANCUL DREPT
Cheie: +3
Text criptat: DWDFDWL IODQFXO GUHSW
Exemplul 2.1.2. Decriptarea cu cifrul lui Caezar
Text criptat: WULPLWH DUPDWD
Cheie: -3
Text în clar : TRIMITE ARMATA
2.2 Cifrarea afină
2.2.1 Descriere generală
Cifrarea afină este un caz particular al cifrării prin substituție, fiind o cifrare monoalfabetică și
simetrică. Acest tip de cifrare este vulnerabil la toate ti purile de atacuri care sunt posibile
pentru cifrarea prin substituție precum și la alte tipuri de atacuri. Principala slăbiciune a
cifrului constă în faptul că dacă atacatorul poate descoperi textul în clar a două caractere (prin
analiza frecvenței, brute force, sau pur și simplu ghicind) poate apoi obține cheia rezolvând un
sistem de două ecuații cu două necunoscute.
2.2.2 Descriere matematică
Teorema 2.2.1. Congruen ța ax
b(mod n) are soluție unic ă pentru x
Zn pentru
b e Zn
dacă ș i num ai dac ă cmmdc(a, n) = 1.
Definiția 2.2.1. Fie a
1 și m
2 două numere întregi. Dac ă cmmdc(a,n)=1 spunem c ă a și m
sunt numere relativ prime între ele. Num ărul de numere relativ prime între ele din Z n este defi nit
ca fiind φ (m) (func ția Euler)
Definiția 2.2.2. Fie a
Zn, inversul lui a fa ță de opera ția de multiplicare în Z n se noteaz ă cu
27 a-1mod n și este un element a' care satisface relația aa' = a'a = 1(mod n). Pentru m fixat se
folose ște nota ția a-1 care înlocuie ște a-1 mod n.
Definiția 2.2.3. Un sistem criptografic afin cu n=26 (Z26) este definit ca fiind P = C = Z26 și
K = {(a, b)
Z26 x Z 26 : cmmdc(a, 26) = 1}
Pentru k = (a, b)
Z26 defini m func ția de criptare:
ek(x) = (ax + b)mod26
și func ția pentru decriptare
dk(y) = a-1 (y — b)mod26
unde x, y
Z26
2.2.3 Algoritm
Algoritmul criptării afine este o modificare trivială a algoritmului criptării prin metoda
lui Caesa r. Și în acest caz se cere o conversie prealabilă a textului identică metodei de criptare
a lui Caesar. Vom presupune imple mentată procedura cmmdc pentru calcularea celui mai
mare divizor comun, folosită pentru a verifica faptul că a și lungimea alfabetul ui folosit sunt
numere prime între ele, în caz contrar mesajul criptat nu va putea fi decriptat.
Algoritmul 2.2.1. Criptare afină
1. criptare_afina(M n,k,lung_alfabet)
2. if (cmmdc(a,lung_alfabet)>1)
2.1 incheie_procedura
3. i <— 0
4. while(i<n)
4.1. Ci = a* Mi + b
4.2. i++
5. return Ci
Algoritmul 2.2.2. Decriptare afină
1. decriptare_afina(C n,k,lung_alfabet)
2. A ← 1/a
3. B ← -b/a
4. k ← (A, B)
5. criptare_afina(C n,k,lung_alfabet)
28 2.3 Codul Hill
2.3.1 Descriere generală
Există două metode de bază prin care se poate evita un atac criptanalitic prin analiza
frecvenței asupra unui text criptat. Prima metodă presupune criptarea polialfabetică a textului,
și anume pentru aceeași literă a alfabetu lui textului în clar să existe mai multe litere diferite în
textul criptat. Această soluți e a fost oferită de criptosistemul Vigenere și alte criptosisteme
poli-alfabetice. A doua abordare este criptarea textului în clar prin împărțirea sa în grupuri de
n litere și criptarea grupului spre deosebire de criptarea literă cu literă. Sistemul Playfa ir
ascunde relativ bine comportamentul specific al literelor, dar un sistem care să fie capabil să
cripteze un număr variabil de litere ar fi fost de preferat.
În 1929 Lester S. Hill a propus un sistem algebric capabil să cripteze gru puri de câte n
litere , unde n este un întreg pozitiv. La vremea respectivă calculele aferente criptării și
decriptării ar fi putut fi făcute pe o foaie de hârtie fără prea multă greutate pentru grupuri de
până la 5 litere. Dincolo de această cifră dificultatea calculelor ar fi devenit o povară. Odată
cu difi cultatea efectuării calculelor crește și dificultatea spargerii cifrului, se pare că un astfel
de sistem care ar fi folosit grupuri de 10 litere ar fi destul de greu de spart. Se pare ca Hill
împreună cu un partener, Weisne r au depus o cerere de brevetare a unei mașini mecanice
(denumită Message Protector) care folosea matrici involuntare (A = A-1) pentru a ușura munca
criptării și decriptării mesajelor. Dispozitivul inventat de ei este descris în specificațiile
tehnice ca f iind mai degrabă un identificator de authenticitate. Împreună cu mașina venea o
metodă prin care inventatorii propuneau unităților bancare o modalitate prin care să verifice
dacă datele de pe cecuri au fost modificate. Ideea lor nu a avut succes, majoritat ea
potențialilor clienți nefiind interesați de o mașină care putea să multiplice matrici.
Codul Hill implementat de mașina pe care a brevetat -o presupune ca toate calculele să
fie făcute modulo 26. Înainte de a începe criptarea efectivă lite rele alfabetul ui vor fi
numerotate, fiecare primind numere de la 0 la 25 inclu siv. Pentru criptarea textului se alege
aleator o matrice inversabilă (Kn
K) de dimensiune n x n care va reprezenta cheia de
criptare. Textul în clar va fi împărțit în grupuri de mărime n care vor fi considerate matrici
(Mn
P)de dimensiune n x 1. Pentru a cripta mesajul vom considera Cn
C definită astfel:
Cn = A n x Mn(mod26). Decriptarea se va face calculând inversa matric ii An astfel Dn = A-1 x
Cn(mod 26)
2.3.2 Descriere matematică
Acest mod de criptare se bazează pe aritmetica modulo -n a matricilior pătratice din
Z26. În cadrul aritmeticii modulo -n a matricilor pătratice aduna rea și multiplicarea (notate + și
29 respect iv, *) sunt definite analog operațiilor din Mmxm(Z). Diferența constă în faptul că
rezultatul este redus modulo -n. La fel ca în cazul utilizării cifrului Caesar literele alfabetului
trebuie transformate în cifre din intervalul [0, 25]. Înainte de a defini acest tip de criptosistem
trebuie introduse câteva noțiuni din aritmetica matricilor modulo -n.
Definiția 2. 3.1. Fie matricile A și B aparținând Mmxm(Zn) spunem c ă A B dac ă între a ij A
și bij B exist ă relația a ij = bij, cu i,j = 1, m.
Definiția 2. 3.2. Fie A o matrice, A Mmxm(Zn) spunem despre matricea A c ă este inversabil ă
dacă există o matrice B Mmxm(Zn) astfel încât:
AB BA I
B se va numi inversa lui A și vom nota acest lucru prin A-1 = B mod n.
Definiția 2. 3.3. Fie A o matrice, A Mmxm(Zn) determinantul matricii A este:
det(A) = a(mod n).
Teorema 2. 3.1. Daca A este o matrice aparținând M mxm(Zn), A este inversa bilă dacă și numai
dacă cmmdc(det( A), n) = 1.
Definiția 2. 3.4. Un criptosistem bazat pe cifrul Hill, unde lungimea alfabetului este n =
26(Z 26), este definit pentru P = C = Z26 și
K = {A Mmxm(Z26) : cmmdc(det(A), 26) = 1}
pentru cheia k = A K, textul în clar p P scris sub form ă de vector cu m componente
definim func ția de criptare
ek(x) = Ax(mod26)
și funcția pentru decriptare
dk(y) = A-1y(mod 26)
unde x,y Mmx1(Zn).
2.3.3 Algoritm
Pentru algoritmii de mai jos se presupune că literele textului în clar dar și ale textului
criptat sunt puse intr -o corespondență cu cifrele de la 0 la 25 de forma: a ↔ 0, b ↔ 1, … , z ↔
25. După crearea acestei corespondențe textul în clar trebuie scris sub forma a t vectori
obținuți prin împărțirea textului în clar în grupuri de câte m elemente. Dacă pentru ultimul
vector avem un număr de elemente mai mic decât m vom repeta ultima literă pentru
completarea vectorului. Algoritmul pentru criptare este următorul, (toate operațiile sunt
modulo -n):
Algoritmul 2. 3.1. Criptare Hill
1. criptare_hill(M n,k,n)
30 2. if cmmdc(det(M n),n)>1
2.1 incheie_procedura
3. for( i = 1,m)
3.1 while(col<t)
3.1.1 for( j = 1,m)
3.1.1.1 Ci,j = A i,j *M j,t
3.1.2 col++
4. return Ci,j
Algoritmul pentru decriptare este asemănător cu cel pentru criptare cu sin gura diferență ca de
data aceasta se folosește matricea A-1 care trebuie cal culată apriori, ea fiind înmulțită cu
matricea Cn, matricea textului criptat.
Algoritmul 2. 3.2. Decriptare Hill
1. decriptare_hill(C n,k,n)
2. for(i = 1,m)
3. while(col<t)
3.1 for(j = 1,m)
3.1.1 Mij =
1
,
jiA * Cj,t
3.2 col++
4. return M i,j
31 Capitolul 3
Criptosisteme simetrice
Criptosisteme le bazate pe cheie simetrică asigură confidențialitatea me sajelor transmise
între doi parteneri de comunicație prin folosirea aceleiași chei atât pentru criptare cât și pentru
decriptare. Acest fapt este motivul pentru care aceste criptosisteme sunt numit e cu cheie
simetric ă sau criptosisteme cu cheie privat ă. Un presupus adversar, Eve, care va intercepta un
mesaj transmis între cei doi parteneri de comunicație nu va putea obține informa ții
semnificative despre textul transmis chiar dacă cunoaște detalii despre algoritmul folosit atât
timp cât nu cunoaște cheia folosită pentru criptare. Ne propunem în acest capitol să analizăm
diferențele dintre două categorii ce aparțin de criptosistemele cu cheie simetrică sau cheie
privată. Diferen țele între cele două categorii pleacă de modul în care se face criptarea, și
anume dacă textul în clar este criptat caracter cu caracter sau bit cu bit este vorba de un cifru
de tip stream sau flux. Dacă datele sunt criptate sub formă de blocuri de text sau biți, atunci
acest cifru este un cifru de tip block.
Schema de aplicare a unui algoritm simetric
Definiția 3.0.5. Un criptosistem cu cheie simetric ă este un tuplu de forma (P,C,K,E,D) care
îndepline ște urm ătoarele cerin țe:
1. P este un s et finit de posibile texte în clar
2. C este un set finit de posibile texte criptate
3. K este un set finit de posibile chei de criptare
32 4. Pentru fiecare cheie k K exist ă o regul ă de criptare e k E și o regul ă corespunz ătoare de
decriptare d k D. Fiecare e k : P → C și dk : C → P funcționeaz ă astfel încât:
dk(ek(x)) = x
pentru orice text în clar x P.
Algoritmii folosiți pentru a calcula ek(x), unde x P este un text în clar, și dk(y), unde y
C este un text criptat, sunt făcuți publici, deci oricine poat e cripta sau decripta un mesaj dacă
deține cheia potrivită. Pentru a stabili un criptosistem cu cheie privată Alice și Bob trebuie să
folosească o cheie comună care va fi folosită atât pentru a cripta, dar și pentru a decripta.
Această cheie trebuie păstra tă secretă astfel încât adversari precum Eve să nu o poată accesa.
Desigur o cerință imperativă a unui astfel de criptosistem este ca atunci când se cunoaște
textul criptat, y P, să fie imposibil să se calculeze rezultatul funcției dk(y).
Dintre toate cr iptosistemele cunoscute, cele cu cheie simetrică sunt prin tre cele mai
rapide, acest fapt le face foarte potrivite pentru a cripta volume mari de date. Dacă Alice și
Bob vor dori să schimbe mai multe imagini fără ca Eve să poată să le vadă, ei vor trebui mai
întâi să schimbe o cheie a unui algoritm de criptare cu cheie simetrică. Pentru aceasta trebuie
mai întâi să stabilească un canal de comunicație securizat. Așa cum se va arăta în capi tolele
următoare se pot folosi criptosisteme bazate pe cheie publică pentru transmiterea cheii
simetrice pentru ca apoi cei doi să dispună de o posibi litate de criptare rapidă. Putem spune
deci că cele două criptosisteme se complementează reciproc pentru a oferi modele de
securitate pentru medii nesigure de comunicație.
3.1 Cifrare de tip flux (stream)
Un cifru de tip stream este un algoritm de criptare cu cheie simetrică. Astfel de algoritmi
pot fi concepuți să fie extrem de rapizi, mult mai rapizi decât oricare alt algoritm te tip bloc.
În timp de algoritmii de tip bl oc lucrează cu blocuri de biți, algoritmii de tip stream operează
cu unități mai mici de date, de obicei la nivel de bit. Criptarea anumitor porțiuni de text în clar
cu un algoritm de tip bloc va avea ca rezultat același text criptat atunci când se foloseș te
aceeași cheie, cu un algoritm de tip flux de date aceste subdiviziuni ale textului vor varia în
textul criptat, acest lucru depinzând de momentul în care vor fi întâlnite în textul în clar atunci
când se desfășoară procesul de criptare.
Un cifru de tip flux generează ceea ce se cheamă un flux al cheii de crip tare, iar criptarea
este obținută prin combinarea fluxului cheii de criptare cu textul în clar. De obicei se folosește
operația XOR la nivel de bit. Ge nerarea cheii de cifrare poate fi făcută indep endent de textul
în clar sau de textul criptat, în acest caz se spune că cifrul de tip flux este sincron. În ca zul în
care generarea cheii de criptare se face dependent de mesaj cifrul se numește asincron.
33 Majoritatea algoritmilor sunt de primul tip.
Definiția 3.1.1. Fie K mulțimea de chei posibile și P mulțimea mesajelor posibile. În acest caz
elementele lui P se vor numi caractere. Un cifru de tip stream este definit prin e k : P x K → C
unde e k are forma:
ek(p, k) = c = c1c2c3 …
funcția e k cripteaz ă mesajul p = p 1p2p3 . . . P ca fiind un șir de caractere c = c1c2c3… C
folosind o cheie k = k 1k2k3… K. Inversa fun cției e k este funcția d k definit ă astfel:
dk(c, k) = p 1p2p3 . . . = p
care pentru acelea și elemente enumerate va avea ca rezultat textu l în clar.
În mod tipic caracterele din P și cheile din K sunt cifre binare sau octeți, pentru a păstra
compatibilitatea cu sistemele de operare, unde intrările și ieșirile sunt realizate prin
intermediul fluxurilor de date. Desigur fluxul cheii de criptar e trebuie păstrat secret. Deseori
nu cheia de criptare este cea care este cunoscută de ambele părți implicate în comunicație ci o
cheie secretă din care se poate genera cheia de criptare.
3.1.1 Codul Vernam sau One Time Pad
Descriere generală
Este poat e unul dintre cele mai faimoase exemple de cifru care este teore tic imposibil de
"spart". Cifrul a fost inventat de Gilbert Vernam, inginer la AT&T, și perfecționat împreună
cu Joseph Mauborgne, căpitan în cadrul armatei S.U.A.. În acest cifru textul în c lar este
combinat cu o cheie obținută aleator. Mai precis fiecare caracter sau fiecare bit al mesajului,
împreună cu fiecare bit al cheii, este supus operației XOR pe biți. Astfel lungimea cheii
trebuie să fie cel puțin egală cu lungimea mesajului. Din pun ct de vedere teoretic nu există
nici o posibilitate de a decripta mesajul fără a cunoaște cheia. Cheia este deci un element de
securitate important în cadrul acestui cifru, ea poate fi folosită o singură dată și obținută în
mod complet aleator. Altfel cifr ul poate fi compromis foarte ușor. Dacă în generarea cheii se
folosește un algoritm care generează biții cheii respectând o structură atunci se curitatea
cifrului este redusă considerabil, deoarece în acest caz criptograma rezultată respectă o
structură ș i poate fi supusă unor atacuri criptanalitice. Cheia este folosită numai o singură dată
pentru a cripta și decripta un me saj, de aici numele de "one time pad". Spre exemplu dacă
aceeași cheie ar fi folosită pentru două mesaje atunci un atacator care se pr esupune ar fi
interceptat cele două mesaje ar putea foarte ușor calcula c c din cele două criptograme și ar
obține cheia, lucru care inevitabil conduce la obținerea de informații despre textul în clar.
Pe lângă aceasta sunt dezavantaje evidente ale cifr ului Vernam în ceea ce privește
generarea cheii de criptare și transportul cheii între părțile co municante. Totuși cele mai
34 practice metode de criptare folosesc conceptele prezente în acest cifru. Generatorul aleator
este înlocuit cu un generator pseudo -aleator, cheile obținute în urma utilizării unui astfel de
generator sunt asemănătoare cu cele ale generatoarelor aleatoare cu diferența că sunt obținute
în urma unui algoritm determinist. În practică astfel de genera toare se bazează pe modurile de
operare ale cifrurilor de tip bloc și pe regiștrii de deplasare cu feedback sau revenire.
Avantajul acestui cifru constă în faptul că poate fi dovedit a fi sigur. Pre supunând că un
atacator poate intercepta un mesaj care conține un bit. Alice și Bob vor să schim be mesajul
da=1, nu=0. Anterior transmiterii mesajului Alice și Bob au schimbat cheia k obținută în urma
unei experiențe aleatoare. Mai întâi se presupune că oricare din mesaje poate fi transmis, fie
da, fie nu. Adversarul, Eve interceptează criptograma c care în mod evident criptează fie da,
fie nu. Din moment ce cheia a fost aleasă aleator Eve nu poate decât să ghicească conținutul
mesajului deoarece exista ½ șanse ca mesajul să fie da și ½ șanse ca mesajul să fie nu. Însă Eve
știa aceste lucruri înainte să inter cepteze mesajul. Deci nu a obținut nici o informație
semnificativă în urma interceptării mesajului. Acest lucru rămâne valabil și în cazul în care
una din posibilități are probabilitate mai mare de a se întâmpla.
Un mare dezavantaj al cifrului Vern am constă în faptul că nu protejează mesajul împotriva
eventualelor modificări survenite pe parcursul transmi siei. Dacă un atacator va modifica
mesajul astfel încât după decriptare să aibă sens, destinatarul nu va putea observa acest lucru.
Descriere mate matică
Definiția 3.1.2. Un criptosistem bazat pe cifrul Vernam este un tuplu de forma (P,C,K,E,D)
care trebuie s ă îndeplineasc ă următoarele condiții:
1. P este un set finit de posibile texte în clar
2. C este un set finit de posibile texte criptate
3. K este un set finit de posibile chei de criptare
4. P=K=C={0,1} și funcția de criptare este definit ă astfel e k : {0,1} x {0,1} → {0,1}
ek(p, k) = p k
unde p este un mesaj din P și k este o cheie din K. Pentru func ția de decrip tare d k : {0,1} x
{0,1} → {0,1} consider ăm c din C si avem:
dk(c, k) = c k
pentru aceste operații p este de forma p = p 1p2p3 . . ., k este deforma k = k 1k2k3… și c
este deforma c = c1c2c3.. .. Prin semnul am simbolizat XOR pe biți (sau exclusiv).
Algoritm
Algoritmul 3.1.1. Algoritm criptare V ernam
1. criptare_vernam(P n, Kn)
2. i ← 0
35 3. while(i<=n)
3.1. C i ← P i Ki
4. return C
Algoritmul 3.1.2. Algoritm decriptare Vernam
1. decriptare_vernam(C n, Kn)
2. i ← 0
3. while(i<=n)
3.1. P i ← C i Ki
4. return P
Algoritmul de mai sus ar putea fi înlocu it cu un apel al funcției de crip tare pentru textul
criptat și cheia Kn, deoarece în principiu se fac același operații.
Exemplu
Înainte de a prezenta un exemplu vom presupune că literele alfabetului su feră o conversie
de forma celor de la criptosistemele clasice: a ↔ 0, b ↔1, c ↔ 2,…, z ↔ 25.
Exemplul 3.1.1. Criptare Vernam
Presupunem că Alice dorește să transmită mesajul "TRIMIT AJUTOR" folosind un canal
de comunicație nesigur. Atât ea cât și Bob se presupune că au obținut printr -o metodă
necunoscută un set de chei generate absolut aleator și că una dintre aceste chei este
"AFVKGHOPERTS". Pentru a cripta mesajul ei vom proceda în felul următor, operațiile sunt
în aritmetica modulo -26.
Text în clar T R I M I T A J U T O R
Cheie A F V K G H O P E R T S
Text în clar 19 17 8 12 8 19 0 9 10 19 14 17
Cheie 0 5 21 10 6 7 14 15 4 17 19 18
Criptograma 19 22 3 22 14 0 14 24 14 10 7 9
Text criptat T W D W O A O Y O K H J
Exemplul 3.1.2. Decriptare Vernam
Pentru a obține textul în clar din textul criptat de mai sus pur și simplu scădem din valorile
literelor criptogramei valorile literelor cheii. Acol o unde valorile vor fi negative, ținând cont
de faptul că lucrăm în aritmetica modulo -26 aceste valori for semnifica 26 — V, unde V este
valoarea negativă.
36 Text criptat T W D W O A O Y O K H J
Cheie A F V K G H O P E R T S
Criptograma 19 22 3 22 14 0 14 24 14 10 7 9
Cheie 0 5 21 10 6 7 14 15 4 17 19 1 8
Text în clar 19 17 -18 12 8 -7 0 9 10 -7 -12 -9
Text în clar T R I M I T A J U T O R
3.1.2 SEAL – Software Encryption Algorithm
Descriere generală
Algor itmul prezentat în continuare se află la a treia versiune. Proiectul SEAL a început în
vara anului 1992 și creatorii săi au dorit să ofere un răs puns la cerințele existente atunci pe
piață cu privire la un algoritm sigur, rapid și cu implementare software eficientă. În
construcția algoritmului s -a avut în vedere faptul că algoritmul trebuia să funcționeze
excepțional pe un set restrâns de cerințe minime ale sistemului, mai degrabă decât sa func –
ționeze acceptabil pentru o gamă largă de componente hardware. Singurul aspect important cu
adevărat era viteza cu care se făcea criptarea, desigur neignorând elementul de securitate. În
total au fost luate în considerare 9 propuneri pentru ce avea să fie cifrul SEAL. Pentru fiecare
din cele 9 propu neri cei doi auto ri ai cifrului urmau un drum asemănător în ceea ce privește
testarea securității cifrului. Phillip Rogaway pregătea specificațiile criptosistemului după care
i le prezenta lui Don Coppersmith, acesta încerca diverse atacuri criptanalitice împotriva
cifrulu i. Atacurile erau concepute de așa na tură pentru a se putea pune deacord asupra ideilor
principale pe care cifrul trebuia să le urmeze. Desigur rezultatele atacurilor erau analizate de
Roga way și slăbiciunile cifrului eliminate. Prima versiune a cifrului a fost pre zentată prima
dată în decembrie 1993. Versiunea prezentată în continuare este versiunea 3.0, de aceea vom
înțelege că acronimul SEAL desemnează versiunea 3.0 a acestui cifru.
SEAL este o familie de funcții pseudo -aleatoare: sub controlul unei c hei, mai întâi
preprocesată într -un set de tabele, algoritmul produce dintr -o secvență de 32 de biți, denumită
"index de poziție", un flux de biți al cheii de criptare, care în mod esențial poate fi de lungime
arbitrară. Criptarea se face apoi în maniera c ifrului Vernam, aplicând operatorul XOR fluxului
cheii și mesajului în clar. La fel ca în cazul cifrului Vernam, fluxul cheii trebuie fo losit o
singură dată.
SEAL este un cifru rapid în comparație cu alți algoritmi din clasa sa. Pe un procesor pe 32
de bi ți SEAL poate cripta un octet de text la fiecare 4 cicli de ceas. Acest fapt îl face de 10 ori
mai rapid decât DES.
În aplicațiile tipice care au nevoie de criptografia implementată în soft ware, criptarea
37 datelor este necesară atunci când doi parteneri do resc să comunice pe durata unei sesiuni. În
aceste cazuri cheia de criptare k este determinată în faza de stabilire a sesiunii. De obicei
această fază durează câteva milisecunde și nu este o operație critică în ceea ce privește timpul
trecut până la închei erea ei. Este deci acceptabil, în cazul majorității aplica țiilor, ca în faza de
stabilire a sesiunii să se piardă câteva milisecunde pentru stabilirea conexiunii dintre cheia
k(varianta scurtă a cheii) și o reprezentare a unei transformări criptografice s pecializate a
acestei chei. Aplicațiilor care au nevoie de o fază de stabilire a acestor parametri mai rapidă
nu le este indicată folosirea acestui cifru.
Descriere matematică
Funcția SEAL este un tip de obiect criptografic denumit familie de funcții
pseud oaleatoare(PRF). Sub controlul unei chei k de lungime 160 biți, SEAL produce dintr -un
un șir de caractere, n, de 32 de biți, un șir de caractere de lungime L, SEAL(k, n, L). Șirul L
poate fi oricât de mare, în funcție de ce rințele aplicației care implemen tează algoritmul,
mărimi ale lui L cuprinse între câțiva octeți și câteva mii de octeți sunt însă anticipate. Desigur
mărimea cheii k poate fi mai mare, însă ea va fi adusă la forma k = SHA — 1(k'), unde k’ este
cheia de mărime arbitrară, iar SHA -1 este f uncția de hash cu același nume.
SEAL fiind parte a familiei de funcții pseudo -aleatoare, SEAL(k, • , L) ar trebui să "arate
ca o funcție aleatoare". Afirmația precedentă se referă la faptul că alegând aleatoriu o cheie k
din {0, 1}160, adversarul, Eve, va trebui să ghicească dacă outputul pe care îl deține este
rezultatul funcției SEAL( k, •, L) sau este rezultatul unei funcții cu adevărat aleatoare R(•).
Scopul algoritmului este acela de a obține o probabilitate apropiată de ½ cu care Eve poate
ghici corec t.
În cazul unu cifru de tip flux, criptarea unui mesaj nu depinde numai de cheia k și mesajul
p, dar și de "poziția" n a mesajului în cadrul fluxului de date. Criptarea mesajului p la poziția
n este dată de {n, x SEAL(k, n, L)), unde L = | x |. În cadru l altor aplicații n ar putea fi
indexul unor date de pe un disc.
Cifrul este bazat pe tabele după care se va face criptarea. Cheia k va fi folosită doar pentru
generarea acestor tabele. Tabelele vor fi specificate folosind o funcție G. Pentru k un șir de
caractere cu lungimea de 160 biți și i un întreg cuprins în intervalul 0 < i < 232, Ga(i) este o
valoare pe 160 de biți. Funcția G este funcția de compresie din Secure Hash Algorithm SHA –
1.
Reindexăm funcția G pentru a construi o funcție Γ a cărei imagine e ste un cuvânt de 32 de
biți. Funcția Γ este definită astfel: Γa(i) = H iimod5 unde
jH5
0
||
15
1jH ||
25
2jH ||
35
3jH ||
45
4jH = G a(j)
unde j = [i/5]. Astfel un tab el al valorilor funcției Γ este identic cu un tabel al valorilor
38 funcției G citit de la dreapta la stânga și de sus în jos. Definim:
T[i] = Γ a(i) pentru 0 < i < 512
S[j] = Γa(0x1000 + j) pentru 0 < j < 256
R[k] = Γa(0x2000 + k) pentru 0 < k < 256.
Pentru a cripta un kilobyte din SEAL(k, n, L) sunt necesare 4 cuvinte din R, așadar dacă
cineva a dat variabilei Lmax valoarea maximă posibilă pentru L, atunci va calcula R[k] pentru 0
< k < 4[L max/8192]. Pentru mărimea maximă permisă de 64 Kiloocteți vor fi necesare 207
apeluri ale funcției de compresie SHA -1.
O rundă a acestui cifru se referă la execuția liniilor 1 → 8 în timp ce o iterație presupune
execuția liniilor 1 → 11. Sunt deci 8 runde pentru fiecare iterație executată.
Algoritm Exemplu
Figura 3.1: Funcția de inițializare a cifrului SEAL
39
Figura 3.2: Funcția SEAL
40 Capitolul 4
Sisteme de criptare prin chei publice (asimetrice)
Spre deosebire de sistemele de criptare bazate pe chei secrete, care presupun o singură
cheie c unoscută de emițător și receptor, sistemele bazate pe chei publice folosesc două chei:
una publică și alta privată.
Cheia publică este pusă la dispoziția oricărei persoane care dorește să transmită un mesaj
criptat.
Cheia privată este utilizată pentru decr iptarea mesajului, iar nevoia de a face schimb de
chei secrete este eliminată.
Pentru înțelegerea sistemului, sunt necesare următoarele lămuriri:
• cheie publică nu poate decripta un mesaj criptat;
• se recomandă ca o cheie privată să nu deriveze dintr -o cheie publică;
• un mesaj care a fost criptat printr -o anumită cheie poate fi decriptat cu altă cheie;
• cheia privată nu este făcută publică.
Dacă notăm cu C un text criptat și cu P un text clar (P este notația consacrată pentru plain
text), iar Kp este cheia publ ică și Ks cheia privată (secretă), procesul este ilustrat astfel: C =
Kp(P) și P = Ks(C) . Și invers este adevărat: C = Ks(P) și P = Kp(C) .
Criptografia prin chei publice este posibilă în aplicațiile care funcționează într -un singur
sens. O funcție în sens unic este aceea care este ușor de calculat într -o direcție, dar este dificil
de calculat în sens invers. Pentru o astfel de funcție, dacă y = f(x), este simplu de determinat
valoarea lui y dacă se cunoaște x, dar este foarte dificil să -l determini pe x cunoscându -l pe y.
Într-o astfel de situație se află căutările telefonice. Este ușor să găsești numărul cuiva dacă știi
numele și adresa, dar este foarte dificil să găsești pe cineva într -o carte de telefon cunoscându –
i doar numărul de telefon. Pentru ca func țiile cu sens unic să fie utile în contextul criptografiei
bazate pe chei publice ele trebuie să aibă o trapă , adică un mecanism secret care să permită
realizarea cu ușurință a funcției inverse funcției în sens unic. Printr -o astfel de modalitate se
poate obține x dacă se dă y.
În contextul criptografiei bazate pe chei publice este foarte dificil să se calculeze cheia
privată din cheia publică dacă nu se știe trapa.
De-a lungul anilor s -au dezvoltat mai mulți algoritmi pentru cheile publice. Unii dintre ei
se folosesc pentru semnătura digitală, pentru criptare sau în ambele scopuri.
Din cauza calculelor numeroase solicitate de criptarea prin chei publice, aceasta este de la
1.000 la 10.000 de ori mai înceată decât criptografia prin chei secrete. Astfel, au a părut
41 sistemele hibride care folosesc criptografia prin chei publice pentru transmiterea sigură a
cheilor secrete utilizate în criptografia prin chei simetrice.
Dintre algoritmii importanți ai cheilor publice, amintim Diffie -Hellman, RSA, El Gamal
Knapsak și curba eliptică, foarte utilizați fiind primii doi algoritmi.
Schema de aplicare a unui algoritm asimetric
4.1 Schimbul de chei Diffie -Hellman
Metoda schimbului de chei Diffie -Hellman, cunoscută și ca metoda de distribuție a
cheilor publice, poartă n umele a doi specialiști de la Standford University, Whitfield Diffie și
Martin Hellman. În anul 1976, ei au inventat o metodă prin care două părți pot cădea de
comun acord să comunice prin mesaje secrete fără să fie nevoie de o terță parte, de un schimb
off-line sau de transmiterea vreunei valori secrete între ele.
Independent, Ralph Merkle a venit cu o soluție de distribuție a cheilor publice, numai că
metoda propusă implica substanțiale cheltuieli pentru efectuarea calculelor și a transmisiei.
Varianta re alizată de Diffie și Hellman a fost numită sistemul distribuției cheilor publice sau
al schimburilor de chei publice .
Metoda Diffie -Hellman se bazează pe conceptul perechii de chei publică -privată.
Protocolul începe cu fiecare parte care generează independ ent câte o cheie privată. În pasul
următor, fiecare calculează câte o cheie publică, aceasta fiind o funcție matematică a cheilor
private respective. Urmează schimbul de chei publice. În final, fiecare dintre cele două
persoane calculează o funcție a propr iei chei private și a cheii publice a celeilalte persoane.
Matematica este cea care va face să se ajungă la aceeași valoare, care este derivată din cheile
lor private. Ele vor folosi valoarea ca pe cheie a mesajului.
Diffie și Hellman folosesc exponențiere a în aritmetica modulară pentru a calcula cheile
42 publice și cheia mesajului. Aritmetica modulară este ca și aritmetica standard, cu excepția
faptului că folosește numere numai în intervalul 0 la N, numit modulo. Atunci când o operație
produce un rezultat c are este mai mare sau egal cu N, N este scăzut repetat din rezultat până
când valoarea se încadrează în intervalul 0 la N -1 (ca și cum s -ar împărți la N și se ia în seamă
restul). De exemplu, 3+4 mod 5 = 2. Dacă rezultatul este negativ, N se adaugă acestui a până
când se va încadra în intervalul 0 la N -1. De exemplu, 3 -8 mod 7 = -5 mod 7 = 2.
În aritmetica modulară, exponențierea este o funcție într -un singur sens. Aceasta
înseamnă că este ușor de calculat un număr y = gx mod N pentru o valoare secretă x, însă este
mult mai dificil să se calculeze x din y, dacă numerele sunt suficient de mari, ca de exemplu o
lungime de câteva sute de cifre (noi presupunem că g și N sunt cunoscute). Aceasta este
referită ca și problema logaritmului discret pentru că x este lo garitm din y în baza g (mod N),
iar numerele sunt finite și întregi.
Cu metoda Diffie -Hellman a schimbului de chei publice, Alice și Bob stabilesc cheia
mesajului secret după cum urmează. Alice generează o cheie secretă xa și Bob o cheie secretă
xb. După a ceasta, Alice calculează o cheie publică ya, care este g ridicat la puterea xa modulo
p, unde p este un număr prim (adică nu poate fi descompus în produsul a două numere), g
fiind mai mic decât p. Identic, Bob calculează o cheie publică yb, prin ridicarea lui g la
puterea xb modulo p. Ei vor schimba valorile publice ale acestora. Apoi, Alice ridică cheia
publică a lui Bob la puterea exponentului său, xa modulo p, în timp ce Bob ridică cheia
publică a lui Alice la exponentul său, xb modulo p. Amândoi vor obț ine același rezultat, g
ridicat la puterea xa și xb, iar rezultatul obținut va fi folosit de amândoi drept cheia K a
mesajului. Matematic, totul se va exprima astfel:
ya = gxa mod p yb = gxb mod p
K = yaxb mod p = ybxa mod p = gxa*xb mod p
Deși în practică se folosesc numere foarte lungi, de câteva sute de cifre, pentru a ajuta la
înțelegerea modului de funcționare, vom folosi numere mici. Exemplul 1
Să presupunem că p = 7, g = 3, cheia lui Alice xa = 1 și a lui Bob xb = 2 Vom avea:
• Alice calculează cheia s a publică: ya = gxa mod p = 31 mod 7 = 3
• Bob calculează cheia sa publică: yb = gxb mod p = 32 mod 7 = 2
• Alice calculează K = ybxa mod p = 21 mod 7 = 2
• Bob calculează K = yaxb mod p = 32 mod 7 = 2 sau
K = gxa*xb mod p = 32×1 mod 7 = 9 mod 7 = 2.
Exemplul 2
Să presupunem că p = 5, g = 4, cheia lui Alice xa = 3 și a lui Bob xb = 2
• Alice calculează cheia sa publică: ya = gxa mod p = 43 mod 5 = 4
43 • Bob calculează cheia sa publică: yb = gxb mod p = 42 mod 5 = 1
• Alice calculează K = ybxa mod p = 13 mod 5 = 1
• Bob cal culează K = yaxb mod p = 42 mod 5 = 1 sau
K = gxa*xb mod p = 43×2 mod 5 = 4096 mod 5 = 1.
Se observă că în ambele cazuri K ia valori identice, 2, respectiv 1.
Metoda Diffie -Hellamn, precum și variantele ei sunt utilizate în câteva protocoale de
securitate a rețelelor și în produse comerciale, inclusiv la AT&T 3600 Telephone Security
Device, la Fortezza card – o variantă de carduri criptate, și la Pretty Good Privacy pentru
criptarea e -mail-urilor și a unor fișiere.
4.2 Sistemul RSA
RSA provine de la numele de familie ale inventatorilor săi, Rivest, Shamir și Adleman.
Pe vremea când Diffie și Hellman au inventat metoda distribuției prin chei publice, aceștia au
gândit și la un alt concept mult mai performant, dar n -au găsit soluția implementării lui –
criptog rafia prin chei publice. Prin aceasta, fiecare persoană are o pereche de chei publică și
privată, unică, pe termen lung. Componenta publică, transmisibilă prin Internet și partajată cu
toată lumea, este folosită pentru criptarea datelor, în timp ce compone nta privată, greu de
calculat pe baza cheii publice, este folosită pentru decriptare. Criptografia prin chei publice
este numită și „criptografie prin două chei” și „criptografie asimetrică”. Metodele
convenționale, descrise anterior, care apelează la o si ngură cheie, sunt referite ca și
„criptografie printr -o singură cheie”, „criptografie prin cheie privată”, „criptografie prin cheie
secretă”, „criptografie simetrică” și „criptografie convențională”.
La scurt timp după ce Diffie și Hellman au lansat ideea revoluționară a criptografierii prin
chei publice, trei profesori de la MIT (Massachusetts Institute of Technology), Ronald Rivest,
Adi Shamir și Leonard Adleman, au venit cu soluția implementării ei. Varianta propusă se
numea RSA. Concomitent, Hellman și Merkle au inventat o altă metodă, numită „ trapdoor
knapsacks ”, bazată pe alt model matematic. Oricum, modelul lor a fost spart la începutul
anilor 1980.
Pentru a transmite un mesaj cu text clar către Bob, folosind sistemul cheilor publice, gen
RSA, Alice g enerează cheia K a mesajului și o folosește prin intermediul criptosistemului
convențional, cum ar fi DES, pentru criptarea mesajului. Utilizând criptografia prin chei
publice, ea, de asemenea, criptează K, sub cheia publică a lui B, denumită K Bobpub . Apoi , ea
transmite atât cheia criptată, cât și mesajul criptat către Bob. Bob, la rândul său, apelează la
propria lui cheie privată, denumită K Bobpriv , pentru a decripta cheia K a mesajului, apoi el
folosește cheia K pentru decriptarea mesajului. Modelul este redat sub formă grafică în figura
44 4.1.
Teoretic, Alice poate să transmită textul către Bob folosind doar criptarea prin cheia
publică a lui Bob, apelând doar la criptografia prin cheie publică. În practică, însă, nu se
întâmplă așa datorită încetinirii pro cesului de transmitere prin mulțimea calculelor de efectuat.
E mult mai rapid să folosești o metodă convențională de mare viteză pentru criptarea
mesajului, rezervând metoda cheii publice doar pentru distribuția cheii. În plus, nu se
consideră o practică p rea inspirată să folosești aceeași cheie pentru criptarea mesajelor de -a
lungul unei mari perioade de timp, din cauza sporirii șanselor de a fi atacată. Perechea de chei
publică și privată este uneori numită „cheia cheii de criptare”, pentru a o deosebi de cheia
mesajului (cheia datelor criptate).
Ca și Diffie -Hellman, sistemul RSA calculează exponențierile în aritmetica modulară
folosind numere cu lungimea de câteva sute de cifre. În RSA, totuși, fiecare persoană are un
modulo N personal, care este produsu l a două numere prime secrete. Cheia K a mesajului este
criptată prin ridicarea ei la puterea exponentului public a lui Bob ( eb), modulo Nb, iar
decriptarea se efectuează prin ridicarea ei la puterea exponentului privat al lui Bob ( db),
modulo Nb. presupun ând că C va prelua valoarea cheii textului criptat, aceasta se va exprima
matematic astfel:
C = Keb mod Nb (criptarea lui K)
K = Cdb mod Nb (decriptarea)
Pentru ca exponentul folosit la decriptare ( db) să poată reface exponențierea cu eb la
criptare, formu la eb * db = 1 mod (pb -1)(qb -1) trebuie să fie realizată; în care Nb = pb * qb
pentru numerele prime pb și qb.
În aceste condiții, oricine știe eb, pb și qb poate să folosească formula pentru a deduce db.
Din acest motiv, pb și qb nu se divulgă, chiar dacă eb și Nb sunt făcut publice. Calcularea
factorilor primi ai lui Nb se consideră a fi, din punct de vedere matematic, nerezolvabilă
pentru numere foarte mari.
Vom folosi valori mici ale numerelor din exemplul următor pentru a ușura înțelegerea
mecanismului . Să presupunem că Bob a ales numerele prime secrete pb = 5 și qb = 3, de unde
rezultă că Nb = pb * qb = 5 * 3 = 15. Apoi alege exponentul secret db = 29 și îl calculează pe
eb după formula eb * db = 1 mod (pb -1)(qb -1), ceea ce va conduce la eb * 29 = 1 mo d (4 * 2),
29 * eb = 1 mod 8 . Prin încercări succesive rezultă eb = 5.
Dacă Alice dorește să transmită cheia K = 2 către Bob, ea o va cripta cu exponențierea
din cheia publică a lui Bob, efectuând calculele:
C = Keb mod Nb = 25 mod 15 = 32 mod 15 = 2
Când Bob obține cheia criptată o va decripta folosindu -și cheia secretă drept exponent,
45 prin calculul:
K = Cdb mod Nb = 229 mod 15 = 2 (Se aplică mod (2 ** 29, 15)).
Se observă că s -a obținut valoarea K = 2 a cheii transmisă de Alice.
4.3 Semnătura digitală
Inventarea criptografiei prin chei publice a adus două importante mutații valoroase.
Prima, discutată anterior, permite transmiterea unui secret către o altă persoană fără să fie
nevoie de o a treia persoană de încredere sau de un canal de comunicație off -line pentru a
transmite cheia secretă. A doua mutație s -a produs pe planul calculării semnăturii digitale.
O semnătură digitală este un bloc de date (alcătuit din cifre binare, ceea ce în engleză
înseamnă binary digit , de unde și digitală – exprimată printr -un șir de cifre) ce se atașează
unui mesaj sau document pentru a întări încrederea unei alte persoane sau entități, legându -le
de un anumit emițător. Legătura este astfel realizată încât semnătura digitală poate fi
verificată de receptor sau de o terță pers oană și nu se poate spune că a fost uitată. Dacă doar o
cifră binară nu corespunde, semnătura va fi respinsă în procesul de validare. Semnătura
digitală stabilește autenticitatea sursei mesajului. Dacă o persoană nu -și dă în vileag cheia
personală privată nimeni nu poate să -i „imite” semnătura. O semnătură digitală nu înseamnă
și recunoașterea dreptului de proprietate asupra textului transmis, ci ea atestă faptul că
persoana semnatară a avut acces la el și l -a semnat. Documentul poate fi și sustras de undev a.
Totuși, atunci când semnarea este cuplată cu crearea documentului, semnătura poate oferi o
probă evidentă a originii documentului. În această categorie intră fotografiile luate cu camere
digitale bazate pe chei private. În acest caz, proba este de necon testat. Așa se procedează când
se intenționează realizarea protecției împotriva manipulării imaginilor cu ajutorul
calculatorului. La fel pot fi camerele video, radio -receptoarele și alți senzori care pot semna
ieșirea pentru a -i certifica originea.
Deși s emnătura digitală este implementată prin sistemul criptografiei cu chei publice,
transformările ce au loc sunt diferite de cele de la criptare. În timp ce la criptare fiecare parte
are o pereche de chei publică -privată, în cazul semnăturii digitale, compon enta privată este
întrebuințată pentru semnarea mesajelor, iar cea publică este folosită de o altă parte pentru a
verifica semnătura. Modul de funcționare este redat în figura 4.2.
După prezentarea suplimentară a algoritmilor semnăturii digitale să parcurg em pașii
„dialogului” purtat de Alice cu Bob. Alice intenționează să semneze un mesaj. Ea va începe
prin calcularea unei valori rezumat a mesajului, care este determinată printr -o funcție publică
de dispersie ( hashing ). În acest moment nu se folosesc chei. În pasul următor, ea va utiliza o
cheie privată pentru semnătură KS Alicepriv , pentru a calcula o transformare criptografică a
46 valorii rezumat a mesajului. Rezultatul, care este semnătura sa pe mesaj, se atașează
mesajului. Din acest moment, mesajul semnat poate fi transmis altei persoane, inclusiv Bob,
sau poate fi stocat într -un fișier.
Să presupunem că Bob va recepționa mesajul ei. El poate să valideze semnătura lui Alice
făcând apel la cheia ei publică pentru semnătură, KS Alicepub , ce va fi folosită ca intrare într -o
funcție criptografică prin care se va testa dacă valoarea rezumat determinată de el este aceeași
cu valoarea codificată prin semnătura lui Alice. Dacă da, va accepta semnătura. Se observă că
nici o cheie de -a lui Bob nu este folosită în proc esul de validare a semnăturii transmise de
Alice, ci doar cheile ei. În schimb, când Alice transmite cheia unui mesaj secret către Bob, ea
va folosi doar cheile lui Bob.
Dacă Alice dorește să transmită un mesaj către Bob, mesaj care să fie semnat și cripta t,
procesul presupune utilizarea cheilor pentru semnătură ale lui Alice (KS Alicepriv , KS Alicepub ),
cheilor lui Bob de criptare a cheii (K Bobpub ) și o cheie a mesajului, K. În sinteză, iată pașii:
• Alice generează o cheie aleatoare a mesajului, K. Alice crip tează mesajul M cu cheia
K, obținând mesajul criptat, MC;
• Alice criptează cheia K folosind cheia publică a lui Bob de criptare a cheii, K Bobpub ,
rezultând cheia criptată, KC;
• Alice procesează o semnătură S folosind cheia sa privată pentru semnătură,
KS Alicepriv ;
• Alice transmite către Bob KC, MC și S;
• Bob folosește cheia sa privată de criptare a cheii, K Bobpriv , pentru a decripta KC și a
obține K;
• Bob folosește K pentru decriptarea MC și obținerea textului -clar, M;
• Bob folosește cheia publică pentru s emnătură a lui Alice, KS Alicepub , pentru validarea
semnăturii S.
Tot acest proces este folosit de sistemul de criptare e -mail-uri, așa că Alice și Bob nu vor
efectua operațiunile enunțate, ci le face calculatorul. Pentru a dispune de aceste servicii este
necesară contactarea unor firme specializate. Microsoft recomandă Verisign, cu site -ul
www.verisign.com , deși sunt mai multe oferte. Oricum e necesară obținerea unui ID digital.
La click -ul pe Sign apare semnul sigiliul ui special pentru semnătură, iar la comanda Send , vi
se oferă un meniu prin care puteți începe dialogul pentru obținerea ID -ului digital pentru
semnătură, prin click pe butonul Get Digital ID .
Pentru a studia cadrul legal al utilizării semnăturii electroni ce în România, puteți obține
informațiile dorite de pe site -ul www.legi.internet.ro/lgsemel.htm .
47 4.4 Sisteme de certificare a cheilor publice
Un sistem criptografic bazat pe chei publice poate fi compro mis de o persoană (A) care
transmite o cheie publică altei persoane (B) către un alt partener (C). În acest caz (C) va folosi
cheia publică a lui (B) pentru a cripta mesajul, cu intenția de a ajunge înapoi la (B), numai că
(A), folosindu -și propria cheie p rivată, va face ca receptorul să fie el, reușind astfel să
decripteze mesajul care era adresat lui (B).
Pentru a se evita o astfel de ciudățenie, se recurge la procesul certificării, prin care
persoanele sunt legate de cheile lor publice. Documentul oferit de o Autoritate de Certificare
acționează ca orice alt act emis de un notar și se efec tuează după aceleași reguli, adică pe baza
verificării identității persoanei solicitante, concretizându -se prin atribuirea unei chei publice
pentru persoana respectivă. Unitatea de certificare semnează certificatul cu propria cheie
privată. Din această cauză, persoana este verificată ca emițător dacă este necesară cheia ei
publică pentru deschiderea sesiunii de transmitere a mesajelor criptate și/sau semnăturilor
electron ice. Certificatul conține numele subiectului, cheia lui publică, numele autorității de
certificare, perioada de valabilitate a certificatului. Pentru a verifica semnătura autorității de
certificare, cheia ei publică trebuie să fie verificată încrucișat cu o altă autoritate de
certificare. În SUA formatul certificatelor este reglementat prin standardul X.509.
Certificatele sunt păstrate într -un Registru (Repository), alături de lista certificatelor revocate.
În principiu, operațiunile pentru obținerea certif icatelor digitale și validarea tranzacțiilor sunt
redate în figura 4.3.
Fig. 4.3 Prezentarea unei tranzacții cu certificate digitale
4.5 Infrastructura cheilor publice (PKI)
Infrastructura cheilor publice ( PKI – Public Key Infrastructure ) își propune să rezolve
probleme manageriale din domeniul cheilor publice, integrând semnături și certificate digitale
cu o mare diversitate de alte servicii specifice comerțului electronic, prin care se solicită
48 oferirea integrității, controlului accesului, confidențiali tății, autentificării și a nerepudierii
tranzacțiilor electronice.
Infrastructura cheilor publice cuprinde certificatele digitale, autoritățile de certificare,
autoritățile de înregistrare, politici și proceduri cu chei publice, revocarea certificatelor,
nerepudierea, marcarea timpului, certificarea încrucișată, aplicații de securitate, LDAP
(Lightweight Directory Acces Protocol ).
LDAP oferă un format standard de accesare a directoarelor certificatelor. Aceste
directoare sunt stocate pe serverele LDAP dintr -o rețea, serverele de pe aceste rețele oferind
chei publice și certificate X.509 pentru companii.
În SUA, majoritatea certificatelor sunt emise de Verisign, Inc., recomandată și de
Microsoft. Compania oferă trei clase de certificate personale , numite digital IDs , toate legate
de e-mail:
• clasa 1 de certificate verifică adresa e -mail a utilizatorului, fără să solicite alte
elemente de autentificare. După exprimarea interesului pentru un certificat, sistemul
trimite o confirmare cu un PIN pe adresa de e -mail a persoanei. Utilizatorul se
întoarce la site -ul anterior (al companiei) și oferă PIN-ul, după care este generat un ID
digital și se memorează în calculatorul utilizatorului.
• clasa 2 de certificate cere utilizatorului să mai introducă și Social Security Number
(codul oferit de Internal Revenue Service ), adresa și seria carnetului de șofer;
• clasa 3 de certificate digitale este destinată companiilor ce publică software,
oferindu -le un grad mult mai mare de securitate, dar există și o variantă pentru
persoane fizice ocupate cu transferuri bancare, contracte ș.a. Este o clasă mult mai
sigură.
Oricum, realizarea unei infrastructuri a cheilor publice la nivel internațional, dar și
național, este o mare problemă, nu din punct de vedere tehnic sau managerial, ci al legislației.
4.6 Algoritmi
4.6.1 Algoritmul DES
Algoritmul DES (Data Encryption Standard) a fost dezvoltat pentru guvernul Statelor
Unite și pentru folosință publică. El a fost dezvoltat plecând de la algoritmul “Lucifer”
conceput în Laboratoarele IBM. În mai 1973, revista Federal Register a sintetizat principiile
care trebuie să stea la baza proiectării unui algoritm criptografic standard:
– algoritmul trebuie să asigure un înalt nivel de securitate;
– algoritmul trebuie să fie complet specificat și simplu de înțeles;
49 – securitatea algoritmului trebuie să fie asigurată de cheie și nu trebuie să depindă
de păstrarea secretă a algoritmului;
– algoritmul trebuie să fie disponibil tuturor utilizatorilor;
– algoritmul trebuie să fie adaptabil pentru diverse aplicații;
– algoritmul trebuie să fie implementabil pe dispozitivele electronice;
– algoritmul trebuie să fie eficient în utilizare;
– algoritmul trebuie să poată fi validat;
– algoritmul trebuie să fie exportabil.
DES a fost oficial adoptat ca standard federal în 23 noiembri e 1976, iar în 1977
specificațiile sale au fost făcute publice.
Privire generală asupra algoritmului
Algoritmul DES este o combinație complexă folosind două blocuri fundamentale în
criptografie: substituția și permutarea (transpoziția). Acest cifru bloc ac ceptă un bloc de 64 de
biți la intrare și generează un bloc cifrat de 64 de biți. DES este un algoritm simetric. Același
algoritm și aceeași cheie sunt folosiți atât la criptare cât și la decriptare.
Algoritmul este constituit din 16 cicluri repetate ale blocurilor fundamentale. Textul
inițial este descompus în blocuri de 64 de biți. Cheia este de 64 biți din care doar 56 sunt
efectivi, ceilalți fiind biți de paritate. Folosirea substituției provoacă confuzie prin sistematica
substituire a unor biți cu alț ii. Transpozițiile provoacă difuzie prin re -ordonarea biților.
Algoritmul folosește numai operații clasice aritmetice și logice cu număr de până la 64
de biți, ceea ce face relativ ușor de implementat atât software cât mai ales hardware: unul din
scopurile declarate ale algoritmului fiind ușoara lui implementare hardware într -un cip
specializat.
Parcurgerea celor 16 cicluri are loc după schema din figura 4.6.1.
La intrarea datele sunt împărțite în blocuri de 64 biți, care sunt transformate folosind
cheia de 64 de biți. Cei 64 de biți sunt permutați prin “permutarea inițială”. În continuare,
urmează operațiile ce constituie un ciclu. Blocul de 64 de biți este separat în două, “jumătatea
stângă” și “jumătatea dreaptă”, fiecare de 32 de biți. Cheia este deplasa tă la stânga cu un
număr de biți și permutată: ea se combină cu “partea dreaptă” care apoi se combină cu “partea
stângă”; rezultatul devine noua “parte dreaptă”; vechea “parte dreaptă” devine noua “parte
stângă” (vezi fig. 4.6.2). După repetarea acestui ci clu de 16 ori se face permutarea finală care
este inversă permutării inițiale.
Pentru combinarea unei secvențe de 32 biți cu cheia de 64 biți se folosesc expandări de
la 32 biți la 48 biți și reducerea cheii de la 64 biți la 48 biți prin alegerea anumitor biți,
operații ce le numim “permutare expandată” și “permutare aleasă” (fig. 4.6.3).
50 În fiecare ciclu practic au loc patru operații separate. Întâi partea dreaptă este expandată
de la 32 la 48 biți; apoi este combinată cu o formă a cheii; rezultatul este substituit și
condensat în 32 biți, cei 32 biți sunt permutați și apoi combinați cu partea stângă pentru a da o
nouă parte dreaptă (fig. 4.6.4).
Fig. 4.6.1 Detalii pentru folosirea algoritmului DES Intrare
permutare inițială
Substituție
Permutare Cheia
Ciclul 1
Cheia Substituție
Permutare
Substituție
Permutare Cheia
Imaginea inversată a perm utării inițiale
Ieșire
Ciclul 16
51
Fig. 4.6.2 Manipular ea cheii în algoritmul DES
Fig. 4.6.3 Manipularea permutării în algoritmul DES
Cheia este împărțită cu două părți de 28 biți deplasate la stânga cu un număr de biți apoi
reunite și 48 din cei 56 de biți sunt permutați și folo siți ca o cheie de 48 de biți de -a lungul
ciclului.
Cheia dintr -un ciclu este combinată printr -o funcție sau exclusiv cu “partea dreaptă”
expandată. Rezultatul este operat în 8 “cutii -S” care efectuează substituția. O “cutie -S” este o
tabelă în care 6 biți de date sunt înlocuiți de 4 biți.
Permutările sunt efectuate de tabele numite “cutii -P”. Date permutate
Jumătatea stângă
S Jumătatea
dreaptă Cheie
deplasată
Cheie
permutată
Noua jumătatea
stângă (vechea
jumătate dreaptă) Noua jumătatea
dreaptă
Permutare Permutare aleasă Permutare expandată
52
D
32 biți
S
32 biți
Permutare
expandată
Cheia
28 biți
28 biți
Deplasare Deplasare
permutare aleasa d e
58 biți
48 biți
4.6.4 Ciclul în algoritmul DES
Permutarea expandată este definită în tabelul ce urmează:
Bit 1 2 3 4 5 6 7 8
se mută la 2,48 3 4 5,7 6,8 9 10 11,13
Bit 9 10 11 12 13 14 15 16
se mută la 12,14 15 16 17,19 18,20 21 22 23,25
Bit 17 18 19 20 21 22 23 24
se mută la 24,26 27 28 29,31 30,32 33 34 35,37
Bit 25 26 27 28 29 30 31 32
se mută la 36,38 39 40 41,43 42,44 45 46 47,1
Tabelul 4.6.1 Definirea permutării expandate în DES
Considerații asupra algoritmului DES
Cu algoritmul DES se poate face atât codificarea cât și decodificarea unui mesaj.
Rezultatul este adevărat pentru că ciclul j derivă din ciclul ( j-1) astfel:
S Dj j1
(1)
), ()(1 1 j j j j k Df S D
(2)
53 unde (+) este operația sau exclusiv, f este funcția rezultată din operațiile dintr -un ciclu.
Aceste ecuații arată că rezultatul fiecărui ciclu depinde numai de ciclul precedent.
Descriind ecuațiile pentru D j-1 și S j-1 avem :
D Sj j1 (3)
și
), ()(1 1 j j j j k Df D S (4)
înlocuind (3) în (4) avem:
),()(1 j j j j kSf D S (5)
Ecuațiile (3) și (5) arată că aceleași valori pot fi obținute în cicluri ulterioare. Această
proprietate face al goritmul DES reversibil.
Deci putem face codificarea unor date și decodificarea lor folosind același algoritm
făcând observația că la decodificare cheia se ia în ordine inversă.
Datorită lungimii cheii de lucru și a operațiilor elementare pe care le folose ște
algoritmul, nu se ridică probleme deosebite într -o implementare software; singura observație
este că, datorită modulului de lucru (cu secvențe de date, cu tabele) practic algoritmul este lent
într-o implementare software. Modul de concepere îl face îns ă perfect implementabil hard
(într-un cip) ceea ce s -a și realizat, existând multiple variante de mașini hard de codificare.
Criptanaliza
Deși DES a fost cel mai celebru algoritm al secolului XX este considerat la această oră
nesigur pentru multe aplicați i. Pare paradoxal, dar aceasta este consecința măririi
considerabile a puterii de calcul de la confirmarea DES – ului ca un standard criptografic și
până in anul 2000. Slăbiciunea pleacă de la lungimea prea mică a cheii de 56 de biți. Varianta
algoritmului cunoscută ca triplu -DES este cea care este considerată sigură și la această oră.
Insecuritatea DES -ului pleacă de la premiza că un atac “în forță” are șanse de reușită
în condițiile puterii de calcul disponibile astăzi ( a se vedea atacurile EFF1 ); până în 2004 cel
mai eficient atac este datorat criptanalizei liniare care folosind 243 texte cunoscute generează o
complexitate temporală de 239-43 (Junod 2001); în condițiile unui atac cu text ales
complexitatea poate fi redusă de patru ori (Knudsen și Mathi assen, 2000).
1 Electronic Frontier Foundation
54 O istorie cronologică a DES – ului este prezentată în următorul tabel:
Data Anul Evenimentul
15 mai 1973 NBS publică prima cerere pentru un algoritm standard pentru criptare
27 august 1974 NBS publică a doua cerere pentru un algoritm standard pentru criptare
17 martie 1975 DES este publica t în Federal Register2 pentru comentarii
august 1976 Se organizează primul workshop despre DES
septembrie 1976 Al doilea workshop despre fundamentele matematice ale DES -ului
noiembrie 1976 DES este aprobat ca un standard
15 ianuarie 1977 DES este publicat în FIPS PUB 46
1983 DES este reconfirmat pentru prima dată
22 ianuarie 1988 DES este reconfirmat pentr u a doua oară ca FIPS 46 -1
1992 Biham și Shamir publică primul atac teoretic cu o complexitate mai
mică decât atacul
”în forță brută” : criptanaliza diferențială ; metoda cerea un număr
nerealist (247) de texte alese
30 decembrie 1993 DES este reconf irmat pentru a treia oară ca FIPS 46 -2
1994 Prima criptanaliză experimentală folosind criptanaliza liniară (Matsui,
1994)
iunie 1997 Proiectul DESCHALL sparge pentru prima dată în public un mesaj
criptat cu DES
iulie 1998 EFF găsește o cheie pentru DES în 56 de ore
ianuarie 1999 EFF folosind putere de calcul distribuită găsește o cheie pentru DES în
22 de ore și 15 minute
25 octombrie 1999 DES este reconfirmat pentru a patra oară ca FIPS 46 -3 cu specificația
preferinței pentru Triplu DES
26 noiembrie 2001 AES este publicat în FIPS 197
26 mai 2002 Standardul AES devine efectiv
26 iulie 2004 Retragerea standardului F IPS 46 -3 (și a celor conexe) este propusă în
Federal Register
Tabelul 4.6.2 Cronologia evenimentelor algoritmului DES
2 Publicație a NIST (National Institute of Standards and Technology)
55 4.6.2 Variante de DES
DES multiplu
Unele implementări de DES folosesc triplul -DES. Deoarece DES nu este un grup, textul
cifrat re zultat este mult mai greu de spart folosind căutarea exhaustivă: 2112 încercări în loc de
256 încercări.
DES cu sub -chei independente
O altă variantă constă în folosirea unei sub -chei diferite pentru fiecare trecere, în loc de
a o genera dintr -o singură ch eie de 56 de biți. Deoarece în fiecare din cele 16 treceri se
folosește o cheie de 48 de biți, rezultă că lungimea cheii pentru această variantă este de 768
biți, ceea ce va crește semnificativ dificultatea unui atac în forță împotriva algoritmului, acesta
având complexitatea de 2768.
Totuși, un atac de tip “întâlnire la mijloc” este posibil, ceea ce reduce complexitatea
atacului la 2384; încă destul de lung pentru orice nevoie imaginabilă de securitate.
Această variantă poate fi analizată folosind criptana liza diferențială și poate fi spartă cu
261 texte în clar date. Se pare că nici o modificare în planificarea cheilor nu conduce la
întărirea semnificativă a algoritmului DES.
DESX
DESX este o variantă DES dezvoltată de RSA Data Security, care a fost inclus ă încă din
1968 în programul de securitate pentru poștă electronică MailSafe. DESX folosește o tehnică
numită albire, pentru a ascunde intrările și ieșirile DES. În plus față de cheia DES de 56 de
biți, DESX are o cheie suplimentară de albire de 64 de biți . Acești 64 de biți sunt operați XOR
cu textul în clar înainte de prima trecere DES. 64 de biți suplimentari, calculați ca o funcție
bijectivă de toți cei 120 de biți ai cheii DES, sunt operați XOR cu textul cifrat înaintea ultimei
treceri. Albirea îl face pe DESX mult mai puternic decât DES față de un atac în forță; atacul
necesită (2120)/n operații cu n texte în clar cunoscute. De asemenea se îmbunătățește
securitatea împotriva criptanalizei liniare și diferențiale; atacul necesită 261 texte în clar date și
260 de texte în clar cunoscute.
CRYPT(3)
CRYPT(3) este o variantă de DES întâlnită în sistemele UNIX. Este folosită în mod
obișnuit pentru parole, dar uneori și pentru criptare. Diferența între CRYPT(3) și DES este că
CRYPT(3) are o permutare de chei cu 212 posibilități, astfel încât să nu permită folosirea
cipurilor DES la construcția unui dispozitiv hardware de spart parole.
56 DES generalizat
DES -ul generalizat (GDES) a fost proiectat să mărească viteza DES -ului și să întărească
algoritmul. Mărimea tot ală a blocului crește, în timp ce suma calculelor rămâne constantă.
GDES operează pe blocuri de text în clar de lungime variabilă. Blocurile criptate sunt
împărțite în q sub-blocuri; numărul exact depinde de mărimea totală a blocului. În general q
este ega l cu lungimea blocului împărțită la 32.
Funcția f este calculată o dată la fiecare trecere, pe ultimul bloc din dreapta. Rezultatul
este operat XOR cu toate celelalte părți, care sunt apoi rotite spre dreapta. GDES are un
număr variabil de treceri, n. Exis ta o mică modificare la ultima trecere, astfel încât procesele
de criptare și decriptare diferă doar prin ordinea sub -cheilor. De fapt, pentru q=2 și n=16 se
obține algoritmul DES.
Biham și Shamir arată că, folosind criptanaliza diferențială, GDES cu q=8 și n=16 este
vulnerabil cu doar șase texte în clar date. Dacă se folosesc și sub -chei independente, sunt
necesare 16 texte în clar date. Pentru q=8 și n=64, GDES e mai slab decât DES; sunt necesare
249 texte în clar date pentru a -l sparge. De fapt, orice sc hemă GDES este mai rapidă decât
DES, dar este de asemenea mai puțin sigură.
RDES
RDES este o variantă care înlocuiește schimbarea stânga -dreapta de la sfârșitul fiecărei
treceri cu o schimbare dependentă de cheie. Schimbările sunt fixe, depinzând doar de c heie.
Aceasta înseamnă că cele 15 schimbări dependente de cheie se petrec cu 215 posibilități și că
această variantă nu rezistă la criptanaliza diferențială.
O idee mai bună este ca schimbarea să aibă loc doar în partea dreaptă, la începutul
fiecărei trece ri, iar schimbarea să depindă de datele de intrare și nu de cheie. În RDES -1 se
practică o schimbare dependentă de date de cuvinte pe 16 biți la începutul fiecărei treceri. În
RDES -2 există o schimbare de octeți dependentă de date la începutul fiecărei tre ceri, după o
schimbare ca în RDES -1. Se poate continua în același mod până la RDES -4. RDES -1 este
sigură atât față de criptanaliza liniară cât și față de cea diferențială.
4.6.3 Algoritmul AES
În ianuarie 1997, NIST3 a organizat un concurs de criptografi e deschis cercetătorilor din
întreaga lume, având ca subiect crearea unui nou standard, care urma să se numească AES4.
Regulile concursului erau:
3 National Institute of Standards and Technology SUA
4 Advanced Encryption Standa rd – Standard de Criptare Avansat
57 – algoritmul să fie un cifru bloc simetric;
– proiectul trebuia să fie public;
– AES trebuia să suporte chei de 128, 192 și 256 biți;
– algoritmul trebuia să se poată implementa atât hardware cât și software;
– AES trebuia să fie un standard public sau oferit cu licență ne discriminatorie.
În august 1998 NIST a selectat cinci finaliști pe criterii de securitate, eficiență ,
flexibilitate și cerințe de memorie. Finaliștii au fost:
1. Rijndael (Joan Daemen și Vincent Rijmen, 86 de voturi)
2. Serpent (Ross Anderson, Eli Biham, Lars Knudsen, 56 voturi)
3. Twofish (echipa condusă de Bruce Schneier, 31 voturi)
4. RC6 (RSA Laboratories, 23 vo turi)
5. MARS (IBM, 13 voturi)
În octombrie 2000 NIST a stabilit câștigătorul. Acesta este algoritmul Rijndael,
dezvoltat de doi tineri cercetători belgieni, Joan Daemen și Vincent Rijmen și care devine
standard guvernamental al SUA. Se speră ca Rjindael să devină standardul criptografic
dominant în lume pentru următorii 10 ani.
Rijndael permite lungimi de chei și mărimi de blocuri de la 128 de biți la 256 de biți, în
pași de câte 32 de biți. Lungimea cheii și lungimea blocului pot fi alese în mod independen t,
dar în practică se vor folosi două variante: bloc de 128 biți cu cheie de 128 biți și bloc de 128
biți cu cheie de 256 biți. Standardul comercial va deveni cel mai probabil varianta 128/128. O
cheie de 128 biți permite un spațiu al cheilor de 2128 chei.
Preliminarii matematice
Rijndael se bazează pe teoria câmpului Galois, în sensul că anumite operațiuni sunt
definite la nivel de octet iar octeții reprezintă elemente în câmpul finit GF(28).
Cum toate reprezentările câmpului finit GF(28) sunt izomorfe, s e poate alege
reprezentarea clasică polinomială, cu impact pozitiv asupra complexității implementării.
Octetul b, format din biții b7, b6, b5, b4, b3, b2, b1 și b0, este considerat ca fiind un
polinom de gradul 7 cu coeficienți 0 sau 1:
b7 x7 + b 6 x6 + b5 x5 + b 4 x4 + b 3 x3 + b 2 x2 + b 1 x + b0
Operațiunea de adunare este definită ca suma a două polinoame în care coeficienții se
adună modulo 2 și care corespunde operării XOR a celor doi octeți corespondenți. Sunt
58 îndeplinite axiomele grupului abelian : operația este internă, asociativă, comutativă, există
element neutru și element invers
Operațiunea de înmulțire corespunde produsului a două polinoame modulo, un polinom
ireductibil de grad 8 și care pentru AES este
m(x) = x8 + x4 + x3 + x + 1
Înmulțir ea este internă (rezultatul este un polinom de grad strict mai mic ca 8),
asociativă și există element neutru. Elementul invers se determină cu algoritmul lui Euclid, iar
distributivitatea celor doua operații se verifică.
Concluzia este că mulțimea celor 2 56 de valori posibile ale unui octet, împreună cu cele
două operațiuni definite mai sus formează un corp algebric finit, respectiv GF(28).
Proiectarea AES
În proiectarea AES s -a ținut cont de trei criterii:
– rezistența împotriva tuturor atacurilor cunoscut e;
– viteza și compactitatea codului pe un mare număr de platforme;
– simplicitatea proiectării.
Ca și DES, AES folosește substituție și permutări, ca și runde multiple. Numărul de
runde depinde de mărimea cheii și de mărimea blocului, fiind 10 în cazul 128/1 28 și mărindu –
se până la 14 pentru cazul 256/128. Spre deosebire de DES, toate operațiile sunt la nivel de
octet, pentru a permite implementări eficient hardware și software.
Descrierea AES
În algoritmul AES rezultatul cifrat intermediar este numit vector state , care poate fi
reprezentat ca un tabel cu patru linii și patru coloane, acestea fiind numerotate începând de la
0.
Vectorul state se inițializează cu blocul de 128 biți de text în clar (în ordinea coloanelor,
cu primii patru octeți în coloana 0) și va fi modificat la fiecare pas al calculului, prin
substituții, permutări și alte transformări, rezultând în final blocul de 128 biți de text cifrat.
Cheia de 128 de biți este expandată în 11 tabele 4×4 notate rk(0), rk(1),…., rk(10).
Expandarea este rea lizată prin rotiri repetate și operații XOR asupra unor grupuri de biți din
cheia originală.
Înainte de a începe cele 10 runde, cheia rk(0) se operează XOR cu vectorul state.
59 Calculul principal constă în execuția a 10 runde, folosind cheia rk(i) la iterați a i. Fiecare
rundă constă în patru pași.
Pasul 1 realizează o substituție octet cu octet asupra vectorului state folosind o cutie S.
Pasul 2 rotește la stânga fiecare din cele 4 rânduri ale vectorului state : rândul 0 este rotit
cu 0 octeți, rândul 1 este rotit cu 1 octet, rândul 2 este rotit cu 2 octeți și rândul 3 este rotit cu
3 octeți, realizând difuzia datelor.
Pasul 3 amestecă fiecare coloană din vectorul state independent de celelalte, prin
înmulțirea coloanei cu o matrice constantă, multiplicarea fi ind realizată folosind câmpul finit
Galois GF(28).
În fine, pasul 4 operează XOR cheia rk din runda respectivă cu vectorul state .
Deoarece fiecare pas este reversibil, decriptarea se poate realiza prin rularea
algoritmului de la coadă la cap, sau prin rula rea algoritmului de criptare nemodificat, dar
folosind tabele diferite.
Avantaje AES
Avantajele AES relativ la implementare sunt:
– AES se poate implementa pe un procesor Pentium Pro și va rula cu o viteză
mai mare decât orice alt cifru bloc;
– AES se poate i mplementa pe un dispozitiv Smart Card, folosind un spațiu
redus de memorie RAM și un număr redus de cicluri;
– transformarea din cadrul unei runde este paralelă prin proiectare, ceea ce
constituie un avantaj pentru viitoarele procesoare;
– AES nu folosește ope rațiuni aritmetice, ci doar operații la nivel de șiruri de
biți.
Simplitatea proiectării AES :
– AES nu folosește componente criptografice externe, cum ar fi cutii S, biți
aleatori sau șiruri de cifre din dezvoltarea numărului ;
– AES nu își bazează securitat ea pe interacțiuni obscure sau greu de înțeles între
operațiuni aritmetice;
– proiectarea clară a AES nu permite ascunderea unei “trape”.
Lungimea variabilă a blocului
– lungimile de bloc de 192 și 256 biți permit construirea unei funcții hash
iterative folos ind AES ca funcție de compresie.
60
Extensii:
– proiectarea permite specificarea de variante cu lungimi de blocuri și lungimi
de chei aflate între 128 și 256 biți, în pași de câte 32 de biți;
– deși numărul de runde în AES este fixat în specificațiile algoritmul ui, el poate
modificat ca un parametru în cazul unor probleme de securitate.
Limitările AES
Limitările AES sunt în legătură cu algoritmul de decriptare:
– algoritmul de decriptare este mai puțin pretabil la implementarea pe un
dispozitiv Smart Card, deoarec e necesită mai mult cod și mai multe cicluri;
– implementarea software a AES folosește cod și/sau tabele diferite pentru
algoritmul de criptare, respectiv decriptare;
– implementarea hardware a AES a algoritmului de decriptare refolosește doar
parțial circuite le care implementează algoritmul de criptare.
4.6.4 Algoritmul LUCIFER
În 1960, IBM inițiază un program de cercetare în criptografia computerizată numit
Lucifer. Astfel se numește și algoritmul cifru bloc dezvoltat în cadrul acestui program în
1970. În r ealitate există cel puțin doi algoritmi cu acest nume.
Lucifer este o rețea de permutări și substituții, cu blocuri construite într -o manieră
asemănătoare cu DES. În DES, ieșirea funcției f este operată XOR cu intrarea fazei anterioare
pentru a forma intra rea fazei curente. În cazul lui Lucifer, “cutiile -S” au intrări și ieșiri de 4
biți; intrarea este o permutare a biților ieșirii din faza anterioară, iar intrarea din prima fază
este chiar textul în clar. Un bit cheie este folosit pentru a alege între “cut ia-S” actuală din
două posibile – Lucifer implementează aceasta printr -o “cutie -T” cu 9 biți la intrare și 8 la
ieșire). Lucifer are 16 faze, blocuri de 128 de biți și o manipulare a cheii mai simplă decât
DES -ul.
Folosind criptografia diferențială împotri va primei forme de Lucifer, Biham și Shamir
au arătat că Lucifer cu 8 faze și 32 de biți poate fi spart cu 40 de texte în clar alese și 229 pași;
același atac poate sparge Lucifer cu 8 faze și 128 biți cu 60 de texte în clar alese și 253 pași.
Aceste atacu ri folosesc “cutii -S” DES tari. Folosind criptografia diferențială împotriva celei
de a doua forme de Lucifer, s -a arătat că “cutiile -S” sunt mai slabe decât în DES. Analize
ulterioare au arătat că peste jumătate din chei nu sunt sigure, ceea ce conduce la posibilitatea
61 de a sparge Lucifer cu 128 de biți, cu orice număr de faze, cu 233 texte în clar alese, sau cu 265
texte în clar cunoscute cu chei alese. În concluzie, a doua formă de Lucifer este mai slabă.
Sentimentul că Lucifer este mai sigur decât DES d atorită lungimii mai mari a cheii și lipsei de
rezultate publicate este nejustificat.
4.6.5 Algoritmul Blowfish
Blowfish este un algoritm proiectat pentru a fi implementat pe procesoare puternice,
care încearcă să respecte următoarele criterii:
1. Rapidita te – Blowfish criptează date pe procesoare de 32 de biți la o rată de 26
de tacturi pe octet.
2. Compact – Blowfish poate rula în mai puțin de 5K de memorie.
3. Simplitate – Blowfish folosește doar operații simple: adunare, operare XOR și
căutare în tabelă, cu o peranzi de 32 de biți. Algoritmul este ușor de analizat,
ceea ce evită erorile de implementare.
4. Securitate variabilă – lungimea cheii este variabilă, putând crește până la 448
de biți.
Blowfish este optimizat pentru aplicații în care cheia nu trebuie să s e schimbe des, cum
ar fi legături de comunicație sau un criptor automat pentru fișiere. Este semnificativ mai rapid
decât DES când este implementat pe procesoare de 32 de biți dotate cu memorie cache mare,
cum ar fi Pentium. Blowfish nu este potrivit pentr u comutarea de pachete, cu schimbări dese
de cheie, ca funcție hash one -way sau în aplicații smart -card, unde memoria este insuficientă.
Descrierea algoritmului Blowfish
Blowfish este un cifru bloc care operează cu blocuri de 64 de biți si are cheie de
lungime variabilă. Algoritmul constă în două părți: expandarea cheii și criptarea datelor.
Expandarea cheii convertește o cheie de până la 448 de biți în mai multe matrice de sub -chei
totalizând 4168 de biți.
Criptarea datelor rezidă într -o funcție simplă it erată de 16 ori. Fiecare ciclu este format
dintr -o permutare dependentă de cheie și o substituție dependentă și de cheie și de date. Toate
operațiile sunt adunări și operări XOR pe cuvinte de 32 de biți. Singurele operații
suplimentare sunt patru căutări î ntr-un tabel indexat, pe ciclu.
Blowfish folosește un număr mare de sub -chei. Aceste sub -chei trebuie precalculate
62 înainte de orice criptare sau decriptare de date.
Tabelul P este format din 16 chei de 32 de biți:
P1, P2, …, P 18
Patru “cutii -S” de 3 2 de biți are 256 de intrări fiecare:
S1,0, S1,1, …. , S 1,255
S2,0, S2,1, …. , S 2,255
S3,0, S3,1, …. , S 3,255
S4,0, S4,1, …. , S 4,255
Blowfish este o rețea Feistel cu 16 cicluri. Intrarea este x, un element de 64 biți de date.
Pentru criptare:
Se împarte x în două părți de câte 32 de biți: xL și xR
For i = 1 to 16:
xL = xL Pi
xR = F(xL) xR
se schimbă xL și xR între ele
End for
se schimbă xL și xR între ele
xR = xR P17
xL = xL P18
se recombină xL și xR
Funcția F funcționează astfel:
Se împarte xL în patru sferturi a câte 8 biți:
a, b, c, d
F(xL) = (( S1,a + S2,b mod 232) S3,c) + S4,d mod 232
Decriptarea are loc similar cu criptarea, cu diferența că P1, P2, …, P 18 sunt folosite în
ordine inversă.
63 O implementare a algoritmului Blowfish care să asigure o creștere de viteză trebuie să
mențină toate cheile în memoria cache.
Sub-cheile sunt calculate folosind algoritmul Blowfish, care constă în următorii pași:
1. Se iniția lizează tabelul P și cele patru “cutii -S”, în ordine, cu un șir fix. Acest
șir este format din cifrele hexazecimale ale lui .
2. Se operează XOR P1 cu primii 32 de biți ai cheii, se operează P2 cu următorii
32 de biți ai cheii și tot așa până la P18, astfel încât întreg tabelul P să fie operat
XOR cu biții din cheie.
3. Se criptează un șir format din zerouri cu algoritmul Blowfish, folosind sub –
cheile descrise în pașii 1 și 2.
4. Se înlocuiesc P1 și P2 cu ieșirea din pasul 3.
5. Se criptează ieșirea din pasul 3 folosi nd algoritmul Blowfish cu sub -cheile
modificate.
6. Se înlocuiesc P3 și P4 cu ieșirea din pasul 5.
7. Se continuă procesul, înlocuind toate elementele din tabelul P și apoi cele patru
“cutii -S” în ordine, cu ieșirea algoritmului Blowfish.
În total, 521 de itera ții sunt necesare pentru a genera toate sub -cheile necesare.
Aplicațiile pot memora sub -cheile pentru a nu trebui să le calculeze de fiecare dată.
Securitatea algoritmului Blowfish
În cazul algoritmului Blowfish cu “cutii -S” cunoscute și r cicluri, tabelu l P poate fi
determinat cu 28r+1 texte în clar alese. Atacul funcționează doar pe variantele cu un număr
redus de cicluri și este complet ineficient în cazul algoritmului Blowfish cu 16 cicluri.
4.6.6 Dubla criptare
Un mod evident de îmbunătățire a secu rității algoritmilor bloc este criptarea unui bloc
de două ori, folosind două chei diferite. Mai întâi se criptează blocul cu prima cheie, apoi se
criptează textul cifrat rezultat folosind a doua cheie. Decriptarea este procesul invers:
C = EK2 (EK1 (P))
P = DK1 (DK2 (C))
Dacă algoritmul bloc este un grup, există întotdeauna un K3, astfel încât
64
C = EK2 (EK1 (P)) = EK3 (P)
În caz contrar, blocul de text cifrat rezultat dintr -o dublă criptare ar trebui să fie mult
mai greu de decriptat folosind c ăutarea exhaustivă. În loc de 2n încercări (unde n este
lungimea în biți a cheii), vor fi necesare 22n încercări. Dacă algoritmul are chei de 64 de biți,
vor fi necesare 2128 încercări pentru a găsi cheia.
În cazul atacului cu texte în clar cunoscute, Merk le și Hellman au demonstrat că schema
cu dublă criptare poate fi spartă în 2n+1 criptări și nu în 22n. Atacul se numește “întâlnire la
mijloc”; el funcționează prin criptarea de la un capăt, decriptarea la capătul celălalt și
potrivirea rezultatelor în mij locul textului criptat.
În acest atac, criptanalistul cunoaște P1, C1, P2 și C2, astfel încât
C1 = EK2 (EK1 (P1))
C2 = EK2 (EK1 (P2))
Pentru fiecare K posibil, se calculează EK(P1) și se memorează rezultatul. După
terminarea tuturor calculelor, se calculează DK(C1) pentru fiecare K și se caută un rezultat
identic în memorie. Dacă se găsește un astfel de rezultat, fie K2 cheia curentă și K1 cheia
folosită pentru rezultatul din memorie. Se criptează P2 cu K1 și K2; dacă se obține C2 este
aproape sigur (cu o probabilitate de 1 din 22m-2n, unde m este mărimea blocului), că cele două
chei sunt valide. Dacă nu, se continuă căutarea. Numărul maxim de căutări este 2 x 2n, adică
2n+1.
Acest atac necesită un spațiu mare de memorie: 2n blocuri. Pentru un algori tm de 56 de
biți, aceasta înseamnă 256 blocuri de 64 de biți, adică 1017 octeți. Este o cantitate considerabilă
de memorie, dar demonstrează că dubla criptare nu duce la dublarea securității. În cazul însă
al unei chei de 128 de biți, cantitatea de memorie necesară este de 1039 octeți, ceea ce
înseamnă că un atac de tip “întâlnire la mijloc” nu este fezabil.
O altă metodă de dublă criptare, numită Davies -Price, este o variantă de CBC:
Ci = EK1 (Pi EK2(Ci-1))
Pi = DK2 (Ci ) EK2(Ci-1))
care prezint ă aceeași vulnerabilitate față de un atac de tip “întâlnire la mijloc”.
65 4.6.7 Tripla criptare
Tripla criptare cu două chei
O idee mai bună, propusă de Tuchman, operează pe un bloc de trei ori folosind două
chei: se începe cu prima cheie, se continuă cu a doua cheie și se termină folosind din nou
prima cheie, în sensul că expeditorul criptează cu prima cheie, decriptează cu a doua cheie și
în final criptează cu prima cheie. Destinatarul decriptează cu prima cheie, apoi criptează cu a
doua cheie și în final decriptează cu prima cheie:
C = EK1 (DK2(EK1 (P)))
P = DK1(EK2 (DK1 (C)))
Aceasta poartă numele de mod EDE (encrypt -decrypt -encrypt ); dacă algoritmul bloc
are o cheie de n biți, această schemă conduce la o cheie de 2n biți. Această formă curioasă de
criptare -decriptare -criptare a fost proiectată de IBM, pentru a păstra compatibilitatea cu
implementarea convențională a algoritmului: dacă cele două chei sunt identice, tripla criptare
se reduce la o singură criptare cu o singură cheie.
K1 și K2 alterne ază, pentru a preveni posibilitatea de a folosi un atac de tip “întâlnire la
mijloc”. Dacă C = EK2 (EK1 (EK1 (P ))), atunci criptanalistul poate calcula EK1 (EK1 (P )) pentru
toate valorile K1 posibile, după care pornește atacul. Ar fi necesare doar 2n+2 criptări.
Tripla criptare cu două chei nu permite un atac de tip “întâlnire la mijloc” de genul celui
întâlnit în cazul dublei criptări, dar Merkle și Hellman au proiectat un alt gen de atac, care
poate sparge tripla criptare cu două chei în 2n-1 pași folos ind 2n blocuri de memorie.
Pentru fiecare K2 posibil, se decriptează 0 și se memorează. Apoi, se decriptează cu
fiecare K1 posibil, pentru a -l găsi pe P. Se criptează triplu P pentru a -l afla pe C, după care se
decriptează C cu K1. Dacă această decriptare este o decriptare a lui 0 folosind K2 (din
memorie) atunci perechea K1, K2 este o posibilă candidată. Dacă această posibilitate nu se
verifică, se continuă căutarea.
Acesta este un atac cu texte în clar alese, care necesită o mare cantitate de texte în cla r
alese și anume 2m, în timp ce memoria și durata sunt de ordinul 2n. Nu este foarte practic, dar
subliniază o slăbiciune a algoritmului.
Paul van Oorschot și Michael Wiener au convertit aceasta la un atac cu 2p texte în clar
cunoscute. Exemplul presupune modul EDE:
1. Se ghicește valoarea intermediară a.
2. Se calculează și memorează pentru fiecare K1 posibilă, a doua valoare
intermediară b, când prima valoare intermediară este a, folosind textul în clar
cunoscut:
b = DK1 (C)
66 3. Se caută în tabelul memorat, pentru fiecare K2 posibil, elemente cu aceeași
valoare intermediară b:
b = EK2 (a)
4. Probabilitatea de succes este p/m, unde p este numărul de texte în clar
cunoscute și m este mărimea blocului. Dacă nu se găsesc elementele căutate la
pasul 3, se alege o nouă valo are pentru a și se reia de la pasul 1.
Acest atac necesită 2n+m/p timp operațional și p spațiu de memorie. Pentru DES, aceasta
înseamnă 2120/p. Pentru p mai mare ca 256, acest atac este mai rapid decât căutarea
exhaustivă.
Tripla criptare cu trei chei
Această variantă presupune o lungime totală a cheii mai mare, dar memorarea cheii nu
constituie o problemă.
C = EK3 (DK2(EK1 (P)))
P = DK1(EK2 (DK3 (C)))
Cel mai bun atac cere 22n pași și 2n blocuri de memorie si este de tip “întâlnire la
mijloc”.
Tripla criptare cu trei chei independente este echivalentă din punct de vedere al
securității, cu dubla criptare.
4.6.8 Concluzii
Criptografia cu chei simetrice și cea cu chei publice prezintă diverse avantaje și
dezavantaje pe care le prezentăm în contin uare:
(i) Avantaje ale criptografiei cu chei simetrice
1. Algoritmii folosiți permit gestionarea unor volume mari de date, cu viteză relativ
bună. În special atunci când este vorba de implementări hard.
2. Cheile folosite pentru algoritmii simetrici sunt relat iv scurte.
3. Algoritmii simetrici pot fi folosiți ca primitive pentru a construi soluții
criptografice incluzând generatoarele de numere pseudo -aleatoare și funcțiile
hash.
67 4. Algoritmii cu chei simetrice se pot compune pentru a produce algoritmi mai
puternici.
(ii) Dezavantajele criptografiei cu chei simetrice
1. Într-o comunicație cheia trebuie să rămână secretă în ambele capete.
2. Într-o rețea cu mulți utilizatori numărul cheilor care trebuie gestionate devine o
problemă majoră.
3. Pentru o comunicație între două păr ți, practica criptografică impune schimbul
cheilor frecvent, uneori chiar la fiecare sesiune, ceea ce în condițiile unui canal
nesigur de comunicație este o altă problemă.
(iii) Avantajele criptografiei cu chei publice
1. Dintre cele două chei folosite în al goritmii cu chei publice doar una trebuie
ținută secret.
2. Administrarea cheilor într -o rețea poate fi făcută cu un singur administrator “de
încredere”.
3. În general perechile de chei publice/secrete pot fi folosite pe o perioada lungă de
timp fără a fi schimb ate.
4. Într-o rețea de dimensiuni mari numărul de chei necesare este considerabil mai
mic decât în cazul criptografiei simetrice.
(iv) Dezavantajele criptografiei cu chei publice
1. Viteza algoritmilor cu chei publice (chiar și a celor mai performanți) este d e
câteva ori mai mică decât a celor cu chei secrete.
2. Dimensiunea cheilor folosite este mai mare (1024 pentru RSA în comparație cu
64 sau 128 în cazul algorimilor de tip bloc).
3. Pentru nici un algoritm cu chei publice nu s -a demonstrat că ar fi “sigur”;
securitatea lor se bazează prezumția de dificultate a unui set de probleme de
teoria numerelor.
4. Istoria criptografiei cu chei publice este relativ scurtă (din 1970) .
Utilizarea algoritmilor în sisteme de criptare disponibile în Internet
Aplicațiile și protoc oalele folosite în Internet au nevoi diferite de securitate, în funcție
de care se utilizează diverse sisteme criptografice. Se observă că nu există un algoritm unic
bun pentru orice situație – în funcție de noile rezultate obținute în proiectarea criptogr afică,
dar și în criptanaliză, se renunță la unii algoritmi sau se dezvoltă variante îmbunătățite din
punct de vedere al securității.
68 În Internet, sistemele criptografice pot fi grupate în două mari categorii: protocoale de
rețea și programe/protocoale fol osite pentru criptarea mesajelor trimise prin poșta electronică
(tabelul 4.6.3).
Nr. Sistem Caracteristici Principalii
algoritmi
1 PCT (Private
Communications
Technology)
Protocol criptare transmisii
TCP/IP
RSA
RC4
MD5
2 SSL (Secure Socket
Layer)
Protocol criptare transmisii
TCP/IP RSA
RC4
MD5
3 S-HTTP – Secure –
HyperText Transfer
Protocol Protocol pentru criptarea cererilor și
răspunsurilor HTML RSA
DES
4 SET (Secure Electronic
Transaction) Protocol criptare transmisii de
instrucțiuni de platã pri n Internet RSA
MD5
RC2
5 CyberCash Protocol criptare transmisii
instrucțiuni de platã prin Internet RSA
MD5
RC2
6 Ipsec, Ipv5 Protocol de nivel scăzut pentru criptarea
pachetelor IP Diffie –
Hellman
7 DNSSEC (Domain Name
System Security)
Sistem pentru s ecurizarea
DNS RSA
MD5
8 Kerberos Securitate în rețea pentru aplicațiile de
nivel înalt DES
9 SSH (Secure Shell) Protecție pentru Telnet la
transferul de fișiere RSA
Diffie –
Hellman
Des
Triple DES
10 S/MIME – Secure
Multipurpose Internet Mail
Extension Format pentru criptarea poștei
electronice
Specificații
utilizator
11 PGP (Pretty Good
Privacy) Aplicație pentru criptarea poștei
electronice
MD5
IDEA
RSA
Tabelul 4.6.3 Algoritmi de criptare utilizați în aplicațiile din Internet
69 Capitolul 5
Aplica ție. Algoritmul RSA și implementarea lui
5.1 Codul RSA
5.1.1 Descriere generală
RSA este unul dintre primele criptosisteme practice cu cheie publică și este utilizat pe
scară largă pentru transmiterea securizată a datelor. Într-un astfel de sistem de criptare, cheia
de criptare este publică și diferită de cheia de decriptare care este păstrată secretă (privată). În
RSA, această asimetrie se bazează pe dificultatea practică de a factoriza produsul a două mari
numere prime, problema factoriz ării. RSA es te alcătuită din literele inițiale ale numelor de
familie ale lui Ron Rivest, Adi Shamir și Leonard Adleman, care au descris inițial algoritmul
în 1978. Clifford Cocks, un matematician englez care lucra pentru agenția britanică de
informații GCHQ, a dezvol tat un sistem echivalent 1973, dar nu a fost declasificată până în
1997. Un utilizator de RSA creează și publică o cheie publică bazată pe două numere prime
prime, împreună cu o valoare auxiliară. Numerele prime trebuie păstrate în secret. Oricine
poate fo losi cheia publică pentru a cripta un mesaj, dar cu metodele publicate în prezent, dacă
cheia publică este suficient de mare, numai cineva care are cunoștințe despre numerele prime
poate decodifica acest mesaj. Ruperea criptării RSA este cunoscută sub nume le de problema
RSA; dacă este la fel de greu ca problema f actorizării rămâne o întrebare deschisă. RSA este
un algoritm relativ lent și din acest motiv este mai puțin frecvent folosit pentru criptarea
directă a datelor utilizatorului. Mai des, RSA trece ch ei partajate criptate pentru criptografia
cheilor simetrice, care la rândul lor pot efectua operațiun i de criptare -decriptare în mas ă la o
viteză mult mai mare. .
5.1.2 Opera ții:
Generarea de chei:
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ă n = pq și Φ = (p – 1)(q – 1)
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 calculea ză întregul d, unicul cu
proprietatea că de ≡1mod Φ . (n, d) constituie cheia secretă.
70 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 poat e juca
oricare dintre roluri[4]. Î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. 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 :
c≡mᵉ (mod n)
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ă:
de ≡1mod Φ
Astfel, mesajul clar este recuper at calculând:
m= cᵈ (mod n)
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 c heile 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 cl ar (sau cu hash -ul
acestuia), că într -adevăr acea entitate este autorul mesajului.
71
Implementarea algoritmului RSA
Programul criptează și decriptează textul introdus de la tastatură.
Utilizatorul poate alege din meniul programului una din opțiunile:
1. Criptare text: Se cere cheia pentru criptarea textului. Utilizatorul apasă space pentru
confirmare a cheii . După introducerea și confirmarea cheii utilizatorul indică numele
fișierului unde sunt datele de criptat și numele fișierului în care vor fi înscrise datele
criptate.
2. Decriptare text: Este cerută cheia cu ajutorul căreia a fost criptat textul. Utilizatorul
apasă space pentru confirmare a cheii . După introducerea și confirmarea cheii
utilizatorul indică numele fișierului unde sunt datele criptate și nume le fișierului în care
vor fi înscrise datele decriptate.
3. Criptare text de la tastatură : Este cerută cheia pentru criptarea textului. Utilizatorul
apasă space pentru confirmare a cheii . După introducerea și confirmarea cheii
utilizatorul tastează textul care trebuie criptat, totodată văzând rezultatul criptării.
4. Decriptare text de la tastatură : Este cerută cheia cu ajutorul căreia a fost criptat
textul. Utilizatorul apasă space pentru confirmare a cheii . După introducerea și
confirmarea cheii utilizatorul tast ează textul care trebuie decriptat, totodată văzând
rezultatul decriptării
9. Informații despre program
0. Ieșire
72
1. /*
2. Implementarea algoritmului RSA in C++
3. */
4. #include<iostream>
5. #include<math.h>
6. #include<string.h>
7. #include<stdlib.h>
8.
9. using namespace std;
10.
11. long int p, q, n, t, flag, e [100], d[100], temp[100], j, m[100],
en[100], i;
12. char msg[100];
13. int prime(long int);
14. void ce();
15. long int cd(long int);
16. void encrypt();
17. void decrypt();
18. int prime(long int pr)
19. {
20. int i;
21. j = sqrt(pr);
22. for (i = 2; i <= j; i++)
23. {
24. if (pr % i == 0)
25. return 0;
26. }
27. return 1;
28. }
29. int main()
30. {
31. cout << "\n INTRODUCETI PRIMUL NR PRIM\n";
32. cin >> p;
33. flag = prime(p);
34. if (flag == 0)
35. {
36. cout << "\n INPUT GRESIT\n";
37. exit(1);
38. }
39. cout << "\n INTRODUCETI AL DOILEA NR PRIM \n";
40. cin >> q;
41. flag = prime(q);
42. if (flag == 0 || p == q)
43. {
44. cout << "\n INPUT GRESIT\n";
45. exit(1);
46. }
73 47. cout << "\n INTRODUCETI MESAJ\n";
48. fflush(stdin);
49. cin >> msg;
50. for (i = 0; msg[i] != NULL; i++)
51. m[i] = msg[i];
52. n = p * q;
53. t = (p – 1) * (q – 1);
54. ce();
55. cout << "\n POSBILE VALORI ALE LUI e SI d SUNT: \n";
56. for (i = 0; i < j – 1; i++)
57. cout << e[i] << "\t" << d[i] << "\n";
58. encrypt();
59. decrypt();
60. return 0;
61. }
62. void ce()
63. {
64. int k;
65. k = 0;
66. for (i = 2; i < t; i++)
67. {
68. if (t % i == 0)
69. continue ;
70. flag = prime(i);
71. if (flag == 1 && i != p && i != q)
72. {
73. e[k] = i;
74. flag = cd(e[k]);
75. if (flag > 0)
76. {
77. d[k] = flag;
78. k++;
79. }
80. if (k == 99)
81. break;
82. }
83. }
84. }
85. long int cd(long int x)
86. {
87. long int k = 1;
88. while (1)
89. {
90. k = k + t;
91. if (k % x == 0)
92. return (k / x);
93. }
94. }
74 95. void encrypt()
96. {
97. long int pt, ct, key = e[0], k, len ;
98. i = 0;
99. len = strlen(msg);
100. while (i != len)
101. {
102. pt = m[i];
103. pt = pt – 96;
104. k = 1;
105. for (j = 0; j < key; j++)
106. {
107. k = k * pt;
108. k = k % n;
109. }
110. temp[i] = k;
111. ct = k + 96;
112. en[i] = ct;
113. i++;
114. }
115. en[i] = -1;
116. cout << "\n MESAJUL CRIPTAT ESTE\n";
117. for (i = 0; en[i] != -1; i++)
118. printf("%c", en[i]);
119. }
120. void decrypt()
121. {
122. long int pt, ct, key = d[0], k;
123. i = 0;
124. while (en[i] != -1)
125. {
126. ct = temp[i];
127. k = 1;
128. for (j = 0; j < key; j++)
129. {
130. k = k * ct;
131. k = k % n;
132. }
133. pt = k + 96;
134. m[i] = pt;
135. i++;
136. }
137. m[i] = -1;
138. cout << "\n MESAJUL DECRIPTAT ESTE: \n";
139. for (i = 0; m[i] != -1; i++)
140. printf("%c", m[i]);
141. }
75 Bibliografie .
[1] An Introd uction to Cryptography , Copyright © 1990 -1999 Network Associates, Inc.
and its Affiliated Companies.
[2] Phillip R. Zimmermann , Cryptography for the Internet .
[3] R.L. Rivest, A. Shamir, L Adleman, A Method for Obtaining Digital Signatures and
Public -Key Cryptosys tems.
[4] Bruce Schneier, Applied Cryptography, Second Edition: Protocols, Algorthms, and
Source Code in C (cloth), 1996 .
[5] Joppe W. Bos, J. Alex Halderman, Nadia Heninger , Jonathan Moore, Michael
Naehrig, Eric Wustrow, Elliptic Curve Cryptography in Practice .
[6] Whitfield Diffie, Martin E. Hellman New Directions in Cryptography
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Lect. Constantinescu Nicolae [620962] (ID: 620962)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.