Criptosisteme CU Chei Simetrice Si CU Chei Publice
UNIVERSITATEA DIN ORADEA
FACULTATEA DE ȘTIINȚE
PROGRAMUL DE STUDIU SISTEME DISTRIBUITE ÎN INTERNET
FORMA DE ÎNVĂȚĂMÂNT ZI
LUCRARE DE DISERTAȚIE
COORDONATOR ȘTIINȚIFIC
PROF.UNIV.DR. POPESCU CONSTANTIN
ABSOLVENT
VESA COSMIN MIHAI
ORADEA
2015
UNIVERSITATEA DIN ORADEA
FACULTATEA DE ȘTIINȚE
PROGRAMUL DE STUDIU SISTEME DISTRIBUITE ÎN INTERNET
FORMA DE ÎNVĂȚĂMÂNT ZI
CRIPTOSISTEME CU CHEI SIMETRICE ȘI CU CHEI PUBLICE
COORDONATOR ȘTIINȚIFIC
PROF.UNIV.DR. POPESCU CONSTANTIN
ABSOLVENT
VESA COSMIN MIHAI
ORADEA
2015
Cuprins
Introducere………………………………………………………………………………………………………….3
Capitolul I
1.Noțiuni fundamentale………………………………………………………………………………………..5
1.1 Definiții……………………………………………………………………………………………………………………………….5
1.2 Rolul unui criptosistem………………………………………………………………………………………………………..6
Capitolul II
2.Clasificarea criptosistemelor……………………………………………………………………………..9
2.1. Criptosisteme cu chei simetrice………………………………………………………………………………………….9
2.2. Tipuri de cifrare………………………………………………………………………………………………………………12
2.2. Criptosisteme cu chei simetrice………………………………………………………………………………………..14
Capitolul III
3.Criptosisteme cu chei simetrice………………………………………………………………………..17
3.1.Criptosistemul DES……………………………………………………………………………………………………………17
3.1.1 Criptarea unui mesaj cu ajutorul DES……………………………………………………………………………..25
3.1.2 Securitatea DES………………………………………………………………………………………………………………35
3.2. Criptosistemul AES…………………………………………………………………………………………………………..38
Capitolul IV
4.Criptosisteme cu chei publice…………………………………………………………………………..39
4.1.Sistemul de criptare RSA……………………………………………………………………………………………………39
4.1.1. Securitatea criptosistemului RSA……………………………………………………………………………………41
4.2. Prezumții criptografice dificile………………………………………………………………………………………….44
4.3.Sistemul de criptare EL Gamal…………………………………………………………………………………………..47
4.3.1 Securitatea sistemului ElGamal……………………………………………………………………………………….48
4.4.Sisteme asimetrice bazate pe curbe eliptice…………………………………………………………………………49
4.5.Criptarea Menezes – Vanstone……………………………………………………………………………………………53
Capitolul V
5.Comparație între criptosistemele simetrice și criptosistemele cu chei publice…….55
Introducere
Informația a însemnat dintotdeauna putere (în termeni economici, se spune că informația este cel mai scump și valoros factor de producție), iar protecția acesteia a fost întotdeauna un obiectiv principal.
Primele informații referitoare la criptare se cunosc de acum circa patru mii de ani și acestea provin din Egiptul antic sub forma unor formule funerare care conțin, într-o modalitate incipientă, elemente constitutive ale științei de azi.
După cum atestă documentele istorice grecii antici au cunoscut și au practicat în numeroase variante scrierea secretă. Încă din secolul al V-lea î.H. este cunoscută o primă formă a transpoziției, metodă folosită și azi. Pentru cifrare se folosea un instrument denumit scitală – un baston în julul căruia se înfășura, spiră lângă spiră, o panglică de piele, papirus sau pergament pe care, în paralel cu axa, se scriau literele mesajului. După ce textul era scris, panglica era derulată, mesajul devenid indescifrabil, întrucât literele erau dezasamblate. Mesajul putea fi reconstituit numai de acea persoană care dispunea de un baston de lungime și grosime identice cu dimensiunile inițiale pe care să fie înfășurată din nou panglica primită.
În cartea sa „Istoria generală”, istoricul grec Polibiu, acorda o mare importanță păstrării secretului militar. El este cel care a inventat un pătrat, cu ajutorul căruia literele erau codificate prin numere de două cifre, în care cifrele erau linia respectiv coloana pătratului în care se găsea litera. Acest sistem a fost prima formă concretă de schimb secretizat de mesaje.
În evul mediu dezvoltarea criptologiei a luat avânt în strânsă legătură cu extinderea și amplificarea relațiilor diplomatice dintre diferitele state feudale.
Prima carte despre criptologie a apărut în anul 1518 iar metoda prin care cifrarea descrisă era făcută era denumită tablou de transpoziție. Întocmit sub formă pătratică, tabloul era obținut prin deplasarea ciclică spre stânga a alfabetului normal de un anumit număr de ori, după care alfabetele astfel rezultate erau așezate unul sub altul. În acest mod orice literă din prima linie putea fi substituită cu orice literă a alfabetului în funcție de cheia aleasă pentru litera respectivă, și din acest motiv substiuția se numește polialfabetică.
De numele lui Vigenere se leagă dezvoltarea unor modalități noi de cifrare. El a scris „Tratatul cifrurilor sau modalităților secrete de a scrie” (1586) mult citată de criptologi. Din metodele metodele de cifrare descrise în lucrare, multe se bazează pe substituția polialfabetică. Metoda lui Vingenere a fost încorporată în mai multe mașini de cifrat moderne.
Primul criptolog profesionist din Franța, Rosignol, a fost considerat cel mai abil descifrator din Europa.
Rosignol și-a dovedit competența nu numai în domeniul criptanalizei, ci și în cel al cifrării. El a reușit să modifice modul de stabilire a corespondenței între elementele clare ale mesajului și cifruri, introducând două tipuri de corespondențe, denumite tabel de cifrare și tabel de descifrare.
Dezvoltarea sau recesiunea criptografiei coincide cu evoluția marilor imperii și civilizații. Criptografia nu apare și nu se dezvoltă decât în acele locuri unde puterea trebuie protejată, așadar, apariția telegrafului și a radioului precum și cele două războaie mondiale din secolul XX au fost factori puternici de stimulare pentru procesul de dezvoltare a metodelor și tehnicilor de criptare.
Dezvoltarea criptografiei a fost mult stimulată datorită inventării telegrafului. În condițiile dezvoltării impetuase a industriei și comerțului acest aparat de transmitere a informației avea rolul de a satisface nevoile crescânde de comunicare. Telegraful a dus la schimbări substanțiale și în activitatea comandamentelor militare; conducerea operativă a acestora și creșterea numărului mesajelor transmise. A apărut necesitatea de a face distincție între un sistem de scriere cifrată destinat pentru un schimb temporar de scrisori între un număr redus de persoane și o metodă criptografică pentru un trafic intens de mesaje.
Începând cu perioada de dinaintea primului război mondial, radioul a fost folosit intens pentru a fi transmise infromații secrete militare și diplomatice. În paralel cu creșterea volumului de informație transimisă pe această cale, a luat avânt și activitatea de criptanaliză. Pentru apărarea secretului mesajelor diplomatice, s-a introdus o nouă metodă de criptografie. Metoda consta în utilizarea drept cheie a unor blocuri formate din cifre alese la întâmplare și tipărite, foile ce conțineau aceste grupuri de cifre fiind legate într-un volum. Fiecare foaie se folosea o singură dată, după care era distrusă. Deși ținută în cel mai mare secret, metoda s-a răspândit în decurs de 10-15 ani în întreaga lume. Folosită și azi, ea este considerată una dintre cele mai sigure metode criptografice.
Dezvolatarea calculatoarelor electronice în ultimele decenii a schimbat rapid evoluția criptografiei în două direcții fundamentale: utilizarea criptografiei – numită în acest caz și computațională – pentru a fi protejate datele memorate și transmise între calculatoare și utilizarea calculatoarelor pentru descifrarea unor criptosisteme complexe, deci în criptanaliză.
Criptografia este folosită în zilele noastre aproape în orice sistem de comunicație, rețea de calculatoare sau sistem informatic. Exemple din viața de zi cu zi care folosesc criptarea: cardul bancar cu chip folosit în automatele bancare sau la plata într-un magazin, cardul SIM dintr-un telefon mobil, banala telecomanda pentru activarea alarmei de la mașină, autentificarea la serverul de email, tranzacțiile online pentru cumpărături (eBay, PayPal), comunicația de tip wireless WiFi, televiziunea digitală.
Capitolul I
Noțiuni fundamentale
1.1 Definiții
Criptografia (cryptography) este știința creării și menținerii mesajelor secrete, adică cititorilor neautorizați le este imposibil să le citească (știința mesajelor secrete).
Mesaj (text) inițial (M) (plain / clear text) este mesajul ce urmează a fi criptat; în criptografie M se numește scriere chiar dacă este un document de alt tip, de exemplu sunet, imagini, date.
Mesaj cifrat (criptograma) (C) (cipher text) este mesajul secretizat, inaccesibil neavizaților.
Criptare / cifrare (E) (encryption / enciphering) este procedeul de ascundere a mesajului inițial M în mesaj C astfel încât mesajul M nu poate fi citit până când acesta nu este decriptat.
E(M)=C
Decriptare / descifrare (D) (decryption / deciphering) este procedeul de regăsire a mesajului în clar M din mesajul cifrat C.
D(C) = D(E(M))=M
Algoritm criptografic cifru (cryptographic algorithm / cipher) este funcția sau funcțiile matematice ce sunt utilizate pentru criptare / decriptare, adică ansambul transformărilor care sunt aplicate asupra mesajului M pentru ca acesta să devină textul cifrat C; în mod obișnuit există două funcții: una pentru criptarea mesajului (E) și alta pentru decriptara textului cifrat (D).
Cheia criptografica (K) (key) este mărimea (în majoritatea cazurilor secretă) necesară realizării criptării și decriptării.
Criptosistem (cryptosistem) este sistemul format din:
-algoritmul de criptare
-toate mesajele inițiale (M)
-toate textele cifrate (C)
-toate cheile (K)
Criptanaliza (cryptanalysis) este știința spargerii cifrurilor, deci a obținerii mesajelor inițiale (M) sau a cheii (K) din mesajul cifrat (C).
Criptanalist (cryptanayst) este persoana care se ocupă cu criptanaliza. Atac(attack) este încercarea sau tentativa criptanalitică.
Criptologie(cryptology) este știința care se ocupă atât de criptografie cât și de criptanaliză. Criptolog (cryptologist) este persoana care se ocupă cu criptologia.
Steganografia(steganography) este tehnica ascunderii mesajelor secrete în alte mesaje, în așa fel încât existenta mesajelor secrete să fie invizibilă.
A,B – emițătorul respectiv receptorul mesajului
E – funcția de criptare(cifrare)
D – funcția de decriptare(descifrare)
M – spațiul mesajelor în clar
C – spațiul criptogramelor(text cifrat)
K – spațiul cheilor
Ke – spațiul cheilor de criptare
Kd – spațiul cheilor de decriptare
Definiția 1.1
metodă
În general se consideră [1]
1.2 Rolul unui criptosistem
Criptosistemul într-un sistem informatic este realizat pentru a descoperi și a preveni activitățile care nu sunt permise, cum ar fi: modificarea, ștergerea sau distrugrerea mesajelor existente, inserarea de mesaje false, conectările neautorizate, consultarea informațiilor transmise sau stocate.
Cele 3 caracteristici absolut necesare interacțiunii dintre calculatoare sunt:
Confidențialitatea sau protecția datelor – se referă la faptul că informațiile transmise sunt inaccesibile unui utilizator neavizat
Autentifiacrea se aplică pentru:
-entități și în acest caz are denumirea de autentificarea entităților
-informație, aceasta trebuie să fie autentică în sensul originii, conținutului datelor
Integritatea datelor (data integrity). – aceasta este proprietatea de a putea evita orice modificare neautorizată a informației, cum ar fi inserare, substituție, ștergere și sunt folosite diferite metode pentru a putea identifica sau împiedica astfel de schimbări.
Semnătura digitală se referă că utilizatorul B cel care primește mesajul este sigur că acesta a fost trimis de utilizatorul A prin faptul că mesajele acestuia sunt semnate (SA), iar utilizatorul A este sigur că nimeni nu poate să îi atribuie un mesaj fals deoarece mesajul pe care l-a transmis are semnătura lui.
Desigur că există și alte obiective mai particulare dar cu aceeași relevanță care trebuie amintite. Actualitatea informației se referă la asigurarea faptului că informația primită este actuală (proaspătă). Interpretarea aspectului se face astfel: pe de o parte face referire la faptul că informația să expire după o anumită perioadă de timp, pe de altă parte face referire la faptul că un adversar ar putea să schimbe ordinea în care pachetele cu informație ajung la destinație. Este realizată prin intermediul parametrilor varianți în timp: amprente temporale (time stamps), numere aleatoare, contoare (counter), etc.
Anonimitatea se referă la posibilitatea de a împiedica ca identitatea unei entități care a cerut un serviciu să fie identificată. De exemplu, aceast aspect poate fi foarte folositoar în tranzacții bancare când nu se dorește să se identifice persoana care sau către care se face o plată, sau în trimiterea mesajelor prin e-mail pentru a păstra anonimitatea expeditorului, etc. Este îndeplinită fie cu ajutorul protocoalelor, fie prin funcții criptografice create pentru acest scop. De exemplu există un puternic segment de cercetare în zona funcțiilor de criptare cu renegare (deniable encryption), prin care se poate cripta informație al cărei conținut poate fi schimbat la decriptare, făcând astfel renegabilă orice informație criptată (nu există pentru aceasta soluții eficiente până în prezent).
Autorizarea face referire la a controla accesul și la a preveni ca agenții neautorizați să intre în sistem. Relația între autentificarea entităților și controlul accesului este aceea că cel din urmă element se construiește în general pe primul (e normal să fie necesară o metodă de a autentifica entitatea înainte de a-i permite accesul) dar ele sunt totuși distincte. Aceasta pentru că autorizarea presupune folosirea unui mecanism de autentificare și a unei politici de securitate având ca scop deciderea dreptului de acces al unor entități asupra unor resurse.
Disponibilitatea se referă la asigurarea faptului că un serviciu este accesibil la solicitarea unui utilizator legitim. Obiectivul acesta presupune că o entitate neautorizată nu poate să blocheze accesul unei entități care este autorizată la serviciile oferite de sistem. În cazul acesta însă nu intră în discuție problemele legate de autorizarea accesului, anterior amintite, ci cele de disponibilitate a resursei în sine. Aceasta presupune a evita problemele de epuizare a resurselor sistemului din cauza utilizării nelegitime a acestora.
Protecția părților terțe se referă la evitarea de a transmite pericolul asupra părților cu care există o legătură. De exemplu atacul asupra unei anume componente IT nu va defecta și altă componentă, sau din punct de vedere economic: căderea unei componente datorită unei erori de manipulare nu va duce la discreditarea producătorului, etc.
Revocarea se referă la posibilitatea de a revoca un drept oferit. Poate cel mai relevant exemplu legat de criptografie este posibilitatea ca un certificat de cheie publică să fie revocat de către entitatea care l-a emis.
Trasabilitatea sau urmărirea unui sistem se referă la faptul că istoricul funcționării sistemului poate fi reconstituit pe baza înregistrărilor, de exemplu înregistrarea comenzilor relevante, a persoanelor care le-au lansat etc. obiectivul este relevant în determinarea cauzelor eventualelor problemelor de funcționare.
Capitolul II
Clasificarea criptosistemelor
Criptosistemele se clasifică în criptosisteme cu chei simetrice și criptosisteme cu chei publice.
2.1. Criptosisteme cu chei simetrice
Criptosistemele cu chei simetrice sunt acele criptosisteme în care cheia folosită la criptarea mesajului este identică cu cheia folosită la decriptarea textului cifrat. Criptografia care apelează la astfel de criptosisteme are denumirea de criptografie convențională sau criptografie simetrică sau criptografie cu o singură cheie.
Acestor criptosisteme au caracteristica că criptarea mesajului clar și decriptarea textului cifrat se realizează foarte ușor dacă se cunoaște cheia . Astfel , și
Figura 2.1. Model criptografia simetrică [9]
Definiție. o schemă (sistem) de criptare cu cheie simetrică (secretă) este compusă din trei algoritmi: algoritmul prin care se generarează cheia care primește ca intrare nivelul de securitate și returnează cheia, algoritmul de criptare care primește ca intrare mesajul m și cheia și returnează mesajul criptat și algoritmul de decriptare care primește ca intrare un text criptat și cheia și returnează mesajul decriptat m.[2]
Două proprietăți sunt esențiale pentru schemele simetrice:
Fără cheia din criptotextul nimic nu se poate afla despre mesajul m
Criptotextul împruenă cu orice informație cu privire la mesajul m nu aduce nicio informație cu privire la .
Nu sunt însă nicidecum singurele proprietăți ale unei scheme de criptare simetrică. La acestea pot fi adăugate proprietăți avansate, cum ar fi faptul că adversarului îi este imposibil să modifice mesajul din interiorul unui criptotext, fără ca acesta să aibă acces la cheia , chiar dacă m este cunoscut, un adversar nu poate altera fără ca receptorul mesajului să poată detecta acest lucru în momentul decriptării. Proprietatea are numele de non-maleabilitate(non-maleability). O altă proprietate aceea că adversarul nu poate distinge dacă este criptat un bit de valoare 0 sau un bit de valoare 1. Adică având și , fără cunoașterea cheii K unui adversar îi este imposibil să spună care este criptarea lui 1 și care a lui 0. Această proprietate poartă numele de imperceptibilitatea sau nedistingerea criptotextelor. Viteza cu care se face criptarea și decriptarea mesajelor constituie avantajul algoritmilor simetrici, aceasta fiind una ridicată. Dacă îi comparăm cu algoritmii cu chei publice aceștia din urmă sunt mai rapizi cu câteva ordine de magnitudine, de 10, 100 sau chiar 1000 de ori. În ceea ce privește deficiențele, una dintre deficiențele algoritmilor simetrici este aceea a imposibilității de a fi efectuată o comunicare pe un canal nesecurizat înainte (necesită partajarea prealabilă a unui secert). În același context, al cheilor partajate, deficiența acestor algoritmilor este aceea că odată cu creșterea numărului de participanți la comunicare crește și numărul de chei secrete care trebuie cunoscute.
Figura 2.2 Schema algoritm criptare cu cheie secretă [2]
Figura 2.3 Schema decriptare algoritm cu cheie secretă [2]
La baza cifrurilor simetrice, stau cifrurile elementare cum ar fi: transpoziția și substituția.
Cifrurile de transpoziție permută caracterele cifrului inițial . Cheia de cifrare este perechea , unde d reprezintă lungimea blocurilor succesive de caractere care vor fi cifrate conform permutării f.
de forma
1 2 … d
f(1) f(2) …f(d) Mulțimea funcțiilor astfel definite este d!. În acest fel mesajul clar
este cifrat astfel
Cifrurile de substituție înlocuiesc caracterele din alfabetul mesajelor A cu un caracter din alfabetul criptogramelor C. Dacă atunci
Unde
Este funcția de substituție, cheia cifrului.
Cifrarea unui mesaj se face astfel:
Deci substituțiile sunt transformări prin care caracterele(literele) sau grupurile de caractere ale alfabetului primar sunt înlocuite cu caracterele sau grupurile de caractere ale alfabetului secundar. În practică se aplică frecvent substituția care se poate descrie astfel
C=aM + b(mod N)
În acest scop se stabilește o corespondență biunivocă între literele alfabetului primar și numerele întregi 0,1, … ,n-1 care formează un inel, , față de operațiile de adunare modulo și înmulțirile modulo / În relație, a se numește factor de amplificare, iar b coeficientul de deplasare. În cazul cel mai simplu se stabilește o corespondență între literele ale alfabetului primar și elementele alfabetului secundar al criptogramei.
2.2. Tipuri de cifrare
Criptosistemele cu chei simetrice mai pot fi clasificate în funcție de tipul de algoritm folosit în criptosisteme cu cifru bloc și cifrare secvențială.
În cifrarea bloc se lucrează cu blocuri de text clar și cifrat de 64 de biți. Cifrarea secvențială lucrează cu secvențe de text clar și cifrat de un bit sau un octet.
Cifruri bloc
Cifrare carte de coduri (Electronic CodeBook-ECB)
În cazul ECB, același bloc de text clar se cifrează întotdeauna în același bloc de text cifrat. În acest fel devine posibilă crearea unei cărți de coduri prin asocierea text clar –text cifrat. Dacă vorbim de blocurile cu dimensiunea de 64 de biți ar rezulta un număr de intrări în cartea de coduri, aceasta fiind o dimensiune mult prea mare pentru memorare și manipulare. De obicei se aleg aleator blocuri din cadrul fișierului. Sistemul acesta de cifrare are un punct slab, acesta fiind că criptanalistului îi este oferită posibilitatea de a realiza o carte de coduri în cazul în care acesta denține textul clar și textul cifrat. [4]
Cifrarea bloc cu înlănțuire (Cipher Block Chaining – CBC)
Este specific pentru aceste tip de cifrare folosirea unui mecanism de feedback, fiindcă rezultatul care apare după ce se cifrează un bloc anterior revine prin buclă și are rol în cifrarea blocului curent.Cu alte cuvinte, blocul de dinainte este folosit pentru a modifica cifrarea blocului care urmează. Așadar, consecința este că textul cifrat depinde nu doar doar de textul clar, el este făcut XOR cu blocul de text cifrat anterior. După ce blocul de text clar este cifrat, textul cifrat rezultat este sumat mod 2 cu blocul din registrul de reacție și devine următoarea intrare în procesul de cifrare. După cifrare, conținutul registrului este înlocuit cu blocul cifrat. Prin urmare, cifrarea blocului i depinde de toate cele i-1 blocuri anterioare.[4]
Matematic, procesul de criptare și de decriptare decurge astfel:
Figura 2.4. Cifrarea bloc cu înlănțuire[10]
În cazul în care sunt criptate două mesaje prin CBC ele vor fi identice. Pentru ca aceste lucru să fie împiedicat se poate cripta primul cu un vector de date aleator. Dacă acesta este adăugat mesaje clare de text identice vor fi criptate diferit. Vectorul nu trebuie ținut secret.
Dacă acest lucru pare greșit, să considerăm că avem un mesaj din câteva blocuri, B1, B2, . . . , Bi, astfel încât B1 este cifrat cu vectorul aleator, B2 este cifrat utilizând ca vector aleator textul cifrat de la B1,etc. Dacă avem n blocuri, sunt n − 1 vectori de inițializare expuși, chiar dacă vectorul original este
ținut secret.[4]
Cifruri secvențiale
Cifrarea cu reacție (Cipher Feedback – CFB)
Cifrul CFB pe 8 biți, ce lucrează cu blocuri de 64 de biți, operează cu o coadă egală cu cea a blocului. Coada este criptată, iar cei mai din stânga 8 biți ai rezultatului sunt făcuți XOR cu primul caracter din textul cifrat. Se face deplasare cu 8 biți spre stânga, aceștia fiind astfel pierduți. Următorul caracter din textul clar este criptat după același tipic. Decriptarea este procesul invers.[4]
Figura 2.5 Cifrarea cu reacție[2]
Ca și modelul CBC, modelul CFB face ca cifrarea unui caracter din textul clar să depindă de cele criptate anterior.
2.2. Criptosisteme cu chei simetrice
În anul 1976 Whitfield Diffie și Maartin Hellman au pus bazele criptografiei asimetrice cu chei publice. În locul de o singură cheie secretă, criptografia asimetrică folosește două chei care sunt diferite, una fiind folosită pentru cifrare, alta fiind folosită pentru decifrare.
Definiție. o schemă de cifrare cu cheie publică (criptosistem cu cheie publică) are trei algoritmi: algoritmul pin care se generează cheile care primește ca parametru nivelul de securitate și returnează perechea cheie publică-privată), algoritmul prin care se realizaează criptarea care primește mesajul m și cheia publică și returnează criptotextul și algoritmul prin care se realizează decriptarea care primește criptotextul c și cheia privată și returnează mesajul m. [2]
În acest moment cele mai cunoscute sisteme de criptare cu cheie publică sunt:
Sistemul RSA: se bazează pe dificultatea cu care se descompun în factori primi numerele mari (de sute de cifre). Este sistemul cel mai larg utilizat în acest moment.
Sistemul El Gamal: se bazează pe dificultatea de a calcula logaritmul discret într-un corp finit
Sistemul Merkle-Hellman: primul sistem definit cu cheie publică, bazat pe problema {0,1} a rucsacului, problema NP-complectă
Curbe eliptice: Sunt sisteme de criptare care își desfășoară calculele pe mulțimea punctelor unei curbe eliptice (în locul unui inel finit )
Începutul criptografiei cu cheie publică este marcat de schimbul de cheie Diffie-Hellman. Funcționalitatea unui criptosistem cu cheie publică se realizează în esență prin chimbul bazat pe informații asimetrice a unei chei secrete care apoi poate fi utilizată pentru criptarea unei informații .
Algoritmul Diffie-Hellman are la bază problema dificilă a determinării logaritmului discret.
Acest algoritm nu are rolul de a cripta mesajele sau de a crea semnături digitale. Scopul lui este distribuirea cheilor, adică de a face posibil schimbul unei chei secrete între doi utilizatori, deci algoritmul este limitat la schimbul cheilor secrete.
Problema logaritmului discret constă în următoarele
Fiind date un grup ciclic finit, un generator al lui G și un element y din G, se cere să se găsească un număr întreg a , astfel încât .
Algoritmul Diffie-Hellman pentru schimbul de chei constă în următoarele
Sally și Sam convin asupra unui număr mare prim și a unui generator .
Sally alege (generează aleator) un număr secret a, și îi trimite lui B numărul A:
Sam alege(generează aleator) un număr secret a, și îi trimite lui Sally numărul B:
Sally calculează.
Sam calculează.
Menționăm că p și nu este necesar să fie ținute secrete.
În realizările practice ale Algoritmului Diffie-Hellman pentru a și b se utilizează chei de ordinul 10100 și p de ordinul 10300 . Numărul α nu este neapărat mare și de obicei are valori mai mici ca 10. Ținând cont de aceste mărimi ale parametrilor a, b și p putem afirma cu certitudine că securitatea algoritmului este una ridicată, deoarece determinarea cheii secrete cunoscând numai α, p, b mod p, b mod p (fără a cunoaște a și b – ele fiind menținute în secret) folosind cel mai performant algoritm este o problemă foarte complicată care nu poate să fie rezolvată într-un timp rezonabil.
Exemplu de utilizare a schimbului de chei Diffie-Hellman:
• Sally și Sam convin asupra lui p = 23 și = 5.
• Sally alege aleatoriu a = 6 and și trimite lui Sam
• Sam alege aleatoriu b = 15 și trimite lui Sally
• Sally calculează
• Sam calculează
• Sally și Sam au abținut aleși rezultat, deci cheia secretă comună este k = 2
În practică însă algoritmul Diffie-Hellman nu este utilizat astfel. Algoritmul cu chei publice care domină este algoritmul RSA, deoarece anume pentru RSA a fost creat un centru de cerificare. În plus algoritmul Diffie-Hellman nu poate fi utilizat la semnarea certificatelor. Un alt sistem de criptare cu cheie publică bazat pe problema logaritmului discret este sistemul ElGamal, care conține în sine și algoritmul de semnătură digitală. Schema ElGamal se află la baza standardului de semnătură digitală în SUA (standardul DSA), precum și în Rusia (ГОСТ Р 34.10-94).[7]
Capitolul III
Criptosisteme cu chei simetrice
3.1.Criptosistemul DES
Criptosistemul DES
DES numit și Data Encryption Standard (Standardul de Criptare a Datelor), este predecesorul criptositemului AES, și este un cifru bloc care a fost dezvoltat de cerectătorii de la IBM pentru guvernul Statelor Unite. Criptosistemul a fost selectat de către Biroul Național al Standardelor (National Bureau of Standards) ca un standard oficial de procesare a informațiilor (Federal Information Processing Standard – FIPS) în anul 1976. Are la bază cifrul Lucifer, dezvoltat de Horst Feistel, și este un algoritm care utilizează o cheie simetrică, lungimea cheii fiind de 56 de biți. Chiar dacă la început au apărut foarte multe controverse cauzate de unele elemente de design secrete, o lungime destul micăă a cheii și de anumite suspiciuni legate de faptul că NSA (National Security Agency) ar fi introdus unele slăbiciuni intenționate în criptosistem pentru a-l face mai ușor de spart, după analize academice intense, a reușit să convingă comunitatea științifică de securitatea sa și s-a răspândit și la nivel internațional.
Un bloc are lungimea de 64 de biți, cheia fiind pe 64 de biți dintre care 8 sunt biți de paritate. Algoritmul este caracterizat de o implementare flexibilă și acesta poate fi utilizat în diferite aplicații. Fiecare bloc cifrat este independent de celelalte blocuri. Nu este necesar ca operațiile de criptare și decriptare ale unui bloc să se sincronizeze. Construcția fundamentală a unui bloc DES este o combinație unică a acestor tehnici (o substituție urmată de o permutare) aplicate asupra textului clar, bazată pe cheie. Aceasta ia numele de rundă. Algoritmul DES este compus din 16 runde.
Algoritmul de criptare este format dintr-un număr de permutări, substituții și sumă mod 2, acestea fiind aplicate succesiv de 16 ori, pe un bloc de date cu lungimea de 64 de biți, prin folosirea la fiecare rundă a unei chei diferite cu lungime de 48 de biți, aceasta provenind dintr-o cheie cu lungimea de 56 de biți. Împărțirea datelor este făcută în blocuri de 64 de biți și ele sunt criptate fără să fie modifcată lungimea lor.
Cifrarea este compusă din trei categorii de prelucrări care se fac asupra blocului cu text clar de intrare:
a) Blocului mai întâi i se aplică o permutăre inițială IP de forma:
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
În cazul acestei permutări bitul 58 de intrare devine primul bit de ieșire, bitul 34 devine al patrulea , bitul 2 al optulea ș.a.m.d, bitul 7 devine ultimul (al 64-lea)
b) Apoi blocul care a fost permutat trece printr-un calcul complex care depinde de cheie și care constă în 16 iterații funcționale identice. Luând în considerare cei 64 de biți ai unui bloc ce este supus unei iterații i, vom nota cu și cele două jumătăți de 32 de biți, stânga și dreapta, care îl compun. Fie cheia care corespunde ciclului i un bloc cu lungimea de 48 de biți, aceștia fiind selectați din cei 64 de biți ai cheii. Prelucrările unei iterații sunt:
Li = Ri – 1
Ri = L i – 1 f(R i – 1, Ki)
unde reprezintă funcția XOR (sau exclusiv) a două secvențe binare, K1, K2, …, K16 sunt bucăți de 48 de biți calculate din cheia K prin procesul de planificare a cheii (key schedule), iar f este o funcție Feistel f(A,J) care are ca intrare două secvențe binare: o secvență cu lungimea de 32 de biți (ce va fi extinsă tot la 48 de biți folosind o funcție de expansiune E) și una de 48 de biți, și are ca rezultat o secvență cu lungimea de 32 de biți, care se obține prin descompunerea în subsecvențe cu lungime de 8 biți (s1, s2, …, s8) asupra cărora sunt aplicate anumite procese de permutare P.[3]
Figura 3.1 Schema generală a DES[11]
Cei 48 de biți ai cheii se obțin prin procedeul care urmează. Fiecare cheie, supusă unei permutări inițiale P1 este divizată în două blocuri de 28 de biți, Ci și Di, ce sunt deplasate la rândul lor cu una sau două poziții la fiecare ciclu. Numărul de deplasări depinde de numărul iterației la care se află ciclul.
P1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
Cheile sunt supuse din nou unei permutări P2.
P2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Funcția de cifrare f, realizează o substituție. Asupra blocului inițial de 32 de biți se aplică o funcție E care genereză 48 de biți la ieșire.
Figura 3.2 Prelucrarea biților în cele 8 cutii[12]
Apoi blocul de 48 de biți este însumat cu cei 48 de biți ai cheii . Ceea ce se obține este împărțit în 8 blocuri cu lungime de 6 biți ce reprezintă intrările a 8 cutii Si, i=1,8 care fac o substituție cu 6 intrări și 4 ieșiri. Dacă luăm cazul unei cutii Si, dacă B este blocul de 6 biți de la intrare, Si(B) este determinat în felul care urmează: Primul și ultimul bit din blocului B reprezintă în binar un număr care este cuprins între 0 și 3 (fie acest număr k). Cei 4 biți din mijlocul lui B reprezintă în binar un număr care este cuprins între 0 și 15 (fie acest număr l). În tabela Si, la intersecția dintre rândul k și coloana l există un număr cuprins între 0 și 15 și reprezentarea acestuia de 4 biți este cea care constituie ieșirea cutiei Si.
Figura 3.3 Cele 8 cutii[12]
Ieșirile cutiilor Si sunt prelucrate printr-o funcție de permutare, P, cu 32 de biți la intrare și 32 de ieșire.
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Blocul f(Ri-1, Ki) poate fi definit ca:
f(Ri-1, Ki)= P(S1(B1) S2(B2)…S8(B8))
După calculul complex alcătuit din cele 16 iterații descrise anterior, blocul de 32 de biți este supus unei perumtări inverse, inversa celei inițiale.
Procesul de decriptare se realizează în aceeași manieră, singura diferență fiind ca se inversează ordinea derivării cheilor, fiind folosite K16, K15, …, K1
În momentul de față, DES este privit ca un algoritm nesigur, cauza principală fiind faptul că mărimea de doar 56 de biți a cheii este considerată prea mică. În luna ianuarie a anului 1999, distributed.net și Fundația Frontiera Electronică (Electronic Frontier Foundation) au colaborat pentru a sparge o cheie DES în doar 22 de ore și 15 minute. În plus, și alte rezultate teoretice demonstrează slabiciunile cifrului, chiar dacă acestea sunt imposibil de pus în practică. Criptosistemul DES are o formă sigură aceasta este varianta Triplu-DES, deși au apărut atacuri teoretice și asupra acesteia.
Algoritmul Triplu-DES
Algoritmul Triplu-DES (Triple Data Encryption Algorithm – TDEA sau Triple DEA), cunoscut și sub numele de 3DES, DES-ede sau FIPS Pub 46-3 (denumirea sa oficială) este un sistem de cripatare derivat din DES și fiind propus este Walter Tuchman. Pentru fiecare bloc de date Triplu-DES aplică algoritmul DES de trei ori. În ultimele decenii prin intermediul creșterii puterii computaționale, dimensiunea mică a cheii DES a devenit ținta a numeroase atacuri de spargere prin forță brută, Triplu-DES a fost astfel construit pentru a oferi o metodă simplă pentru a crește mărimea cheii DES pentru ca aceasta să fie protejată împotriva atacurilor de acest tip, fără a creea un algoritm complet nou, ci doar prin modificarea celui existent.
Poate fi definit prin următoarele formule:
C = Ek3(Dk2(Ek1(M))) – criptare
D = Dk1(Ek2(Dk3(M))) – decriptare
unde:
– C – textul care a fost criptat
– D – textul care a fost decriptat
– M este un bloc de text clar (64 de biți)
– k1, k2, k3 sunt chei DES (56 de biți)
– Ek se referă la criptarea cu cheia k
– Dk se referă la decriptarea cu cheia k
Metoda mai este numită și DES-ede (encrypt – decrypt – encrypt). Mai puțin frecvent criptarea se face în lanț, și conține trei criptări DES, numită și DES-eee (encrypt – encrypt – encrypt), având următoarea formulă:
e = Ek3(Ek2(Ek1(m))) – criptare
d = Dk1(Dk2(Dk3(m))) – decriptare
Dacă privim cele trei de criptare folosite, există trei opțiuni în alegerea acestora:
1) toate cheile sunt independente una față de celalată
2) k1 și k2 sunt independente și k3 = k1
3) cele trei chei sunt identice, și k1 = k2 = k3
Opțiunea întâi este cea mai sigură, deoarece are 168 (3 × 56) biți de cheie independenți, opțiunea a doua nu are o siguranță la fel de mare ca prima opțiune, având doar 112 (2 × 56) biți de cheie, dar totuși este mai puternică decât o simplă criptare DES realizată de două ori cu k1 și k2, deoarece oferă protecție împotriva atacurilor de tip „întâlnire la mijloc” (meet in the middle). Ultima opțiune este echivalentă cu DES și oferă compatibilitate în sens invers cu acesta.
Pentru aceste cazuri , pentru DES-ede, operația care se află mijloc este inversul primei și ultimei. Astfel este sporită siguranța algoritmului atunci când se folosește opțiunea 2) pentru chei, iar sistemele DES și Triplu-DES pot inter-opera în cazul opțiunii 3). Așadar, prin aceste modificări simple, securitatea lui Triplu-DES este crescută considerabil față de cea a lui DES. Astfel, Triplu-DES nu s-a reușit încă să fie spart, dar dezavantajul lui este viteza mică de criptare.
3.1.1 Criptarea unui mesaj cu ajutorul DES
Dacă mesajul inițial este în sistem hexazecimal acesta devine în sistem binar
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Pasul 1. Crearea de 16 subchei, fiecare de dimensiune de 48 de biți
Cheia de 64 de biți este permutată conform următorului tabel, PC-1. Cum prima valoare din tabel este „57”, aceasta înseamnă că al 57-lea bit din cheia inițială Key devine primul bit din cheia permutată. Al 49-lea bit din cheia inițială devine al doilea bit din cheia permutată. Al 4-lea bit din cheia inițială este ultimul bit în cheia permutată. Se observă, că doar 56 de biți din cheia inițială apar în cheia permutată.
PC-1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
Exemplu: Din cheia originală de 64 de biți
obținem permutarea de 56 de biți.
După aceea, cheia este împărțită într-o jumătate dreaptă și stângă, C0 și D0, unde fiecare jumătate are 28 de biți.
Exemplu: Din cheia permutată, obținem:
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111
Cu C0 și D0 definite, creăm acum șaisprezece blocuri Cn and Dn, 1<=n<=16. Fiecare pereche de blocuri Cn și Dn este formată din perechile anterioare Cn-1 și Dn-1, respectiv, pentru n = 1, 2, …, 16, folosind următorul tabel de deplasări la stânga a biților din blocul anterior. Pentru a realiza o deplasare la stânga, mutăm fiecare bit cu o poziție spre stânga, cu excepția primului bit, care este mutat la sfârșitul blocului.
Numărul Numărul
iterației de deplasări
1 o deplasare
2 o deplasare
3 două deplasări
4 două deplasări
5 două deplasări
6 două deplasări
7 două deplasări
8 două deplasări
9 o deplasare
10 două deplasări
11 două deplasări
12 două deplasări
13 două deplasări
14 două deplasări
15 două deplasări
16 o deplasare
Aceasta înseamnă, de exemplu, C3 și D3 sunt obținute din C2 și D2, respective, prin două deplasări la stânga, și C16 și D16 sunt obținute din C15 și D15, respectiv, printr-o deplasare la stânga. În orice caz, printr-o singură deplasare la stânga se referă la o rotație a biților cu o poziție spre stânga, astfel încât după o singură deplasare la stânga biții din cele 28 de poziții sunt biții care erau înainte pe pozițiile 2, 3, …, 28, 1.
Exemplu: Din perechea inițială C0 și D0 obținem:
C0 = 1111000011001100101010101111
D0 = 0101010101100110011110001111
C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110
C2 = 1100001100110010101010111111
D2 = 0101010110011001111000111101
C3 = 0000110011001010101011111111
D3 = 0101011001100111100011110101
C4 = 0011001100101010101111111100
D4 = 0101100110011110101111010101
C5 = 1100110010101010111111110000
D5 = 0110011001111000111101010101
C6 = 0011001010111011111111000011
D6 = 1001100111100011110101010101
C7 = 1100101010101111111100001100
D7 = 0110011110001111010101011110
C8 = 0010101010111111110000110011
D8 = 1001111000111101010101011001
C9 = 0101010101111111100001100110
D9 = 0011110001111010101010110011
C10 = 0101010111101110000110011001
D10 = 1111000111101011101011001100
C11 = 0101011111111000011001100101
D11 = 1100011110101010101100110011
C12 = 0101101111100001100110010101
D12 = 0001111010101010111011001111
C13 = 0111111110000110011001010101
D13 = 0111101010101011001100111100
C14 = 1111111000011001100101110101
D14 = 1110101010101100110011010001
C15 = 1111100001100110010101010111
D15 = 1010101010110011001111000111
C16 = 1111000011001100101010101111
D16 = 0101010101100110111110001111
Acum formăm cheile Keyn, pentru 1<=n<=16, prin cu ajutorul următoarelor permutări pentru fiecare pereche concatenată CnDn. Fiecare pereche de chei are 56 de biți, dar PC-2 folosește doar 48 din aceștia.
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Așadar, al doilea bit al lui Keyn este al 17-lea bit al conactenării n, al optulea bit este al 28-lea.
Exemplu: Pentru prima cheie avem C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110
care, după ce aplicăm permutarea PC-2, devine
Key1 = 000110 110000 001011 101111 111111 000111 000001 1100
Pentru celelalte chei avem
Key2 = 011110 011010 111011 011001 110110 111100 100111 100101
Key3 = 010101 011111 110010 001010 010000 101100 111110 011001
Key4 = 011100 101010 110111 010110 110110 110011 010100 011101
Key5 = 011111 001110 110000 000111 111010 110101 001110 101000
Key6 = 011000 111010 010100 111110 010100 000111 101100 101111
Key7 = 111011 001000 010010 110111 111101 100001 100010 111100
Key8 = 111101 111000 101000 111010 110000 010011 101111 111011
Key9 = 111000 001101 101111 101011 111011 011110 011110 000001
Key10 = 101100 010111 001101 000111 101110 100100 011001 001111
Key11 = 001000 010101 111111 010011 11111 101101 001110 000110
Key12 = 011101 010111 000111 110101 100101 000110 011111 101001
Key13 = 100101 111100 010111 010001 111110 101111 101001 000001
Key14 = 010111 110100 001110 110111 111100 101100 011100 111010
Key15 = 101111 111001 000110 001101 001111 010011 111100 001010
Key16 = 110010 110011 110110 001011 000011 100001 011111 110101
Pasul 2. Criptarea blocurilor de 64 de biți
Există o permutare inițială IP a celor 64 de biți a mesajului M. Permutarea rearanjază biții după următorul tabel, unde numerele din tabel indică noul aranjament al biților față de ordinea lor inițială. Astfel al 34-lea bit al mesajului M devine al patrulea bit al permutării IP. Al 36-lea bit al mesajului M devine al doisprezcelea bit al IP. Al șaptelea bit devine ultimul bit al IP.
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Exemplu: Aplicând permutarea inițială blocului de text M, obținem
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
Aici al 58-lea bit din mesajul M este 1, care devine al primul bit. Al 50-lea bit din mesajul M este 1 care devine al doilea bit din IP. Al 7-lea bit este 0 care devine ultimul bit din IP.
Apoi blocul permutat IP îl împărțim într-o jumătate stângă L0 de 32 de biți, și o jumătate dreaptă R0 de 32 de biți.
Exemplu: Din IP, obținem L0 și R0.
L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
Acum vor fi făcute cele 16 iterații pentru 1<=n<=16, folosind o funcție f care lucrează cu două blocuri – un bloc de date de 32 de biți și cheia Keyn de 48 de biți – pentru a produce un bloc de 32 de biți. Fie adunarea XoR (adunare bit cu bit modulo 2). Apoi pentru n de la 1 la 16 calculăm
Ln = Rn-1
Rn = Ln-1 f(Rn-1,Keyn)
Rezultatul este un bloc final, pentru n = 16,de L16R16. Așadar, cu fiecare iterație, luăm cei 32 de biți din dreapta de la rezultatul precedent pentru a-i face cei 32 de biți din stânga de la pasul curent. Pentru cei 32 de biți din dreapta de la pasul curent, operația XoR va fi aplicată celor 32 de biți din stânga de la pasul precedent și rezultatului obținut în urma aplicării funcției f .
Exemplu: Pentru n = 1, avem
Key1 = 000110 110000 001011 101111 111111 000111 000001 110010
L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010
R1 = L0 f(R0,Key1)
Rămâne să explicăm cum lucrează funcția f . Ca să calculăm f , lărgim fiecare bloc Rn-1 de la 32 la 48 de biți. Aceasta se face prin utilizarea unui tablou de selecție care repeată unii din biții din Rn-1 . Vom numi acest tablou de selecție funcția E. Așadar E(Rn-1) are un bloc de intrare de 32 de biți, și un bloc de ieșire de 48 de biți.
Fie E astfel încât cei 48 de biți de ieșire, scriși ca 8 blocuri de 6 biți fiecare, sunt obținuți selectând biții de intrare în ordine conform următorului tablou:
TABELUL DE SELECȚIE A LUI E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Așadar primii trei biți ai lui E(Rn-1) sunt biții din pozițiile 32, 1 și 2 ai lui Rn-1 în timp ce ultimii 2 biți ai lui E(Rn-1) sunt biții din pozițiile 32 și 1.
Exemplu: Calculăm E(R0) din R0 după cum urmează:
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
(obsevăm că fiecare bloc de 4 biți inițiali a fost lărgit la un bloc de 6 biși de ieșire). Apoi în calcularea lui f , aplicăm XoR ieșirii E(Rn-1) cu cheia Keyn:
Keyn + E(Rn-1).
Exemplu: Pentru K1, E(R0) avem
Key1 = 000110 110000 001011 101111 110111 000111 000001 110010
E(R0) = 011110 100001 010101 010101 011110 110001 010101 010101
Key1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111.
Nu am terminat încă de calculate funcția f . Până la acest punct am expandat Rn-1 de la 32 de biși la 48 de biți, folosind tabloul de selecție, și aplicăm XoR rezultatului cu cheia Keyn . Acum există 48 de biți, sau 8 grupuri de 6 biți. Fiecarre grup de șase biți va trece prin ceva interesant: îi folosim ca adrese în tablouri numite "cutii S ". Fiecare din grupurile de șase biți ne oferă o adresă într-o cutie S diferită . La adreasa obținută va fi localizat un număr pe 4 biți. Acest număr pe 4 biți va avea rolul de a înlocui cei 6 biți inițiali. Așadar în final opt grupuri de 6 biți sunt transformate în opt grupuri de 4 biți ( ieșirile de 4 biți din cutiile S) pentru 32 de biți.
Rezultatul anterior, care are 48 de biți, în scriem sub forma:
Keyn + E(Rn-1) =B1B2B3B4B5B6B7B8,
unde fiecare Bi este un grup de 6 biți. Acum calculăm
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
unde Si(Bi) se referă la ieșirea cutiei S i.
Să repetăm, fiecare din funcțiile S1, S2,…, S8, ia un bloc de 6 biți ca intrare și întoarce un bloc de 4 biți ca ieșire. Tabloul pentru a determina S1 este arătat și explicat mai jos:
S1
Număril coloanei
Nr
Rând 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Dacă S1 este funcția definită în acest tabel și B este un bloc de 6 biți, atunci S1(B) este determinatîn felul următor : Primul și ultimul bit al lui B reprezintă în baza 2 un număr zecimal în intervalul de la 0 la 3(sau binarde la 00 la11). Fie acel număr i. Cei 4 biți din mijloc ai lui B reprezintă în baza 2 un număr zecimal din intervalul de la 0 la 15 (binar între 0000 și 1111). Fie acel număr j. În tabel ne uităm la numărul de pe rândul i și coloana j. Acesata este un număr cuprins între 0 și 15 și este unic reprezentat de un bloc de 4 biți. Blocul respectiv este ieșirea S1(B) a lui S1 pentru intrarea B. De exemplu pentru un bloc de intrare B = 011011 primul bit este 0 și ultimul 1 dând 01 ca rând. Acesta este rândul 1. Cei 4 biți din mijloc sunt 1101. Acesta este echivalentul binary al lui 13 zecimal, deci coloana este coloana numărul 13. Pe rândul 1 coloana 13 este 5. Aceasta determină ieșirea; 5 este binar 0101, deci ieșirea este 0101. Așadar S1(011011) = 0101.
Tablourile care definesc funcțiile S1,…,S8 sunt următoarele:
Figura3.4 Cele 8 cutii [12]
Exemplu: Pentru prima rundă obținem ieșir ea celor opt cutii:
Key1 + E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111.
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111
Ultimul pas în calcularea lui f este să facem o permutare P a ieșirilor cutiilor S ca să obținem valoarea finală a lui f:
f = P(S1(B1)S2(B2)…S8(B8))
Permutarea P este definite în următorul tabel.
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Exemplu: Din ieșirea celor 8 cutii:
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111
obținem
f = 0010 0011 0100 1010 1010 1001 1011 1011
R1 = L0 + f(R0 , Key1 )
= 1100 1100 1000 0000 0100 1100 1111 1111
+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 1100 1010 0110 0101 0100 0100
În următoarea rundă, avem L2 = R1,care este blocul pe care tocmai l-am calculate, și apoi trebuie să calculăm R2 =L1 + f(R1, Key2), și așa mai departe timp de 16 runde. La sfârșitul celei de-a 16-a runde avem blocurile L16 și R16. Apoi inversăm ordinea celor două blocuri în blocul de 64 de biți R16L16 și aplicăm o permutare finală IP-1 definită de tabelul următor:
IP-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
Astfel, ieșirea algoritmului are bitul 40 al blocului dinaintea ieșirii ca primul bit, bitul 8 ca al doilea bit.
Exemplu: Dacă procesăm toate cele 16 blocuri folosind metoda definită anterior, obținem a 16-a rundă
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1000 0100 1100 1101 1001 1001 0111
Inversăm ordinea acestro două blocuri și aplicăm permutarea finală la
R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100
IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101
care în formă hexadecimală este
85E813540F0AB405.
Aceasta este forma criptată a lui
M = 0123456789ABCDEF
mesajul cifrat
C = 85E813540F0AB405.
3.1.2 Securitatea DES
Rețeaua DES este una de tip Feistel cu 16 runde și lungimea cheii este de 56 de biți. Procesul de derivare a cheii (Key schedule) obține o sub-cheie de rundă pentru fiecare rundă pornind de la cheia master k. Funcțiile de rundă sunt derivate din aceeași funcție principală f și nu sunt inversabile.
SBOX-urile din DES
Formează o componentă esențială din construcția DES. Dacă SBOX-urile sunt modificate ușor sau dacă sunt alese aleator atunci DES devine mult mai vulnerabil la atacuri. Dacă se modifică unui bit de la intrare întotdeauna vor fi afectați cel puțin doi biți de la ieșire. DES are un puternic efect de avalanșă generat de propietatea menționată mai sus și de permutările folosite.
Pentru a demonstra aceasta, analizăm diferența între valorile intermediare dintr-un calcul DES a două valori de intrare care sunt printr-un singur bit.
Notăm cele două valori cu () și unde .
În urma primei runde, valorile ) și sunt încă diferă printr-un singur bit, dar acum diferența e în dreapta; În runda a doua DES, și trec prin funcția f.
Dacă presupunem că bitul în care și diferă nu este duplicat în pasul de expandare, ele încă diferă printr-un bit înaintea de aplicarea SBOX-ului. După SBOX acestea sunt diferite în cel puțin doi biți.
() și diferă în trei biți: 1-bit diferență între și și 2-biți diferență între și . Prin permutarea din f biții dintre și sunt împrăștiați în diferite regiuni ale lor. Fiecare bit care diferă va fi utilizat la runda urmatoare ca intrare într-un SBOX diferit, astfel apare o diferență de 4 biți între jumătățile din dreapta ale valorilor intermediare.[6]
Efectul este unul exponențial și după 7 runde toți cei 32 de biți vor fi modificați.
După ce sunt aplicate 8 rude toți biții din jumătatea stângă vor fi modificați .
Sistemul de criptare DES are 16 runde deci efectul de avalanșă este atins foarte repede.
Deci dacă criptosistemul DES este aplicat asupra a două intrări identice acesta întoarce ieșiri diferite și independente. Efectul se datorează și permutărilor ce sunt alese cu grijă (se cunoaște faptul că permutări aleatorare nu oferă același efect puternic de avalanșă).
Atacuri DES cu număr redus de runde
Putem înțelege securitatea DES dacă studiem mai întâi modul în care DES se comportă pe un număr redus de runde (maxim 3).
Sigur, DES cu 3 runde nu este o funcție psudoaleatoare deoarece efectul de avalanșă nu este încă este complet.
Vom arăta câteva atacuri cu text clar care găsesc cheia .
Adversarul are așadar acces la perechi de forma cu
În descrierea atacurilor, ne vom concentra asupra unei singure perechi (x, y).
Cunoștem și unde
De asemenea
Dacă aplicăm obținem o valoare intermediară care reprezintă ieșirea celor 8 SBOX-uri.
Intrarea în SBOX-uri este ; este cunoscut, la fel ieșirea din SBOX-uri.
Pentru fiecare ieșire din SBOX, există 4 valori posibile ale porțiunii corespunzătoare din 6 biți din cheia care ar conduce la acea valoare.[6]
Am redus numărul cheilor posibile de la la .
Acum se pot verifica pe rând toate variantele și recupera complet cheia.
Atacul DES cu două runde
Acest atac găsește cheile și în timp atunci când se cunoaște o pereche text clar/ test criptat.
Încă de la propunerea sa, DES a fost criticat din două motive:
Spațiul cheilor este unprea mic criptosistemul devenind astfel vulnerabil la forța bruta.
Au fost ținute secrete criteriile de selecție a SBOX-urilor și ar fi putut apărea atacuri analitice care să exploreze proprietățile matematice ale SBOX-urilor, cunoscute numai celor ca l-au proiectat. Cu toate acestea după 30 ani, cel mai bun atac practic rămâne o căutare exhaustivă pe spațiul cheilor.
O problemă cu importanțămai scăzută a sistemului DES, este lungimea blocului relative scurtă (64 biți). Dacă un atactor deține perechi text clar/ text criptate, securitatea criptosistemului va fi compromisă aproape sigur.
În concluzie, putem spune că insecuritatea sistemului DES nu este dată de structura sa sau construcția sa, ci este cauzată numai de lungimea cheii prea mică.
La începutul anilor '90, Matsui a dezvoltat criptanaliza liniară aceasta fiind aplicată cu succes pe DES. Deși necesită texte criptate, avantajul ei este că textele clare nu trebuie să fie alese de atacator, ci doar cunoscute de el; Problema însă rămâne aceeași: atacul este foarte greu de pus în practică.
Criptanaliza liniară
Metoda consideră relațiile liniare între intrările și ieșirile unui cifru bloc. Spunem că biții , … , și , … , au distanța dacă pentru orice intrare aleatoare x și orice cheie
unde
.
Pentru o funcție aleatoare sa așteaptă ca p=0.5
Matsui a arătat cum se poate folosi o diferență mare pentru a sparge complet un cifru bloc.
Sunt necesare un număr foarte mare de perechi text clar/ text criptat.
Criptarea dublă
Fie P un cifru bloc (în particular ne vom referi la DES); definim un alt cifru bloc astfel
cu , chei independente.
Lungimea totală a cheii este de 112 biți. Suficient de mare pentru căutare exhaiustivă.
Însă se poate face un atac în timp unde = 56 = ( față de cât necesită o căutare exhaustivă)
Atacul se numește meet-in-the middle.
Atacul funcționează în următorul mod dacă se cunoaște o pereche text clar/ text criptat (x,y) cu :
Pentru fiecare , calculează z= și păstrează
Pentru fiecare , calculează și păstrează
Verifică dacă există perechi și care coincid pe prima componentă.
Atunci valorile , corespunzătoare satisfac
adică
Criptarea triplă
Există două variante:
Trei chei de criptare independente – și iar
Două chei independente – și iar
este ales astfel încât pentru a fi compatibil cu P atunci când cheile sunt alese ==
Prima variantă are lungimea cheii de 3n dar cel mai bun atac necesită timp (funcționează atacul meet – in – the – middle)
A doua variantă are lungimea cheii 2n și cel mai bun atac necesită .
3.2. Criptosistemul AES
În criptografie, AES face referire la Standardul de Criptare Avansata (Advanced Encryption Standard), o modalitate de criptare simetrică care a fost adoptată de guvernul Statelor Unite. Criptosistemul este format din trei cifruri bloc: AES-128, AES-192 și AES-256, acestea fiind alese dintr-o colecție mai mare de cifruri, cunoscută la început cu numele de Rijndael. Această denumire provine de la numele inventatorilor sistemului de criptare, criptografii de origine belgiană Joan Daemen și Vincent Rijmen, cei care au înscris cifrul Rijandel în procesul de selecți al AES, el fiind considerat algoritmul cel mai adecvat. Toate cele trei cifruri din AES lucrează cu blocuri cu lungimea de 128 de biți, ceea ce diferă între ele fiind dimensiunile cheilor, de 128 de biți, respectiv 192 și 256. După o analiză minuțioasă, au ajuns să fie utilizate la nivel mondial.
Organizația care l-a anunțat oficial a fost NIST (National Institute of Standards and Technology – Institutul Național al Standardelor și Tehnologiilor) pe data de 26 noiembrie 2011, în urma unui proces de standardizare care a avut durata de 5 ani și în care au fost prezentate și evaluate 15 alte modalități de criptare până când Rijndael a fost ales . Pe data de 26 mai 2002 criptosistemul a fost declarat ca fiind standard guvernamental și este primul sistem de criptare la care publicul are acces ce a primit aprobarea NSA (National Security Agency – Agenția Naționala pentru Securitate a S.U.A.) pentru a fi criptate informațiile cu caracter secret.
AES are la bază un principiu numit rețeaua de subsituire și permutare și implementarea lui se face rapid atât software, cât și hardware. Operează pe o matrice de biți de 4×4, denumită stare (state), cele mai multe calcule din AES realizându-se pe un câmp finit special.
Cifrul are proprietatea că e un număr de repetiții de runde de transformare care convertesc textul clar dat ca input în output-ul final al textului ce se dorește cifrat. Fiecare rundă este alcătuită din câțiva pași specifici de procesare, dintre care unul este dependent de cheia de criptare. Starea este modificată pe parcursul rundelor prin 4 tipuri de operații:AddRoundKey, SubBytes, ShiftRows, Mixcolumns.
Prin operația AddRoundKey fiecare bit din stare este făcut XoR cu cheia de rundă. Prin operația SubBytes fiecare octet este înlocuit de un alt octet confrom tabelei de substituție. operația ShiftRows
este un pas de transpoziție în care fiecare rând din stare este deplasat ciclic un anumit număr de pași. operația MixColumns amestecă coloanele stări, combinând cei patru biți din fiecare coloană
Pentru ca textul cifrat să fie transformat înapoi în textul original se folosesc rundele inversate și aceeași cheie de criptare.Dacă AES are numărul complet de runde căutarea exhaustivă este singurul atac eficient, nu se cunoaște niciun alt atac eficient
Capitolul IV
Criptosisteme cu chei publice
4.1.Sistemul de criptare RSA
Sistemul de criptare RSA (Rivest – Shamir – Adleman) este în momentul actual cel mai cunoscut și mai utilizat sistem de criptare cu cheie publică. Modului foarte simplu de criptare și decriptare i se datorează în primul rând acest lucru, care se realizază similar- cu aceleași module de calcul ( proprietate întâlnită în special la multe sisteme simetrice).
Criptosistemul RSA utilizează rezultatele obținute din teoria numerelor, combinate cu dificultatea de a determina factorilor primi pentru un număr țintă. Sistemul de criptare RSA operează cu aritmetica modulo . Blocul de text în clar este tratat ca un întreg, iar pentru a cripta și decripta mesajul se folosesc două chei, și , acestea fiind interschimbabile. Blocul de text clar este criptat ca . Deoarece exponențierea este modulo , factorizarea lui este devine foarte dificilă cu scopul de a descoperi textul original. Pentru a realiza acest lucru, cheia de decriptare este aleasă încât
Astfel M este regăsit fără să trebuiască ca să fie descompus în factori primi.
Factorizarea întregilor mari este problema pe care se bazează algoritmul de criptare. Problema factorizării nu se cunoaște a fi NP-completă; algoritmul cel mai rapid care se cunoaște este exponențial în timp.
Prin intermediul algoritmului RSA mesajul în text clar este criptat folosind chei de criptare obținându-se mesajul în text cifrat
Regăsirea mesajului în text clar se face cu ajutorul cheii de criptare :
.
Din cauza simetriei din aritmetica modulară, criptarea și decriptarea sunt mutual inverse și comutative:
Perechea de întregi este cheia de criptare iar cheia de decriptare este . Alegerea unei valori pentru este punctul de plecare în a găsi cheile. Valoarea lui trebuie să fie una suficient de mare, aceasta fiind exprimată ca produsul a două numere prime și . Numerele și trebuie să fie la rândul lor suficient de mari. În mod uzual, și au aproximativ 100 de cifre fiecare, astfel încât are aproximativ 200 de cifre. Această lungime descurajează încercarea de a factoriza pe , pentru a afla pe și pe .
În continuare, este ales un număr întreg relativ mare, în așa fel încât este relativ prim cu . Acestei condiții este satisfăcută dacă se alege ca un număr prim care este mai mare ca și . În final, se alege astfel încât:
Funcția lui Euler este numărul de întregi pozitivi mai mici decât care sunt relativi primi cu . Dacă este prim, atunci:
.
Dacă , unde și sunt ambele numere prime, atunci
Identitatea Euler-Fermat afirmă că
pentru orice întreg , dacă și sunt reciproc prime.
Să presupunem că mesajul în text clar este criptat de algoritmul RSA, astfel încât . Decriparea mesajului trebuie să fie posibilă. Valoarea este astfel aleasă încât inversa ei să poată fi găsită ușor.
Deoarece și sunt inverse modulo , sau pentru anumiți întregi k.
Pentru a implementa practic algoritmul, utilizatorul acestuia alege numerele prime și , din care obține . Apoi alege , relativ prim la , de obicei un număr prim mai mare decât . În final, se calculează ca inversul lui mod . Utilizatorul distribuie și , și păstrează cheia secretă; ,, și pot fi ignorate, dar nu făcute publice.
Generarea cheilor
Se aleg două numere întregi prime și
Se calculează produsul
Se calculează indicatorul lui Euler
Se calculează un număr întreg astfel încât c.m.m.d.c ,
Se calculează astfel încât
Cheia publică este , iar cheia privată este
Algoritmul de criptare
Presupunem că un utilizator A are cheia publică și cheia privată . Utilizatorul B criptează mesajul M pentru a fi transmis la A astfel:
obține cheia publică a lui A
Transformă mesajul ce va fi criptat într-un număr întreg M în intervalul [0, n-1]
Calculează
Trimite textul cifrat C la utilizatorul A [4]
Exemplu:
Se selectează două numere prime și
Se calculează
Se calculează
Se calculează astfel încât este relativ prim cu . În acest caz
Se determină astfel încât și . Avem deoarece
Cheia publică este (5, 119), iar cheia privată este 77.
Se consideră că textul clar este M=19. Textul criptat va fi
Rezultă . Pentru decriptare se calculează
4.1.1. Securitatea criptosistemului RSA
Singura modalitate care se cunoaște pentru a sparge complet sistemul RSA este factorizarea modulului.
S-a demonstart că pentru a calcularea perechii de chei RSA(cheie publică și cheie privată) este echivalent cu problema factorizării întregilor. În acest sens următoarele două relații sunt valide cu privire la securitatea RSA-ului:
Prima relație ilustrează faptul că decriptarea RSA se reduce polinomial la factorizare ( desemnată ca PFI de la Problema Factorizării Întregilor) și este evidentă, calculul cheii de decriptare RSA realizându-se cu ajutorul factorilor modulului. [2]
Cea de-a doua relație ilustreză faptul că a calcula o pereche de chei RSA este o problemă echivalentă cu factorizarea și poate fi demonstrată după cum cum urmează. Dacă factorizăm modulul va putea fi calculată perechea de chei, rămâne deci să arătăm doar că o pereche de chei poate fi folosită pentru a factoriza modulul. Presupunem că se cunosc și astfel încât și dorim aflarea lui și . Enumerăm două metode folosite pentru a face ascet lucru:
Se observă că deoarece discutăm în contextul criptografiei cu cheie publică și numărul are o mărime foarte mare raportat la ceilalți membrii ai ecuației în mod cert vom avea
. Folosind această valoare pentru k avem . Din moment atât suma cât și produsul sunt cunoscute , care este chiar valoare lui , putem extrage cele două numere ca rădăcini ale unei ecuații de grad 2.[2]
ii) Se observă de asemenea că pentru avem și prin împărțire succesivă a exponentului la 2 vom ajunge la un moment dat la în timp ce care implică ceea ce înseamnă că membrii produsului din partea stângă a ecuației ascund factori distincți ai lui și aceștia pot fi extrași ușor cu metode de calcul al celui mai mare divizor comun.[2]
Fără îndoială dintre criptosistemele cu cheie publică RSA este cel mai intens studiat. Astfel, de-a lungul timpului au fost identificate mai multe atacuri și vulnerabilități ale RSA. Importante sunt în primul rând atacurile pasive, sursa lor fiind un adversar care încearcă off-line să spargă criptosistemul, dintre acesteaamintim:
– Atacul prin factorizare presupune factorizarea întregului – cu ajutorul algoritmilor cunoscuți. În prezent nu este posibil acest lucru pentru valori mari ale lui
– Atacul prin căutarea directă a mesajului (forward-search) este un atac general, atacul putând fi aplicat asupra oricărui sistem de criptare cu cheie publică. Deoarece cheia publică este prin definiție publică pentru adversar, având un criptotext capturat, acesta poate face o căutare exhaustivă în cazul în care spațiul mesajului este redus.
În al doilea rând și mult mai periculoase sunt atacurile active pentru cazul în care un adversar are acces la mașina de decriptare ( fiind criptate cu cheie publică accesul la mașina de criptare este evident). Dintre acestea amintim:
– Atacul prin temporizare. În mod cert cantitatea de timp care este necesară pentru decriptare poate conduce la informații suplimentare despre exponentul utilizat.
-Adaptive chosen chipertext – attack
Anumite vulnerabilități ale lui RSA sunt foarte cunoscute și care trebuie amintite.
– Exponenții de criptare sau decriptare relativ mici. Atacul asupra unui exponent mic de criptare presupune existența unei relații între mesajele criptate și poate fi prevenit dacă mesajul este extins cu biți aleatori. În practică trebuie evitați exponenții mici de criptare (evitarea decurge în mod natural deoarece în practică se utilizează exponenți de criptare mici sau cu forme speciale și aceștia fac ca exponenții de decriptare să fie mari).
– Problema modului comun. Utilizarea aceluiași modul de către mai mulți participanți nu este posibilă deoarece dacă se cunoaște o pereche cheie publică-privată duce automat la factorizarea modului și pierderea securității între participanți.
-RSA balansat și RSA nebalansat. Varianta de RSA în care cele două numere prime sunt alese ca având aceeași dimensiune poartă numele de RSA balansat și este varianta ce este recomandată și utilizată în practică. Shamir a propus și utilizarea unei variante de RSA numite RSA nebalansat împotriva factorizării și are aceeași viteză de criptare/ decriptare. Aceasta presupune utilizarea unui număr relativ mic (câteva sute de biți) și a unui număr prim relativ mare (câteva mii de biți) iar după aceea decriptarea se va face modulo pentru a câștiga timp. Schema aceasta are totuși un dezavantaj major – nu rezistă în fața unui atac de tip criptotext ales. Explicația este următoarea: presupunem că un adversar criptează un mesaj iar valoarea criptată este dacă mașina de criptare oferă ca răspuns și totodată deci
Și nu în ultimul rând câteva proprietăți ale criptosistemului RSA este bine să fie menționate cu specificația că acestea s-au dovedit de-a lungul timpului a fi pe de o parte avantajoase pentru că au permis dezvoltarea unor soluții de securitate noi și pe de altă parte dezavantajoase deoarece au dus la producerea unor noi atacuri asupra criptosistemului .
– Ciclicitatea criptării. Funcțiile definite pe mulțimi finite conduc la cicluri dacă acestea se compun succesiv. Astfel dacă există un mesaj criptat și continuăm să îl criptăm de un anumit număr de ori vom ajunge după runde să obținem . Acest atac devine în cele din urmă o modalitate de factorizare. Cum factorizarea nu este fezabilă, ciclicitatea criptării nu reprezintă un dezavanataj în practică.
-Criptarea identică se poate observa că sunt și mesaje care în urma criptării rămân neschimbate. Aceste mesaje sunt numerele acelea care satisfac ecuația . Se poate determina numărul exact de mesaje care satisfac această condiție. În ecuația are exact c.m.m.d.c(e-1, q-1) rădăcini. Analog există (e-1, q-1) soluții ale ecuației , va rezulta astfel că în există c.m.m.d.c(e-1,p-1) c.m.m.d.c(e-1, q-1) soluții. Numărul de mesaje care verifică această ecuație este deci redus și securitatea schemei de criptare RSA nu poate fi afectată.
-Proprietatea multiplicativă constă în faptul că pentru două mesaje și avem . Proprietatea aceasta a condus la multe construcții interesante bazate pe criptosistemul RSA dar din nefericire a dus și la atacul de tip criptotext.
4.2. Prezumții criptografice dificile
Construcțiile din criptografia cu cheie asimetrică se bazează pe probleme matematice ce sunt dificile din teoria numerelor.
Una dintre problemele considerate ca fiind dificile o reprezintă problema factorizării numerelor întregi sau mai simplu problema factorizării. Fiind dat un număr compus , problema cere să se găsească două numere prime și pe biți așa încât . Numerele acelea care au factori primi foarte mari sunt cel mai dificil de factorizat.
Pentru ca această problemă să fie folosită în criptografie, trebuie să generăm numere prime aleatorare în mod eficient.
Un număr prim poate fi generat în mod aleator pe n biți prin alegerea repetată de numere aleatoare pe n biți până când găsim unul prim.
Pentru eficiență, ne interesează două aspecte: probabilitatea ca un număr aleator de n biți să fie prim, cum testăm în mod eficient că un număr dat p este număr prim.
Pentru distribuția numerelor prime, se cunoaște următorul rezultat matematic:
Teoremă
Există o constantă c așa încât, pentru orice n>1 numărul de numere prime pe n biți este cel puțin .
Rezultă imediat că probabilitatea ca un număr ales aleator pe n biți să fie prim este cel puțin
Iar dacă testăm numere, probabilitatea ca un număr prim să nu fie ales este , adică cel mult , deci neglijabilă.[6]
Testarea primalității
Algoritmii cu eficiența cea mai mare sunt cei probabiliști. În cazul acestor algoritmi dacă p este prim algoritmul întoarce întotdeauna rezultatul prim. Dacă p este compus, atunci cu probabilitate mare algoritmul va returna compus.
Un algoritm probabilist foarte răspândit este algoritmul Miller-Rabin.
1. Se descompune unde m este impar;
2. Se alege aleator întregul ;
3.
4.
5.
6.
7. [1]
Algoritmul Miller-Rabin acceptă la intrare un număr N și un parametru t care determină probabilitatea de eroare. Algoritmul satisface:
Teoremă
Dacă N este prim, atunci testul Miller-Rabin întoarce mereu "prim". Dacă N este compus, alogoitmul întoarce "prim" cu probabilitate cel mult (i.e. întoarce rezulatul corect "compus" cu probabilitate 1-).
Încă nu se cunosc algoritmi polinomiali pentru a rezolva problema factorizării, însă exisă algoritmi mult mai buni decât forța brută.[6]
Deoarece orice implementare a unui sistem RSA trebuie însoțită de un generator de numere prime mari, sunt necesare construcții care să genereze rapid astfel de numere. Schneier propune următoarea variantă.
1. Se genereză un număr aleator p de n biți.
2. Se verifică dacă primul și ultimul bit sunt 1
3. Se verifică dacă p nu este devizibil cu nu numere prime mici (3, 5, 7, 11, …)
4. Se aplică testul Miller – Rabin cu o valoare aleatoare a. Dacă p trece testul, se ia altă valoare pentru a. Cinci teste sunt suficiente. Pentru viteză, se recomandă să se ia valori mici pentru a. Dacă p eșuează la unul din cele cinci teste, se reia algoritmul.
Calculul logaritmului discret
Algoritmul Shanks
Fie . Algoritmul Shanks este:
1. Se construiește lista ;
2. Se construiește lista =;
3. Se determină perechile , (identice pe a doua poziție)
4. Se definește [1]
Fie p=809 și să determinăm . Avem deci , iar
Lista a perechilor , este:
(5, 329) (6, 211) (7, 664) (8, 207) (9, 268)
………
…………………………………………………………………………………………………………………
(25, 586) (26, 575) (27, 295) (28, 81)
Lista a cuplurilor este:
………………………………………………………………………………………..
…………………………………………………………………………………………
…………………………………………………………..(18, 314) (19, 644)
(25, 356) (26, 658) (27, 489) (28, 163)
Parcurgând (eventual simultan) cele două liste se găsește , .
Se poate scrie deci
Se verifică ușor că .
Algoritmul Pohlig – Hellman
Mai întâi un rezultat matematic.
Lema
Fie un element primitiv. Atunci
Formal algoritmul Pohling – Hellman este următorul:
1. Se calculează
2.
3. for
3.1.
3.2. Se caută astfel ca
3.3.
3.4. [1]
3. Algoritmul Pollard-Rho
Fie p un număr prim și un element de ordin n. Vom considera subgrupul ciclic generat de . Ne punem problema căutării lui , unde este arbitrar.
Fie o partiție a lui în mulțimi de cardinale aproximativ egale; considerăm funcția
definită prin
Pe baza acestei funcții vom genera recursiv triplete cu proprietatea . Fie (1, 0, 0) tripletul inițial (el are această proprietate). În continuare:
În continuare se compară tripletele ( și până se găsește o valoare a lui pentru care . În acel moment:
Notăm relația poate fi rescrisă
Cum are ordinul , rezultă
sau
Dacă , atunci se poate obține :
4. Metoda de calcul a indicelui
Această metodă se aseamănă cu unul dintre cei mai buni algoritmi de descopmunere în factori.
Se folosește o bază de divizori compusă din G numere prime „mici”. Prima etapă este aceea a afșării logaritmilor elementelor din baza .
În a doua etapă, folosind acești logaritmi, se va determina logaritmul discret al lui lui .
I. Se construiesc F=G+10 congruențe modulo de forma
Cu aceste F ecuații de necunosscute se înceracă aflarea unei soluții unice modulo (p-1). În caz de reușită, primul pas este încheiat.
Problema ar fi cum să se găsească aceste F congruențe. o metodă elementară constă din 3 pași: alegerea aleatoare a lui , calculul lui și verificarea dacă acest număr are toți divizorii în .
II. Acum se poate determina cu un algoritm de tip Las Vegas. Se alege aleator un număr întreg și se determină .
Se încearcă apoi descompunerea lui în baza G. Dacă acest lucru este posibil, se obține o relație de forma
care poate fi transformată în
[1]
De aici – prin evaluarea membrului drept, se poate determina .
4.3.Sistemul de criptare EL Gamal
Sistemul de criptare El Gamal, se bazează pe problema logaritmului discret, care este următoarea:
Fie număr prim și . Să se determine astfel ca
.
Acest întreg – dacă există – este unic și se notează
În cele de mai jos presupunem că este un număr prim, iar este o rădăcină primitivă de ordinul p-1 a unității.
Sistemul de criptare El gamal este următorul:
Fie acel număr prim pentru care problema logaritmului discret este dificilă, și primitiv.
Generarea cheilor
Fiecare entitate generează o cheie publică și o cheie privată corespunzătoare.
Prima entitate execută următoarele:
Generează un număr prim mare p și un generator al grupului multiplicativ .
Selectează un număr întreg b, și calculează .
Cheia publică a lui A este tripletul ), iar cheia privată a lui A este b.
Algoritmul de criptare
Utilizatorul B criptează un mesaj m și-l trimite utilizatorului A:
Obține cheia publică ) a lui A.
Reprezintă mesajul de criptat într-un număr întreg m din intervalul [0, p-1].
Selectează aleator un număr întreg k, .
Calculează și
Trimite textul cifrat la utilizatorul A[4]
Exemplu
Să alegem Prin calcul se obține
Să presupunem că Sally vrea să transmită mesajul . Ea alege aleator și calculează
, apoi .)
Când Sam primește mesajul , el va determina
4.3.1 Securitatea sistemului ElGamal
Definim sistemul ElGamal pe baza ideii prezentate anterior;
1. Se generează , se alege și se calculează
Cheia publică va fi
Cheia privată va fi
2. Criptarea: dată o cheie publică și un mesaj , și întoarce =);
Decriptarea: dată o cheie secretă și un mesaj criptat , întoarce
Sistemul ElGamal nu este determinst, datorită alegerii aleatoare a lui la fiecare criptare.
Un același mesaj m se poate cripta diferit, pentru .
=);
=);
În caz contrar sistemul nu ar putea fi CPA sigur.
Sistemul ElGamal nu rămâne sigur dacă problema logaritmlui discret este simplă.
Se determină a.î. , apoi se decriptează orice mesaj pentru că se cunoaște cheia secretă.
Proprietatea de homomorfism
Fie texte clare și , textele criptate corespunzătoare:
Atunci
Dacă un adersar cunoaște , criptările lui , atunci el poate determina că
Un sistem de criptare care satisface
se numește sistem de criptare homomorfic.[6]
Este comun în practică pentru un administraror să fixeze parametrii publici , apoi fiecrae utilizator să îți genereze doar cheia secretă ți să publice
4.4..Sisteme asimetrice bazate pe curbe eliptice
În categoria sistemelor de criptare ale acestui mileniu se pot încadra cu certitudine sistemele bazate pe curbe eliptice. Aceste sisteme de criptare su proprietatea unei productivități înalte și permit folosirea cheilor cu dimensiune semnificativ mai mică păstrând nivelul de securitate.
Pentru anumite implementări sunt utilizate curbe eliptice de două tipuri:
Curbă eliptică peste un câmp finit , unde este un număr prim,
Curbă eliptică peste un câmp finit
Curbele eliptice sunt un domeniu al matematicii cu o istorie ce se întinde pe parcursul unui secol. În criptografie curbele eliptice au fost propuse pentru prima dată în 1985 de Victor Miller cercetător de la IBM și, independent, de Neal Kobitz, profesor la Universitatea din Washinghton. Ideea de bază a fost utilizarea grupului punctelor de pe o curbă eliptică din sistemele criptografice existente.
Anii ’90 au fost importanți pentru acest tip de criptosisteme, deoarece ele au început să cunoască acceptarea comercială odată cu standardizarea unor algoritmi și protocoale bazate pe curbe eliptice.
Eficiența curbelor eliptice ține de un avantaj pe care îl au acestea față de alte criptosisteme.
Securitatea acestor criptosisteme constă în calcularea logaritmului discret: date fiind (un element dintr-un câmp finit) și , este practic imposibil să se calculeze , atunci când numerele sunt suficient de mari.
Definiție: Fie un număr prim. Curba eliptică peste constă din mulțimea soluțiilor ecuației
unde sunt constante astfel încât și dintr-un punct numit „punct la infinit”.
Punctul la infinit este elementul neutru: definim
Fie și două puncte de pe curbă, atunci:
dacă și ,
altfel, de coordonate care se calculează astfel:
,
iar
[1]
Geometric, suma a două puncte P și Q se obține prin trasarea unei linii prin cele două puncte și găsind cel de-al treilea punct R de intersecție al liniei cu E.
În această situație, reprezintă panta dreptei care trece prin P și Q.
Există o teoremă de structură pentru care exprimă condițiile în care grupul este ciclic.
Teoremă
Fie E o curbă eliptică peste cu p>3 număr prim. Atunci există două numere întregi și așa încât
Unde n2|n1 și n2|(p-1)
Consecință: dacă n2=1, atunci este ciclic.
o curbă eiliptică definită peste are aproximativ p puncte.
Putem defini acum problema logaritmului discret în grupul punctelor aparținând unei curbe eliptice:
Fie E o curbă eliptică peste , un punct de ordin n și Q un element din grupul ciclic generat de P:
Problema logaritmului discret pe curbe eliptice cere găsirea unui așa încât .
Alegând cu grijă curbele eliptice, cel mai bun algoritm pentru rezolvarea problemei logaritmului discret este considerabil mai slab decât cel mai bun algoritm pentru rezolvarea problemei logaritmului discret în .
De exemplu, algoritmul de calcul al indicelui nu este deloc eficient pentru problema logaritmului discret pe curbe eliptice.
Pentru unele curbe eliptice, singurii algoritmi eficienți sunt algoritmii generici pentru problema logaritmului discret,cum ar fi metoda baby-step-giant-step și metoda Pollard rho.
Curbele eliptice sunt folisite pe larg în standardele comerciale precum IPsec sau TLs.
ECC cu chei pe 160-250 biți oferă cam același nivel de securitate precum RSA sau sistemele bazate pe problema logaritmului discret cu chei pe 1024-3072 biți.[6]
Sistemul ElGamal pe curbe eliptice
Am studiat sistemul de criptare ElGamal peste un grup ciclic , de ordin q.
Transpunem construcția pe curbe eliptice
1. Se generează o curbă eliptică și P un punct pe curbă(generator), se alege și se calculează
Cheia publică este
Cheia privată este ()
Criptarea: dată o cheie publică și un mesaj , alegem y și întoarce
[6]
Decriptare: dată o cheie secretă și un mesaj criptat , întoarce .[6]
Sistemul transpus pe curbe eliptice păstrează proprietățile sistemului inițial.
Exemplu:
Fie E curba eliptică peste. Vom calcula la început punctele lui E. Aceasta se face astfel se calculează ; apoi se testează dacă z este rest pătratic.
În caz afirmativ, deoarece există o formulă pe care o vom aplica direct, obținând rădăcinile pătratice ale lui z.
Rezultatele sunt strânse în tabelele următoare (toate calculele se realizează modula 19):
Curba eliptică E admite deci 15 puncte; cum ordinul grupului nu este un număr prim, grupul nu este ciclic. Vom alege un element primitiv drept generator. Fie acesta . Pentru 2 se calculează mai întâi (modulo 19):
Acum se pot detrmina
, ,
Deci .
Multiplul următor este . Aveem:
, deci
, ,
de unde rezultă
În mod similar se obșin toate punctele curbei eliptice E:
4.5. Criptarea Menezes – Vanstone
În acest tip de criptare – de fapt o variantă a lui El Gamal – curba eliptică este utilizată pentru „mascare”, domeniile de valori ale textelor clare și criptate sunt mult mai mari.
Fie E o curbă eliptică peste (p>3 prim) care conține un subgrup ciclic H în care problema logaritmului discret este dificilă.
Alegem și
[1]
Valorile sunt publice, iar a este secret.
Pentru , ales aleator (secret) și , definim
,
unde , ,
Pentru un text criptat se definește
,
Fie curba peste , criptarea Menezes-Vanstone autorizează 1818=324 teste clare, față de numai 15 în sistemul El Gamal adaptat.
Luăm din nou și exponentul a=7. Atunci
Dacă Sally dorește să transmită textul clar=(5,11) (de remarcat că acesta nu este un punct din E) și alege , ea va începe prin a calcula
și
deci ,
Apoi calculează (modulo 19):
și
Sally trimite deci luiSam mesajul criptat
După recepție, Sam calculează , apoi
Capitolul V
Comparație între criptosistemele simetrice și criptosistemele cu chei publice
Criptografia cu chei simetrice și cea cu chei publice prezintă diferite avantaje și dezavantaje care sunt prezentate în continuare:
(i) Avantaje ale criptografiei cu chei simetrice
Algoritmii folosiți permit gestionarea unor cantități mari de date, cu viteză relativ bună. În special atunci când este vorba de implementări hard.
Dimensiunile cheilor care sunt utilizate pentru algoritmii simetrici sunt mici.
Algoritmii simetrici pot fi folosiți ca punc de plecare pentru a construi soluții criptografice incluzând generatoarele de numere pseudo-aleatoare și funcțiile hash.
Algoritmii cu chei simetrice pot fi compuși pentru a produce algoritmi mai puternici.
(ii) Dezavantaje ale criptografiei cu chei simetrice
Într-o comunicație cheia trebuie să rămînă secretă pentru ambele părți.
Într-o rețea cu mulți utilizatori numărul cheilor care trebuie gestionate devine o problemă majoră.
Pentru o comunicație între două părți, cheile trebuie schimbate, uneori chiar la fiecare sesiune, ceea ce în condițiile unui canal nesigur de comunicație este o altă problemă.
(iii) Avantaje ale criptografiei cu chei publice
Doar una dintre cele două chei folosite în algoritmii simetrici este ținută secretă.
Administrarea cheilor într-o rețea poate să fie făcută cu un singur administrator “de încredere”.
În general perechile de chei publice/secrete pot fi folosite pe o perioada lungă de timp fără ca acestea să fie schimbate.
Într-o rețea de dimensiuni mari numărul de chei necesare este mult mai mic decît în cazul criptografiei simetrice.
(iv) Dezavantaje ale criptografiei cu chei publice
Viteza algoritmilor cu chei publice (chiar și a celor mai performanți) este de câteva ori mai mică decât a algoritmului cu chei secrete.
Dimensiunea cheilor folosite este mai mare (1024 pentru RSA în comparație cu 64 sau 128 în cazul algorimilor de tip bloc).
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.
Istoria criptografiei cu chei publice este relativ scurtă (din 1970) .
Utilizarea algoritmilor în sisteme de criptare disponibile în Internet
Aplicațiile și protocoalele folosite în Internet au necesități diferite de securitate, în funcție de care se utilizează diverse sisteme criptografice. Se poate observa că nu există un algoritm unic bun pentru orice situație – în funcție de noile rezultate obținute în proiectarea criptografică, dar și în criptanaliză, se renunță la utilizarea unor algoritmi sau se dezvoltă variante îmbunătățite din punct de vedere al securității.
În Internet, sistemele criptografice se pot grupata în două mari categorii: protocoale de rețea și programe/protocoale folosite pentru criptarea mesajelor trimise prin poșta electronică.
Algoritmi de criptare utilizați în aplicațiile din Internet[7]
Bibliografie
1.Anastasiu A “Securitatea informatiei, vol 1 (Criptografie)”, Ed. InfoData, Cluj 2007
2.Groza Bogdan “Introducere in Criptografia cu Cheie Publica”, , Editura Politehnica, 2007
3.Patriciu Victor-Valeriu “Criptografia și Securitatea Rețelelor De Calculatoare Cu Aplicații În C și Pascal”, Editura Tehnică, 1994
4.Popescu Constantin “Introducere in criptografie” ,Universitatea din Oradea, 2009
5.Salomaa Arto “Public-Key Cryptography”, Springer, 1996
6.Simion Emil, Naccache David, Mihaita Adela, Olimid Ruxandra Florentina , Oprina Andrei George “Criptografie si securitatea informatiei. Aplicatii”, Editura Matrixrom, 2011
7.Velicanu Manole, Simona Ionescu, Consideration on data encryption and decryption, Revista Informatica Economică, nr2/2004
8.Zgureanu Aureliu “Criptarea și securitatea informației” , Chișinău 2013
9. http://minnie.tuhs.org/NetSec/Slides/week2.html
10. http://homepage.smc.edu/morgan_david/linsec/labs/encryption-modes-exercise.htm
11. http://www.sm.luth.se/csee/courses/smd/102/lek3/lek3.html
12. http://flylib.com/books/en/3.190.1.38/1/
DECLARAȚIE DE AUTENTICITATE A
LUCRĂRII DE FINALIZARE A STUDIILOR
Titlul lucrării ________________________________________________________
___________________________________________________________________
___________________________________________________________________
Autorul lucrării _____________________________________________
Lucrarea de finalizare a studiilor este elaborată în vederea susținerii examenului de finalizare a studiilor organizat de către Facultatea _________________________________________ din cadrul Universității din oradea, sesiunea_______________________ a anului universitar ______________.
Prin prezenta, subsemnatul (nume, prenume, CNP) _____________________
___________________________________________________________________
___________________________________________________________________,
declar pe proprie răspundere că această lucrare a fost scrisă de către mine, fără nici un ajutor neautorizat și că nici o parte a lucrării nu conține aplicații sau studii de caz publicate de alți autori.
Declar, de asemenea, că în lucrare nu există idei, tabele, grafice, hărți sau alte surse folosite fără respectarea legii române și a convențiilor internaționale privind drepturile de autor.
Oradea,
Data Semnătura
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: Criptosisteme CU Chei Simetrice Si CU Chei Publice (ID: 113206)
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.