01/11/2007 Introducere in Criptografie 1 Intro ducere în Criptografie Prof. univ.dr. Constantin Popescu Departamentul de Matematica si Informatica… [614669]

01/11/2007 Introducere in Criptografie 1
Intro ducere în
Criptografie
Prof. univ.dr. Constantin Popescu
Departamentul de Matematica si Informatica
http://webhost.uoradea.ro/cpopescu/

Agenda

1. Criptografia cu chei publice
2. Criptarea cu chei publice
3. Semnatura digitala
4. Functii greu inversabile
5. Criptosistemul RSA

Introducere in Criptografie 2

Criptografia cu chei publice

O schemă de criptare cu chei publice conține următoarele elemente:

• Textul clar : Acesta este un mesaj sau date de intrare pentru
algoritmul de criptare.
• Algoritmul de criptare : Transform ă textul clar în text cifrat.
• Cheia public ă și cheia privat ă: Este o pereche de chei, una
utilizată pentru criptare (cea public ă) și cealaltă pentru decriptare
(cea privat ă).
• Textul cifrat : Textul produs în urma algoritmului de criptare.
Pentru un mesaj dat, dou ă chei diferite vor produce dou ă texte
cifrate diferite.
• Algoritmul de decriptare : Decripteaz ă textul cifrat, în urma c ăruia
rezultă textul clar.
Introducere in Criptografie 3

Criptarea cu chei publice

Transmiterea
textului cifratCheia privat ă
a lui B Cheia public ă
a lui B
Text clar Algoritmul de Algoritmul de Text clar
la intrare criptare decriptare la ieșire
Introducere in Criptografie 4

Criptarea cu chei publice

Sunt respectate urm ătoarele condi ții: 
1. B poate u șor să genereze cheia public ă PB și cheia privat ă SB.
2. Emitătorul A, știind cheia public ă a lui B și mesajul clar M, poate
să genereze textul cifrat corespunz ător:
C = E PB(M)
3. Receptorul B poate u șor să decripteze textul cifrat C:
M = DSB(C) = D SB(EPB(M))
4. Un atacator care știe PB nu poate s ă determine cheia privat ă SB
5. Un atacator care știe cheia public ă PB și textul cifrat C nu poate s ă
determine mesajul original M
6. Are loc urm ătoarea rela ție:
M = D SB(EPB(M)) = D PB(ESB(M)).
Introducere in Criptografie 5

Semnătura digital ă

Transmiterea
textului cifratCheia public ă
a lui A Cheia privat ă
a lui A
Text clar Algoritmul Algoritmul de Text clar
la intrare de criptare decriptare la ie șire
Introducere in Criptografie 6

Semnătura digital ă

• Semnătura digital ă reprezintă un atribut al unui utilizator, fiind
folosită pentru recunoa șterea acestuia.
• Fie B un receptor de mesaj semnat de A.
• Semnătura lui A trebuie s ă satisfacă următoarele propriet ăți:
o Utilizatorul B s ă fie capabil s ă valideze semn ătura lui A
o Să fie imposibil pentru oricine, inclusiv B, s ă falsifice semn ătura
lui A
o În cazul în care A nu recunoa ște semnătura unui mesaj M,
trebuie să existe un „judec ător” care s ă poată rezolva disputa
dintre A și B.
Introducere in Criptografie 7

Aplicațiile criptosistemelor cu chei publice

Algoritm Criptare/Decriptare Semn ătură Distribu ția
digitală cheilor
RSA DA DA DA
Diffie-Hellman NU NU DA
DSS NU DA NU
Algoritmi baza ți DA DA DA
pe curbe eliptice
Introducere in Criptografie 8

Funcții greu inversabile

• Diffie și Hellman au sugerat și o metod ă de implementare practic ă.
• O funcție este greu inversabil ă și ușor de calculat, dar pentru
aproape toate valorile y din codomeniu este imposibil
computațional să se calculeze x = f –1(y).
• Cu alte cuvinte este imposibil computa țional să se calculeze f -1
dacă se dispune de o descriere complet ă a lui f.
• O funcție greu inversabil ă se spune c ă este cu trapă atunci c ând f -1
este ușor de calculat numai dac ă se dispune de o informa ție trapă.
• Necunoașterea acestei informa ții face ca func ția să fie greu
inversabil ă.
• O astfel de pereche de func ții ( f, f -1) poate constitui perechea (E,D)
a unui criptosistem cu chei publice.
Introducere in Criptografie 9

Criptosistemul RSA

• Prima schem ă criptografic ă cu chei publice a fost realizat ă în anul
1977 de c ătre Ron Rivest, Adi Shamir și Len Adleman de la MIT.
• Schema Rivest-Shamir-Adleman (RSA) este cea mai r ăspândită și
implementat ă schemă din lume.

Generarea cheilor:

1. Se selecteaz ă două numere întregi prime p și q.
2. Se calculeaz ă produsul n=p*q .
3. Se calculeaz ă indicatorul lui Euler Φ(n)=(p-1)*(q-1) .
4. Se selecteaz ă un număr întreg e astfel înc ât
c.m.m.d.c.( Φ(n),e)=1, 1<e< Φ(n).
5. Se calculeaz ă d astfel înc ât d = e-1 mod Φ(n).
6. Cheia public ă este (e,n) , iar cheia privat ă este d.
Introducere in Criptografie 10

Criptosistemul RSA

Algoritmul de criptare:

• Presupunem c ă un utilizator A are cheia public ă (e,n) și cheia
privată d.
• Utilizatorul B cripteaz ă mesajul M pentru a fi transmis la A astfel:

1. Obține cheia public ă (e,n) a lui A.
2. Transform ă mesajul ce va fi criptat într-un num ăr întreg M în
intervalul [0,n-1] .
3. Calculeaz ă C = Me (mod n) .
4. Trimite textul cifrat C la utilizatorul A.
Introducere in Criptografie 11

Criptosistemul RSA

Algoritmul de decriptare:

• Pentru a determina textul clar M din textul cifrat C, utiliz. A calc.:
M = Cd (mod n) .
• Numai utilizatorul A cunoaste cheia privata d.

Introducere in Criptografie 12

Criptosistemul RSA

Exemplu:
Se genereaz ă mai întâi cheile:
1. Se selecteaz ă două numere prime p = 7 și q = 17.
2. Se calculeaz ă n = p*q = 7*17 = 119.
3. Se calculeaz ă Φ(n) = (p-1)*(q-1) = 96.
4. Se alege e a. î. e este relativ prim cu Φ(n) = 96. În acest caz e = 5.
5. Se determină d astfel înc ât d*e = 1 mod 96 și d<96. Avem d = 77,
deoarece 77*5 = 385 = 4*96+1.
6. Cheia public ă este (5,119), iar cheia privat ă este 77.
• Se consider ă că textul clar este M =19.
• Textul criptat va fi C = 195 mod 119 = 2476099 mod 119 = 66.
• Pentru decriptare se calculeaz ă 6677 mod 119 = 19 mod 119.
Introducere in Criptografie 13

Atacuri asupra algoritmului RSA

• Firme produc ătoare de sisteme de programe și echipamente, ca
Novell, DEC, Lotus, Motorola, folosesc acest algoritm.
• Instituții importante (Departamentul Ap ărării din SUA, Boeing,
rețeaua bancar ă internațională SWIFT) folosesc acest algoritm
pentru protejarea și autentificarea datelor, parolelor, fi șierelor,
documentelor memorate sau transmise prin re țele.
• Există trei tipuri de atacuri asupra algoritmului RSA:
o Încercarea tuturor cheilor private posibile.
o Factorizarea num ărului n în factori primi p și q.
o Aceste atacuri depind de timpul de execu ție a alg. de decriptare.
Introducere in Criptografie 14

Atacuri asupra algoritmului RSA

Din punct de vedere matematic, exist ă 3 atacuri asupra RSA:
1. Factorizarea numărului n în factori primi p și q. Se poate astfel
determina Φ(n) = (p-1)*(q-1), iar apoi d = e-1 (mod Φ(n)).
2. Determinarea lui Φ(n) direct, f ără a determina mai întâi p și q. Și în
acest caz se poate determina apoi d = e-1 (mod Φ(n)).
3. Determinarea lui d în mod direct, f ără a determina mai întâi Φ(n).
• Determinarea lui Φ(n) este echivalent cu factorizarea num ărului n,
iar determinarea lui d ( știind doar pe e și n) se face într-un timp tot
așa de mare ca și factorizarea lui n.
• Securitatea RSA se bazeaz ă pe dificultatea factoriz ării unui num ăr
întreg în factori primi.
• RSA cu lungimea cheii de 1024 bi ți (aproximativ 300 cifre ) este
considerat destul de puternic pentru aplica țiile actuale.
Introducere in Criptografie 15