1

Algoritmi de criptare cu chei publice(II)

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.

• reprezintă standardul în domeniul semnăturilor digitale şi al confidenţialităţii cu chei publice

• cea mai sigură metodă de cifrare şi autentificare disponibilă comercial (implementare prin programe sau dispozitive hardware speciale)

2

• Protocoale de securitate care folosesc RSA:• IPSEC/IKE – Internet Protocol Security/Internet Key

Exchange - IP data security - funcții matematice și algoritmide criptare și autentficare pentru a asigura confidențialitatea, integritatea și non-repudierea informațiilor din fiecare pachetIP transmis pe rețea

• TLS/SSL - Transport Layer Security /Secure Sockets Layer – permit comunicații sigure pe Internet

• PGP (Pretty Good Privacy)- asigură confidențialitate criptografică și autentificare pentru comunicarea datelor - email security

• SSH (Secure Shell) -permite ca datele să fie transferatefolosind un canal securizat intre dispozitive de rețea - terminal connection security

3

Algoritmul de criptare cu cheie publică RSAProbleme de comunicare...• Să presupunem că două persoane, Bob şi Alice doresc

să comunice într-un mod cât mai sigur prin transmitereade mesaje secrete.

• Există însă şi o treia persoană, Eve, care doreşte săintercepteze şi să decripteze traficul de mesaje dintreBob şi Alice.

• Alice şi Bob pot fi oameni de afaceri aflaţi la distanţă,avioane aflate în zbor sau chiar doi prieteni ce doresc săcomunice într-un mod cât mai privat. În nici unul dincazuri Eve nu poate fi oprită să ”asculte” traficul radiosau cel de pe internet.

4

• Soluţia clasică a problemei este utilizarea algoritmilor decriptare cu cheie privată (criptare simetrică).

• Pentru a fi sigură, această soluţie implică un schimb dechei între Alice şi Bob.

• Acest schimb de chei poate fi făcut printr-o întâlnireprealabilă între cele două persoane sau, în cazul unorinstituţii, companii sau guverne, cu ajutorul unor curieri.

5

• Dacă cele două persoane Alice şi Bob locuiesc în zoneaflate la distanţă mare între ele, întâlnirea se poatedovedi foarte costisitoare, uneori aproape imposibilă.

• Soluţia ar putea fi schimbarea unei chei digitale folosindinternetul sau chiar poşta clasică.

• Nici una dintre aceste metode nu este însă sigură,deoarece cheia poate fi interceptată !!!

6

Algoritmul de criptare cu cheie publică RSACriptografia cu cheie publică• Soluţia problemei anterioare este utilizarea algoritmilor de

criptare cu cheie publică.• Acest tip de criptare implică folosirea a două tipuri de chei

• chei private ştiute doar de destinatarii mesajelor;• chei publice (publicate de destinatar).

7

• Fiecare utilizator al acestui sistem de criptare vaavea două chei:

• cea privată pe care o păstrează secretă• cea publică pe care o poate trimite la toţi cei

care doresc sa-i trimită mesaje criptate.

• Orice ”adversar” de tipul Eve descris anterior vacunoaşte cheia publică dar nu va putea decriptamesajul dacă nu cunoaşte cheia privată.

8

9

Algoritmul RSA - 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,n).

10

• Algoritmul de criptare: 1. Presupunem că un utilizator A are cheia publică (e,n) şi

cheia privată (d,n). 2. 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 utilizatorului A.

11

Criptosistemul RSA • Algoritmul de decriptare:

Pentru a determina textul clar M din textul cifrat C, utilizatorul A calculează:

M = Cd (mod n)

• Numai utilizatorul A cunoaşte cheia privată d.

12

• Un sistem care asigură confidenţialitatea va avea ca elemente următoarele perechi:

1. (e, n) cheia publică;2. (d, n) cheia secretă;

• Un criptanalist care are la dispoziţie perechea (e, n) trebuie să determine d ţinând cont că ed(mod Ф(n))=1. Pentru aceasta trebuie determinat Ф(n)=(p-1)(q-1), deci implicit p şi q, problemă care se reduce la a factoriza numărul n, problemă dificilă pentru un număr n mare.

13

Obs.• RSA fiind un cod bloc, va necesita împărţirea mesajului

iniţial în blocuri de dimensiuni mai mici decât n, pentru a se putea realiza operaţiile modulo n.

• Dimensiunile blocurilor pot fi determinate încă de la începutul algoritmului deoarece se cunosc dimensiunilepe biţi ale numerelor prime generate p şi q, să zicem l/2, deci dimensiunea lui n=pq este l.

• Cunoscând astfel lungimea pe biţi a lui n, putem împărţimesajul iniţial în blocuri de lungime l-1, fără a riscaoperaţii care să depăşească modulo n.

14

Exemplu de criptare/decriptare RSA• Generarea Cheilor

1) Generaţi 2 numere prime p şi q cât mai mari

p = 7q = 19

2) Fie n = p * qn= 7 * 19 n = 133

3) Fie Ф(n) = (p-1)*(q-1)Ф(n) = (7-1)*(19-1) Ф(n) = 6 * 18 =108

p = 7q = 19n = 133Ф(n) = 108e = ?d = ?

Cheia publică = (e,n) = ?Cheia privată = (d,n) = ? 15

4) Alegeţi e astfel încât cmmdc(e, Ф(n)) = 1e = 2 => cmmdc(e, 108) = 2 (NU)e = 3 => cmmdc(e, 108) = 3 (NU)e = 4 => cmmdc(e, 108) = 4 (NU)e = 5 => cmmdc(e, 108) = 1 (DA)

p = 7q = 19n = 133Ф(n) = 108e = 5d = ?

Cheia publică=(e,n)= (5,133)Cheia privată = (d,n) = ?

16

5) Găsiţi d astfel încât (d*e) % Ф(n) = 1sau altfel spus, d*e = 1 + x*Ф(n)(unde x poate fi orice număr întreg) =>d = (1 + x* Ф(n))/e

x = 0 => d = 1/5 (NU)x = 1 => d = 109/5 (NU)x = 2 => d = 217/5 (NU)x = 3 => d = 325/5 (DA)

d = 65

p = 7q = 19n = 133Ф(n) = 108e = 5d = 65

Cheia publică=(e,n)= (5,133)Cheia privată=(d,n)=(65,133)

17

Criptarea RSA

Vom calcula C = Me % nFie M = 6 =>

C = Me % n= 65 % 133= 7776 % 133= 62

• Cheia publica = (e,n) = (5,133)• RSA( 6, (5,133) ) = 62

18

Decriptarea RSA

Vom calcula M = Cd % n

• Cheia privată = (d,n) = (65,133)• RSA-1( 62, (65,133) ) = ?

M = 6265 % 133 = 6

RSA-1( 62, (65,133) ) = 6

19

Criptosistemul RSA Exemplul 2: • 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. • d*e = 1 + x* Φ(n) (unde x este număr întreg) =>• d = (1 + x* Φ(n))/e

Avem d = 77, deoarece 77*5 = 385 = 4*96+1.

20

Cheia publică = (e,n) = (5,119)Cheia privată = (d,n) = (77,119)

Se consideră că textul clar este M =19. • Textul criptat va fi C = 195 mod 119 = 2476099 mod 119

= 66.• Cheia publica = (e,n) = (5,119)• RSA( 19, (5,119) ) = 66

• Pentru decriptare se calculează M = Cd mod n• Cheia privată = (d,n) = (77,119)• RSA-1( 66, (77,119) ) =

= 6677 mod 119 = 19

21

Criptosistemul RSA • Exemplul 3:• Se generează mai întâi cheile: 1. Se selectează două numere prime p = 101 şi q = 113. 2. Se calculează n = p*q =101*113 = 11413. 3. Se calculează Φ(n) = (p-1)*(q-1) = 11200 4. Se alege e a. î. este prim cu Φ(n) = 11200=2 6527 . În acest caz e =

35335. Se determină d astfel încât d*e = 1 mod 11200 şi d<11200. Avem d= 6597, deoarece 3533 * 6597 = 23307201 = 2081*11200+1. 6. Cheia publică este (3533 , 11413), iar cheia privată este 6597. • Mesajul 9726 va fi criptat 97263533 mod 11413 = 5761• Decriptarea: mesajul 5761 va fi 57616597 mod 11413 = 9726.

22

Viteza de criptare/decriptare RSA:

23

Recomandări pentru alegerea cheilor RSA

• Recentele progrese făcute în factorizarea întregilor şi în procesarea paralelă au dat naştere la necesitatea unor chei din ce în ce mai mari pentru sistemele de criptare cu chei publice.

• Ultimele recomandări făcute de laboratoarele RSA Data Security pentru alegerea dimensiunii cheilor de cifrare RSA sunt:

• Securitate pe termen scurt (de ex. Chei utilizatori) 768 biți

• Securitate pe termen mediu (de ex. Chei organizații) 1024 biți

• Securitate pe termen lung(de ex. Chei administratori)2048 biți

Dezavantaje ale algoritmului RSA

• RSA criptează numere şi nu litere. Pentru a cripta secvenţe de text sau imagini, va trebui să aplicăm algoritmul pentru fiecare octet în parte. Acest tip de criptare poate uşura foarte mult munca unui criptanalist (utilizează testul Kasiski) şi poate conduce în cele din urmă la aflarea cheii private. Pentru a evita astfel de situaţii, de obicei, criptarea RSA mai introduce şi octeţi cu valori aleatorii.

• Din cauza complexităţii algoritmului de criptare / decriptare, RSA este considerat lent în comparaţie cu algoritmii simetrici de criptare.

25

Aplicaţii ale algoritmului RSA

• domeniul telecomunicaţiilor: telefoane publice, cu cartele electronice, sau telefoanele mobile (protocoale de autentificare a persoanei apelate)

• domeniul sănătăţii, prin intermediul cardurilor electronice care să conţină istoricul medical al unui individ.

• securitatea naţională: cărţi de identitate, paşapoarte, legitimaţii magnetice.

• economie: cardurile bancare, comerţul electronic• informatica: confidenţialitatea poştei electronice, a

informaţiilor de pe o pagină de web

26

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: - Forţă brută: încercarea tuturor cheilor private posibile. - Atacuri matematice: factorizarea numărului n în

factori primi p şi q.– Atacuri temporizate: aceste atacuri depind de timpul

de execuție a algoritmului de decriptare.27

Criptanaliză RSA

• Tipuri de atacuri posibile:

• Căutarea în spaţiul mesajelor.

• Ghicirea numărului "d".

• Criptarea repetată a ciphertext-ului folosind cheia publică. Se poate demonstra matematic că în cele din urmă, după un anumit număr de iteraţii, putem afla plaintext-ul !!!

28

• Atacuri asupra cmmdc. De obicei organizaţiile guvernamentale/private mari generează o singură dată cheile private/publice pe care apoi le distribuie angajaţilor.

• Atacuri asupra numărului e.Pentru a genera o viteză cât mai mare de criptare, se poate alege un număr e cât mai mic.(în multe cazuri din lumea reală, e=3 !!!)

• Factorizarea cheii publice: încercarea de a deduce cheia privată din cheia publică, concurs lansat de RSA Laboratories.

29