CAPITOLUL III CRIPTOGRAFIE

Istoria criptografiei ncepe nc de acum 4000 de ani (la egipteni). De cele mai multe ori rezultatele acesteia erau folosite n domeniul militar, diplomatic i guvernamental. Criptografia a fost folosit ca un instrument important n protejarea secretelor i strategiilor naionale. Odat cu dezvoltarea, n anii 60, a sistemelor de comunicaie i a computerelor, apare cerina de a oferi sectorului privat mijloace de a proteja informaia n form digital i de a asigura servicii de securitate. Cea mai important realizare, care a dus la o dezvoltare fr precedent n istoria criptografiei, este o lucrare a lui Deffie i Hellman n 1976. Aceasta introduce un concept nou, revoluionar acela de criptografie cu cheie public i furnizeaz o metod nou i ingenioas pentru schimbul de chei la care securitatea se bazeaz pe imposibilitatea de a rezolva problema logaritmilor discrei. Chiar dac cei doi nu au realizat, la acel moment, n mod practic, o schem de criptografie cu cheie public, ideea a generat deosebit interes i o activitate intens n domeniu. n 1978 Rivest, Shamir i Adleman au descoperit prima schem practic de criptare cu cheie public i de semntur (RSA) bazat tot pe o problem dificil din matematic i anume factorizarea numerelor mari. Cu toate c anii 80 au adus noi metode de factorizare, acestea nu au slbit securitatea sistemului RSA. O alt clas de scheme practice cu cheie public, bazat tot pe problema logaritmului discret, este gsit de ElGamal n 1985. Gsirea de noi scheme cu cheie public i mbuntirea mecanismelor criptografice existente continu ntr-un ritm alert. Cteva din principalele scopuri urmrite n criptografie sunt: 1. Confidenialitatea presupune pstrarea secret a informaiei fa de toi cei neautorizai s o cunoasc. 2. Integritatea datelor realizeaz protejarea datelor la alterare sau manipularea de ctre persoane neautorizate. Prin manipularea datelor nelegem procese cum ar fi inserii, ntrzieri sau substituiri. 3. Autentificarea presupune posibilitatea de identificare a informaiei i a entitii (o persoan, un terminal de computer, o carte de credit). 4. Non-repudierea - care previne negarea unor angajamente sau aciuni anterioare. Criptografia trebuie s acopere n mod corespunztor aceste patru direcii att n teorie ct i n practic. Ea trebuie s previn i s detecteze furtul i alte aciuni ilegale, fiind doar una din tehnicile de asigurare a securitii informaiei. Scopul acestui capitol este de a cunoate cteva sisteme criptografice simple i de a ne familiariza cu sistemele cu cheie public.

1.

Criptosisteme simple.

Criptografia studiaz metode de a trimite mesaje sub o form mascat aa nct transformarea mesajului din forma lui secret n cea iniial s poat fi realizat doar de persoana dorit / autorizat. Mesajul iniial se numete text de baz. Forma transformat a mesajului poart numele de text cifrat. Ambele texte pot conine pe lng litere ale alfabetului i numere, semne de punctuaie, pauze sau alte simboluri. Procesul de transformare a textului de baz n cel cifrat se numete cifrare sau criptare iar procesul invers poart numele de decifrare sau decriptare. Textul de baz ct i cel cifrat sunt mprite n uniti de mesaj care pot fi formate dintr-o liter, din dou (diagraf) sau mai multe. Cifrul este transformarea care -1-

pune n legtur fiecrei uniti de mesaj din textul de baz o unitate de mesaj corespunztoare din care va fi format textul cifrat. Cheia de cifrare determin transformarea particular care este folosit dintr-o mulime de posibile transformri. Avnd definite transformarea de cifrare i inversa sa spunem c am definit un criptosistem. Vom considera n toate exemplele c mesajul este alctuit din litere ale unui alfabet cu 26 de litere (cel al limbii engleze, de exemplu) . Atribuim fiecrei litere din alfabet un echivalent numeric de la 0 la 25. Astfel realizm corespondenele A - 0, B 1,, Z 25 ca n tabelul de mai jos: a o n 13 b 1 o 14 c 2 p 15 D 3 Q 16 e 4 r 17 f 5 s 18 g 6 t 19 h 7 u 20 i 8 v 21 j 9 w 22 k 10 x 23 l 11 y 24 m 12 z 25

A. Criptosisteme monografice sau caracter. Aici, unitatea de mesaj este format dintr-o singur liter. Un prim exemplu simplu este un criptosistem care se presupune c a fost inventat i folosit de Iulius Cezar. 1.1. Exemplu. n textul de baz fiecare liter, pe care o notm cu P, este nlocuit cu litera aflat la 3 poziii la dreapta fa de aceasta pe care o notm cu C. Astfel, litera a devine d; litera x se transform n a ; y devine b iar z devine c . Transformarea se poate scrie innd cont de echivalenii numerici ai literelor astfel: C P + 3(mod 26) , 0 C 25. Presupunem c textul de baz este : THIS MESSAGE IS TOP SECRET Pentru nceput, textul de baz se mparte n blocuri de 5 litere THISM ESSAG EISTO PSECR ET care apoi sunt nlocuite cu echivalenii lor numerici: 19 7 8 18 12 4 18 18 0 6 4 8 18 19 14 15 18 4 3 17 4 10. Fiecare echivalent numeric este transformat dup regula precizat i rezult: 22 10 11 21 15 7 21 21 3 9 7 11 21 22 17 18 21 7 6 20 7 13. Blocurile nou construite sunt transformate n litere corespunztoare echivalenilor numerici: WKLVP HVVDJ HLVWR SVHGU HW care formeaz textul cifrat. Pentru decifrare, se folosete transformarea invers P C 3(mod 26) cu 0 P 25 i se aplic acelai procedeu dup care se refac din blocuri cuvintele iniiale. Acest exemplu este un caz particular al criptosistemelor descrise prin transformrile de forma C P + k (mod 26) , 0 C 25. Acestea se numesc transformri de deplasare. Cheia de cifrare este k . Fie acum transformarea definit prin C aP + b(mod 26) , 0 C 25, a,b ntregi cu (a,26) =1. Se observ c pentru a exist (26) = 12 posibiliti de atribuire i pentru b avem 26. Deci exist 1226 = 312 astfel de transformri ( printre care i transformarea identic) numite transformri afine. Cheia de cifrare este dat de a i b. Se remarc faptul c transformrile de deplasare sunt cazuri particulare ale celor afine obinute pentru a = 1. Procesul de criptare se desfoar la fel ca n exemplul dat, numai c de -2-

aceast dat echivalenii numerici se modific dup noua relaie. Pentru decriptare se folosete transformarea P a (C + b)(mod 26) , 0 P 25 unde a este inversul lui a modulo 26. Dac se dorete spargerea unui cifru presupus a fi de tip monografic trebuie fcut o analiz o frecvenei apariiei literelor din textul cifrat i fcut o comparare cu frecvena literelor dintr-un text obinuit. Se cunoate c n limba englez cele mai frecvente litere din cadrul unui text sunt E, T, N, R, I, O, A (pentru limba romn ele ar fi I, E, A, B). Astfel, punnd n coresponden cea mai des ntlnit liter din textul cifrat (de preferin mai lung pentru o mai corect realizare a corespondenei ntre literele de frecven maxim) cu cea care apare de cele mai multe ori ntr-un text arbitrar se pot dobndi informaii legate de transformarea folosit la criptare. 1.2. Exemplu. Presupunem c un text a fost cifrat printr-o transformare de deplasare i observm c litera care are frecvena cea mai mare n textul cifrat este p. Putem atunci presupune c ea corespunde literei e din textul de baz, cum aceasta are cea mai mare frecven ntr-un text scris n limba englez. innd cont de echivalenii numerici corespunztori i nlocuind n relaie obinem 15 4 + k (mod 26) , de unde cheia de cifrare posibil folosit este k = 11. Pentru transformrile de deplasare, determinarea cheii nu presupune necesitatea ca textul cifrat s fie lung pentru c, de fapt, exist doar 25 de posibiliti pentru k ceea ce nu presupune un volum att de mare de munc. n concluzie, acest tip de criptosistem nu este prea bun. 1.3. Exemplu. S presupunem acum c un text a fost criptat printr-o transformare afin. Din analiza frecvenei literelor din textul cifrat, vedem c cel mai des apar literele l i u . Bnuim atunci c l corespunde lui e iar u lui t. Obinem atunci relaiile 11 4a + b(mod 26) i 20 19a + b(mod 26) . Din rezolvarea acestui sistem de congruene obinem a 11(mod 26) i b 19(mod 26) . Dac presupunea noastr este corect, transformarea afin folosit este dat de C 11P + 19(mod 26) iar pentru decriptare se folosete P 19(C 19) 19C + 3(mod 26) unde am inut cont c a 19(mod 26) . B. Criptosisteme poligrafice sau bloc (Hill) Pentru a evita faptul c primele criptosisteme sunt vulnerabile, criptanaliza realiznduse folosind frecvena literelor n text, s-a preferat mprirea textului de baz n blocuri de o anumit lungime i transformarea acestora n blocuri cu aceeai dimensiune. Aceste criptosisteme se numesc poligrafice sau bloc. Studiem nti cazul cifrului diagrafic pe un exemplu concret. Aici, blocurile sunt formate din dou litere. Considerm ca text de baz THE GOLD IS BURIED IN ORONO. nti se mparte textul de baz n blocuri de dou litere. Dac numrul literelor este impar, ultimul bloc este completat cu a liter, de exemplu x. TH EG Ol DI SB UR IE DI NO RO NO Fiecare liter din bloc este nlocuit cu echivalentul sau numeric 19 7 4 6 14 11 3 8 18 1 20 17 8 4 3 8 13 14 17 14 13 14 Fiecare bloc de numere din textul de baz P1P2 este nlocuit cu blocul C1C2 dup transformarea C1 5 P1 + 17 P2 (mod 26) -3-

C 2 4 P1 + 15 P2 (mod 26) . Obinem acum blocurile 6 25 18 2 23 13 21 2 3 9 25 23 4 14 21 2 17 2 11 18 17 2 care transformate n litere formeaz textul cifrat GZ SC XN VC DJ YX EO VC RC LS RC Procesul de decifrare se face dup regula P1 17C1 + 5C 2 (mod 26) P2 18C1 + 23C2 (mod 26) Acest criptosistem este mult mai uor de descris matriceal, i anume: C1 5 17 P1 C 4 15 P (mod 26) . Se observ c matricea care intervine are invers modulo 26, 2 2 matricea invers intervenind n procesul de decriptare.
Trecem acum la cazul general, n care blocurile n care este mprit textul de baz conin fiecare n litere. Procesul de cifrare urmrete aceeai cale ca pentru cifrul diagrafic doar c, transformarea acum este dat de C A P (mod 26) unde A M n (Z ) cu ( det A, 26 )
C1 P 1 = 1 , C = , P = . Pstrnd notaiile fcute n primul capitol, A este inversa modulo C P n n 26 a matricei A, adic AA I n (mod 26) . De aici, pentru decriptare se folosete relaia:
P A C (mod 26) .

Pentru o mai bun exemplificare, considerm cazul n = 3 . Textul de baz este STOP PAYMENT iar transformarea este dat de P 11 2 19 C1 1 C 2 A P2 (mod 26) unde A = 5 23 25 . P 20 7 1 C 3 3 det( A) 5(mod 26) deci, ( det A, 26 ) = 1. Cum la mprirea textului n blocuri de cte 3 litere ultimul bloc este format doar din dou litere, mai adugm un x n final: STO PPA YME NTX Transformm blocurile n numere folosind echivalenii numerici 18 19 14 15 15 0 24 12 4 13 19 23 Pentru primul bloc avem: C1 11 2 19 18 8 C 2 5 23 25 19 19 (mod 26) . C 20 7 1 4 13 3 Repetnd calculul pentru fiecare bloc, obinem 8 19 13 13 4 15 0 2 22 20 11 0 care convertite n litere dau textul cifrat ITN NEP ACW ULA

-4-

 6 5 11 Pentru decifrare folosim matricea A = 5 1 10 . 7 3 7

Aceste criptosisteme sunt i ele vulnerabile privind analiza frecvenei blocurilor de litere. De exemplu, cele mai des ntlnite grupuri de dou litere n limba englez sunt TH, HE iar pentru blocuri de trei litere apar cel mai frecvent THE, AND, THA. Fcnd analiza corespunztoare, putem gsi matricea de cifrare. 1.4. Exemplu. Dac ntr-un text cifrat cu cifru diagrafic cele mai frecvente perechi de litere sunt KX i VZ putem bnui c acestea corespund n textul de baz lui TH respectiv, HE. Atunci, ( 19 7) i ( 7 4 ) sunt trimise n ( 10 23 ) respectiv n ( 21 25 ). Obinem 10 21 19 7 astfel, 23 25 A 7 4 (mod 26) . 19 7 4 19 de este unde, Inversa modulo 26 a matricei 7 4 19 19 10 21 4 19 23 17 (mod 26) d o posibil cheie. A 23 25 19 19 21 2

2. Criptare cu cheie public.

Prin definiie, un criptosistem cu cheie public are proprietatea c o persoan care tie doar s cifreze nu poate folosi numai cheia de cifrare pentru a gsi cheia de decifrare n timp util. Denumirea de cheie public provine din faptul c informaia necesar trimiterii de mesaje secrete (cheia de cifrare) poate deveni informaie cunoscut de oricine fr ca s se permit citirea mesajelor secrete de ctre persoane neautorizate. n trecut, criptografia era folosit mai ales n scopuri militare i diplomatice. Exista de fiecare dat un grup mic, bine definit de utilizatori, care puteau mpri un sistem de chei iar noile chei puteau fi distribuite periodic uor. De aceea, acest tip de sistem nu prezenta atunci avantaje majore. n prezent, aplicaiile criptografiei s-au extins i includ multe alte domenii unde sistemele de comunicaii joac un rol esenial (colectare i pstrare de nregistrri cu informaii confideniale, tranzacii financiare electronice, etc.). De multe ori exist o reea mare de utilizatori n care un grup restrns trebuie s pstreze secretul comunicaiei att fa de ceilali din reea ct i fa de alte persoane din afar. La fel, este posibil ca n urma unei comunicri avute, unul dintre parteneri trebuie s transmit o parte a informaiei secrete unei tere pri. Nu este posibil ca mereu s se realizeze schimbul de chei ntre toi posibilii parteneri confideniali. De remarcat este faptul c, folosind un sistem cu cheie public, este posibil realizarea unei comunicaii secrete ntre dou pri fr a avea un contact iniial, fr a stabili la nceput dac au ncredere unul n altul, fr s schimbe informaii priorii. n continuare prezentm pe scurt sistemul RSA ( Rivest, Shamir, Adleman ) care este unul din cele mai vechi i mai cunoscute criptosisteme cu cheie public. El se bazeaz pe extrema dificultate a factorizrii numerelor.

-5-

Pentru realizarea sa trebuie alese dou numere prime mari p i q avnd de exemplu 100 de cifre zecimale i se calculeaz n = pq . Cunoscnd factorizarea lui n este uor de calculat (n) = ( p 1)(q 1) = n + 1 p q . Apoi alegem un numr natural e , 1 e (n) care este relativ prim cu (n) . Cheia de cifrare este perechea ( n ,e) care se face public. Trebuie remarcat c alegerea nu se face la ntmplare. Ea se poate realiza cu ajutorul unui generator aleator de numere adic a unui program de computer care genereaz un ir de cifre pentru care nu se poate stabili o regul de a intui elementele. p i q nu trebuie alese din tabele de numere prime ca de exemplu numere Mersenne prime. Pentru alegerea unui numr prim mare se poate porni de la un numr aleator mare m. Dac el este par, alegem m + 1. Pentru acesta aplicm testul probabilistic Miller-Rabin i vedem dac convine. Dac nu, repetm pentru m + 2, m + 4,... pn gsim primul numr prim m. Pentru alegerea lui e se poate face acelai lucru ca mai sus pentru a determina un numr prim mai mare dect max( p,q) i mai mic dect (n) . Acesta va verifica n mod sigur condiia (e, (n) ) = 1. Cheia de decifrare este perechea (n,d) unde d este inversul modulo (n) al lui e . Pentru realizarea cifrrii, literele vor avea toi echivalenii numerici formai din dou cifre. De aceea, lui A i corespunde 00, lui B 01, lui C 02,... . Convertim literele din textul de baz n echivalenii numerici corespunztori, apoi grupm numerele n blocuri de 2m cifre zecimale unde 2m este cel mai mare numr par pentru care toate blocurile ce apar, privite ca numere cu 2m cifre zecimale, sunt mai mici dect n . De exemplu, dac 2525 < n <252525 atunci, m = 2. Fiecare bloc este transformat apoi dup relaia C P e (mod n) rezultnd textul cifrat. Pentru decifrare, blocurilor din textul cifrat li se aplic transformarea P C d (mod n) dup care se revine la litere i se recupereaz textul iniial. Pentru uurin, considerm exemplul urmtor: 2.1. Exemplu. Alegem n = 4359 = 2537 , e = 13 i considerm textul de baz: PUBLIC KEY CRYPTOGRAPHY Grupm n blocuri de dou litere ( m = 2) adic scriem blocurile de 4 cifre: 1520 0111 0802 1004 2402 1724 1519 1406 1700 1507 2423 cu meniunea c am adugat un x n final pentru a avea aceeai lungime toate blocurile. Fiecare bloc este transformat prin C P13 (mod 2537) . Obinem n final textul cifrat format din: 0095 1648 1410 1289 0811 2333 2132 0370 1185 1457 1084 Pentru decifrarea mesajului este nevoie de cheia de decifrare, n acest caz, d = 937. 2.2. Observaie. a) n alegerea numerelor prime p,q este necesar s fie ndeplinite cteva condiii, i anume: 1. p i q s nu fie prea apropiate, unul s aib de exemplu cu cteva cifre mai puin dect cellalt. 2. ( p 1, q 1) s fie un numr mic. 3. p 1, q 1 au amndoi cel puin un factor prim mare. Lista acestor condiii rmne deschis adugnd la ea noi restricii furnizate de diferitele cazuri particulare ce se mai pot descoperi i pentru care factorizarea lui n devine simpl. b) Dac n este produs de dou numere prime, a cunoate pe (n) este echivalent cu a cunoate factorizarea lui n. Presupunem c am putea sparge un sistem RSA determinnd un -6-

numr d pentru care a a de (mod n) , oricare ar fi a prim cu n. Aceasta nseamn c de 1 este multiplu al celui mai mare multiplu comun al numerelor p 1, q 1. Cunoaterea lui m = de 1 este un rezultat mai slab dect dac l-am cunoate pe (n) . Dar iat o metod care arat cu mare probabilitate c vom reui s folosim acest m la factorizarea lui n. Presupunem cunoscut n care este produsul a dou numere prime netiute i m pentru care a m 1(mod n) , oricare ar fi a prim cu n. De observat c m trebuie s fie par (lum a =-1). m Vedem nti dac are aceeai proprietate cu m. Dac da, l folosim pe acesta mai departe. 2
m

Dac nu, atunci congruena a 2 1(mod n) nu se verific pentru cel puin 50% din valorile lui a modulo n. Astfel, dac pentru un numr suficient de valori date lui a congruena
m

a 2 1(mod n) este verificat, este o mare probabilitate ca ea s se verifice pentru orice numr m prim cu n. Atunci, putem nlocui pe m cu i relum procedeul pn cnd pentru jumtatea 2 lui m cazurile considerate nu verific congruena. Apar dou posibiliti: m 1. este multiplu numai al unuia dintre numerele p 1, q 1(pentru p -1 s 2
m

presupunem) . n acest caz, a 2 1(mod p) dar exact n jumtate din cazuri este congruent cu 1( mod q) iar n restul cazurilor este congruent cu -1 ( mod q). m m nu este multiplu pentru nici unul dintre numerele p 1, q 1. Atunci, a 2 este 2. 2 1 modulo p i q ( adic modulo n ) pentru exact 25% din cazuri, este 1 modulo p i q pentru exact 25% din cazuri iar n restul rmas de 50% din cazuri este 1 modulo unul dintre p i q i 1 modulo cellalt prim. Astfel, ncercnd pentru valori aleatoare ale lui a, probabilitatea de a gsi un a pentru care
a 1 este divizibil cu unul dintre numerele prime, p de exemplu, este ridicat. Odat gsit un
m 2 m 2

astfel de a, putem factoriza imediat n pentru c ( n, a 1 ) = p. Metoda prezentat este un exemplu de algoritm probabilistic.

-7-