Criptografie si Securitate

Eduard Cimbru

Criptografie cu chei publice

2 Criptosisteme bazate pe problema factorizarii
    2.1 Criptosistemul RSA
    2.2 Criptosistemul Rabin
    2.3 Criptosistemul Paillier

3 Criptosisteme bazate pe problema rucsacului
    3.1 Criptosistemul Merkle-Hellman

4 Criptosisteme bazate pe problema logaritmului discret
    4.1 Criptosistemul ElGamal
    4.2 Schema DSS
    4.3 Scheme criptografice bazate pe teoria curbelor eliptice

5 Criptosisteme bazate pe teoria laticilor
    5.1 Teoria laticilor
    5.2 Criptosistemul NTRU

6 Criptosisteme bazate pe teoria limbajelor formale
    6.1 Criptosistemul Wagner-Magyarik

7 Concluzii

Nota: Pentru a viziona corect aceasta pagina folositi Internet Explorer!!!

Descarca/Download

Legaturi/Links

Capitolul 1

Introducere

1.1 Criptografie

Termenul de criptografie este derivat din cuvintele grecesti "kryptos" cu semnificatia de `ascuns' si `graphein' cu semnificatia de `scris'. Criptografia se refera la studiul tehnicilor matematice, având ca scop transformarea datelor în forme neinteligibile (ascunderea continutului), prevenirea alterarii nedetectate sau prevenirea accesului neautorizat [34].

Istoria criptografiei se extinde în secole de la stravechiul Egipt la India, Mesopotamia, Babylon, Grecia pâna în era calculatorelor. De la Spartani la Iulius Caesar, de la cifrurile Vechiului Testament la cele Papale din secolul XIV, de la Mary, regina Scotiei la cifrurile razboiului civil al lui Abraham Lincoln, criptografia a fost parte a razboiului, diplomatiei si politicii.

Criptografia doreste sa asigure urmatoarele deziderate fundamentale pentru securitatea informatiei:

Confidentialitatea se defineste ca fiind protectia datelor în fata persoanelor neautorizate.
Integritatea datelor presupune nealterarea datelor de catre o entitate neautorizata. Pentru a asigura integritatea datelor trebuie sa fie detectata manipularea de date de catre o entitate neautorizata.
Autenticitatea presupune asigurarea unor comunicatii autentice. Cu alte cuvinte, doua entitati aflate într-un schimb de mesaje sa se poata identifica una pe cealalta. În prima faza, la initierea conexiunii, acest serviciu asigura ca cele doua entitati sunt autentice. În al doilea rând, autenticitatea presupune ca transferul de date între cele doua entitati sa nu fie interferat astfel încât o a treia entitate sa se legitimeze ca fiind una din ele.
Non-repudierea este un serviciu ce previne situatia în care o entitate refuza sa recunoasca actiuni anterioare. Când un mesaj este trimis, destinatarul poate demonstra ca mesajul primit este cel trimis de emitator.

Ceea ce urmeaza este o lista de termeni si concepte fundamentale folosite din criptografie.

Textul orginal al unui mesaj, înainte de a fi criptat este adeseori referit ca plaintext. Dupa criptare se numeste criptotext.
Un criptosistem este un sistem care este folosit pentru a transforma textul clar (plaintextul) într-o forma neinteligibila (criptotext) si viceversa.
Procesul de aplicare a unui criptosistem asupra unui text clar (plaintext) se numeste criptare.
Procesul invers criptarii, de recuperare a textului clar dintr-un criptotext, se numeste decriptare.
Criptanaliza reprezinta studiul metodelor de compromitere a schemelor criptografice. Un criptanalist (referit în mod popular ca fiind `spargator' de cifruri - engl. codebreaker), este orice persoana implicata în criptanaliza.
Criptografii si criptanalistii sunt adversari; fiecare încearca sa-l întreaca pe celalalt. Cele doua parti sunt angajate într-o batalie intelectuala fascinanta, unde miza poate fi foarte mare.

Din punctul de vedere al criptanalistului, problema se prezinta în trei variante principale:

Când are la dispozitie o cantitate de text cifrat si nici un fel de text clar este confruntat cu problema textului cifrat;
Când are la dispozitie o parte din textul clar si textul criptat corespunzator, problema este cunoscuta sub numele de problema textului clar cunoscut;
Când criptanalistul poate cripta bucati de text clar la propria sa alegere, problema este cunoscuta sub numele de problema textului clar ales.

Criptarea si decriptarea necesita folosirea unei informatii secrete, numita cheie. Pentru unele criptosisteme este folosita aceea si cheie pentru criptare si decriptare, pentru alte sisteme, cheile folosite pentru criptare si decriptare sunt diferite (criptografie cu chei publice).

În criptografia conventionala, numita si criptografie simetrica, o singura cheie este folosita pentru criptare si decriptare. Criptosistemul DES [26] (acronim engl. Data Encryption Standard) este exemplul unui astfel de criptosistem conventional. Figura de mai jos este o ilustratie a procesului conventional de criptare.

Dintre criptosistemele simetrice amintim, AES (acronim engl. Advanced Encryption Standard, cunoscut de asemenea sub numele de Rijndael) [27], BLOWFISH [31], SERPENT [3], IDEA [17]. Criptografia conventionala are beneficiile sale. Este foarte rapida. Este benefica pentru datele statice. Totusi, în ceea ce priveste transmiterea sigura a datelor, criptografia conventionala este deficitara din cauza dificultatii distribuirii cheii. Pentru o transmisie sigura de date între doua entitati, o cheie trebuie sa fie stabilita în prealabil folosind scheme de stabilire a cheii.

Problema distribuirii cheii a fost rezolvata de criptografia cu chei publice, concept introdus de Whitfield Diffie si Martin Hellman în anul 1975 [10]. Folosind criptografia cu cheie publica (criptografia asimetrica), se rezolva problema distribuirii cheilor prin faptul ca entitatile pot comunica pe un canal nesigur, fara a se întelege dinainte asupra unei chei. Un criptosistem cu cheie publica este un sistem criptografic ce foloseste parametri secreti ce nu sunt împartasiti între entitatile participante.

Fiecare entitate poseda un set de parametri secreti (respectiv cheia privata) si publica un alt set de parametri (respectiv cheia publica). Când Andrei vrea sa trimita un mesaj secret Ioanei, el va folosi cheia publica a Ioanei pentru a cripta mesajul. Ioana va folosi cheia ei privata pentru a decripta mesajul.

O aplicatie interesanta a criptografiei cu chei publice o reprezinta semnaturile digitale. Semnatura digitala, la fel ca semnatura de mâna, se bazeaza pe faptul ca e foarte greu sa se gaseasca doua persoane cu aceeasi semnatura. În fiecare zi, oamenii semneaza scrisori, cecuri si alte documente, demonstrând ca sunt de acord în ceea ce priveste continutul documentului. Cu ajutorul semnaturilor digitale, asiguram autenticitatea datelor.
Pentru a semna un mesaj, Ioana executa un calcul ce implica atât mesajul cât si cheia secreta. Outputul este numit semnatura digitala si este atasat la mesaj. Pentru a verifica semnatura, Andrei va face un calcul ce implica mesajul, semnatura atasata si cheia publica a Ioanei. Daca rezultatul este corect, conform unei relatii matematice specificate, atunci semnatura este autentica, altfel semnatura este falsa, sau mesajul a fost alterat.

În timp ce criptografia contemporana creste în diversitate, criptografia se bazeaza într-un mod fundamental pe probleme ce sunt dificil de rezolvat. Exista probleme dificile care devin simple daca se cunoaste o anumita informatie secreta. Cautarea unor noi scheme de criptare cu cheie publica, îmbunatatirea celor existente, demonstrarea securitatii continua cu pasi repezi. Numeroase standarde si infrastructuri ce implica criptografia sunt dezvoltate si testate. Produse de securitate sunt dezvoltate pentru a se adresa nevoilor de securitate ale societatii informationale.

Capitolul 2

Criptosisteme bazate pe problema factorizarii

Problema factorizarii întregilor Având un numar natural n, sa se gaseasca descompunerea sa în factori primi. Cu alte cuvinte, sa se exprime n ca p^e₁₁p^e₂₂¼p^e_k_k unde p_i sunt numere prime distincte, iar e_i ³ 1.

Securitatea unor tehnici de criptare ca RSA, Rabin sau Paillier depind de intractabilitatea problemei factorizarii. Problema este considerata grea pentru numere mari, însa recent algoritmii de factorizare au cunoscut îmbunatatiri considerabile, ajungându-se la punctul în care factorizarea unui întreg cu 100 de cifre zecimale sa fie usoara. Totusi, problema factorizarii întregilor ramâne dificila (pentru numere mai mari de 100 de cifre zecimale).

2.1 Criptosistemul RSA

Criptosistemul RSA [29] este cel mai cunoscut si mai folosit criptosistem cu chei publice. Inventatorii sai, Ron Rivest, Adi Shamir, Len Adleman au publicat acest criptosistem în anul 1977. În prezent, criptosistemul RSA este folosit în multe aplicatii comerciale. Fie ca este vorba de servere web si browsere (în vederea securizarii traficului web), sau de servicii E-mail (intimitate si autenticitate), sesiuni de logare la distanta, sau sisteme de plata prin card, criptosistemul RSA este folosit în aplicatii unde securitatea datelor digitale este vitala.

2.1.1 Descrierea criptosistemului RSA

La fel ca toate criptosistemele asimetrice, schema RSA foloseste o cheie publica si una privata. Cheia publica este necesara pentru criptare si va fi disponibila public, în timp ce cheia privata va fi detinuta doar de persoana ce primeste mesajul.

Algoritm 2.1 Criptosistemul RSA. Crearea cheilor

Fiecare entitate A îsi creeaza o cheie publica si o cheie privata corespunzatoare.

1. Se genereaza doua numere mari, aleatoare, prime (distincte) p si q.

2. Se calculeaza n = pq si f(n) = (p-1)(q-1).

3. Se alege aleator un întreg e, 1 < e < f(n) astfel încât cmmdc(e, f(n)) = 1.

4. Se foloseste algoritmul extins al lui Euclid pentru a gasi d, 1 < d < f(n),

astfel încât ed º 1 ( mod f(n) ).

5. Cheia publica este (e, n). Cheia privata este d.

Pentru criptare este folosita cheia publica, rezultând un criptotext dintr-un plaintext. Algoritmul (2.2) descrie procesul de criptare.

Algoritm 2.2 Criptosistemul RSA. Criptare

Fiecare entitate B cripteaza un mesaj M pentru A, mesaj pe care A îl va decripta.

B va face urmatoarele:

1. Se obtine cheia publica ce apartine lui A (optional, verifica autenticitatea).

2. Se codifica mesajul M ca o secventa de întregi din intervalul [0, n-1].

3. Se calculeaza c = M^e mod n .

4. Se trimite criptotextul c lui A.

Pentru a decodifica criptotextul este necesara cheia privata. Procesul decurge dupa cum urmeaza.

Algoritm 2.3 Criptosistemul RSA. Decriptare

Pentru a decripta c, A va face urmatoarele:

1. Se foloseste cheia privata d pentru a recupera M = c^d mod n .

Corectitudinea criptosistemului

Pentru a vedea acest lucru, trebuie sa întelegem de ce

M = (M^e)^d mod n,

unde M reprezinta mesajul, e si d reprezinta exponentii de criptare si decriptare, iar n este produsul pq. Reamintim ca d a fost ales astfel încât ed = 1 mod f(n). Prin urmare, exista un întreg k astfel încât de = 1 + kf(n) = 1+k(p-1)(q-1). Astfel,

(M^e)^d = M^de = M^{1+k(p-1)(q-1)} = M · M^k(p-1)(q-1)

Vom demonstra ca M^ed = M mod p. Vom considera doua cazuri (cazul M^ed = M mod q, analog):

a) p nu divide M.
Folosind teorema lui Fermat, avem M^p-1 º 1 (mod p). Rezulta ca
M^k(p-1)(q-1) º 1^k(q-1) (mod p) (deoarece a º b mod p Þ aⁿ º bⁿ mod p). Astfel, M · M^k(p-1)(q-1) º M mod p. Rezulta,

M^ed = M mod p.

b) p ÷ M
Rezulta p | M (M^ed-1-1) Þ M^ed º M mod p.
Analog M^ed º M mod q. Cum (p, q) = 1 rezulta ca,

M^ed = M mod pq.

Am folosit faptul ca daca a º b mod m si a º b mod m¢, iar (m, m¢)=1, atunci a º b mod mm¢.

--------------------------------------
Exemplu (Criptosistemul RSA)

Crearea cheilor. Entitate A alege p = 33769 q = 33851 si calculeaza n = pq = 1143114419 si f(n) = (p-1)(q-1) = 1143046800. A alege e = 39317 si folosind algoritmul extins al lui Euclid, gasim d = e^-1 mod f(n) = 111289853 astfel încât ed º 1 (mod f(n)). Cheia publica a lui A este reprezentata de perechea (n=1143114419, e=39317), iar cheia privata este d=111289853 .

Criptare. Pentru a cripta mesajul M = 4563289 , B foloseste un algoritm de exponentiere modulara cu scopul de a calcula

c = M^e mod n = 4563289³⁹³¹⁷ mod 1143114419 = 639193744

si îl trimite lui A.

Decriptare. Pentru a decripta c, A calculeaza

c^d mod n = 639193744^111289853 mod 1143114419 = 4563289.

--------------------------------------

2.1.2 Securitatea criptosistemului RSA

Securitatea RSA se bazeaza pe intractabilitatea problemei factorizarii. Gasirea unei metode simple de factorizare ar compromite în totalitate securitatea RSA. Având informa tii despre p si q, totul se reduce la rezolvarea sistemului:

ì
í
î

(p-1)(q-1)

f(n)

Alegerea apropiata a numerelor p si q conduce la o slabiciune a schemei RSA. În acest caz (cu p > q) vom avea (p-q)/2 un numar foarte mic, iar (p+q)/2 un numar foarte apropiat de Ön. Avem, de asemenea relatia, (p+q)²/4 - n = (p-q)²/n.
Atunci, pentru factorizarea lui n se testeaza toate numerele întregi x @ Ön pâna se gase ste unul astfel încât x² - n este patrat perfect; îl notam cu y² . Rezulta rela tiile p = x + y , q = x - y.

Atacul lui Wiener

Teorema 1 Fie p, q doua numere prime astfel încât q < p < 2q, n=pq, si fie e, d Î Z^*_f(n) astfel încât ed º 1 mod f(n). Daca 3d < n^1/4, atunci d poate fi calculat în timp polinomial determinist în raport cu log n, cunoscând doar n si e.

Daca exponentul de decriptare d satisface conditia mai sus mentionata, atunci atacul Wiener [36] va fi eficient pentru criptosistemul RSA.
Fractii continue --> Fie a, b numere naturale, b ¹ 0 . Aplicând algoritmul lui Euclid, obtinem dezvoltarea în fractie continua a lui [a/b] .

q₁·b + r₁ 0 < r₁ < b

q₂·r₁ + r₂ 0 < r₂ < r₁

r₁

q₃·r₂ + r₃ 0 < r₃ < r₂

. . .

(2.1)

r_k-2

q_k·r_k-1 + r_k 0 < r_k < r_k-1

r_k-1

q_k+1·r_k

Se verifica usor ca:

= q₁ +

q₂ +

+	: q_k + [1/( q_k+1)]

(2.2)

Vom spune ca [q₁, q₂ ¼q_k+1] este dezvoltarea în fractie continua a lui [a/b] . Consideram numerele naturale a_i, b_i date prin:

a₁

q₁, a₂ = q₁·q₂ + 1, a_i = q_i-1 ·a_i-1 + a_i-2,

(2.3)

b₁

1, b₂ = q₂, b_i = q_i ·b_i-1 + b_i-2, 3 £ i £ k+1

Atunci are loc relatia:

[q₁, q₂, ¼, q_i] =

a_i

b_i

, (a_i, b_i) = 1, pentru orice 1 £ i £ k+1

Tinând cont de observatiile anterioare, algoritmul Wiener poate fi detaliat:

Algoritm 2. 4 RSA. Atacul Wiener

i:=0;

repeta

i:=i + 1;

determina a_i, b_i, folosind relatiile (2. 1) (pentru a = e si b = n) si (2. 3);

l:=a_i;d:=b_i;

pâna când criteriu(l, d) = 1

unde

criteriu(l, d) =

ì
í
î

1, daca

ì
í
î

(x-1)(y-1)

ed-1

, are solutii întregi.

0, altfel

Solutiile sistemului, reprezinta p si q, respectiv factorizarea lui n.

Alte atacuri
Alta tehnica de a `sparge' RSA este determinarea radacinii de ordin e modulo n a lui c. Din moment ce c = M^e mod n, cea de-a e radacina a lui c mod n este chiar mesajul M. Acest atac, permite oricui sa recupereze mesajul criptat fara sa cunoasca exponentul de decriptare d. În cazuri speciale, în care mai multe mesaje relationate sunt criptate cu acelasi exponent mic, este posibil sa se recupereze mesajele.

Atacurile `cronometru' fac parte din alta clasa de atacuri, în sensul ca nu sunt îndreptate catre structura criptosistemului RSA, ci asupra felului în care este implementat RSA. Prin masurarea atenta a timpului necesar pentru a efectua operatii de decriptare, atacatorii sunt capabili sa gaseasca factorizarea cheilor RSA. Împotriva sistemelor vulnerabile, atacul este simplu de realizat si adeseori nu necesita decât criptotextul [16].
Recent, un nou atac de acest fel a fost descoperit. Atacul, ce poarta denumirea BPA (engl. Branch Prediction Analysis), poate colecta toti bitii cheii secrete într-o singura executie a unui proces RSA si permite rularea în paralel a unui proces de spionare (foarte atent scris - pentru mai multe detalii, cititorul poate consulta [1]).

Masuri preventive
Lungimea unei chei necesara pentru o transmisie RSA sigura este de 1024 biti. Cheile de lungime 512 biti nu mai sunt considerate sigure. Pentru mai multa securitate se pot folosi chei mai mari (2048 sau chiar 4096 biti). Datorita puterii de calcul actuale, criptarea si decriptarea unui mesaj cu o cheie de 4096 biti, nu mai este o problema. În practica, este imposibil de "spart" un mesaj encriptat cu o cheie de lungime 512 biti. Dar o organizatie ca NSA, ce detine supercalculatoare, poate "sparge" mesajul printr-un atac cu forta bruta, într-un timp rezonabil.

Cu scopul de a eficientiza procesul de criptare, suntem tentati sa alegem exponentul e mic (ex. e=3). Un astfel de exponent nu ar trebui sa fie folosit, daca mesajul criptat este trimis mai multor entitati. Exista pericolul ca un atacator sa poata recupera mesajul folosindu-se de Teorema Chineza a Resturilor. Ca masura preventiva, putem adauga la plaintext un sir generat aleator înainte de a face criptarea, independent pentru fiecare din mesajele pe care dorim sa le trimitem.

Similar cu observatiile de mai sus, alegerea unui exponent de decriptare d mic este riscanta. De aceea se recomanda alegerea lui d aproape de dimensiunea lui n.

Daca mesajul este mic sau predictibil, atacatorul poate recupera plaintextul din criptotextul c prin criptare succesiva de plaintexte pâna la obtinerea lui c. Preventiv, se poate folosi o tehnica de padare.

Concluzii asupra criptosistemului RSA
Criptosistemul RSA s-a dovedit a fi remarcabil de robust. De la inventarea sa, acum 3 decenii si pâna astazi, a fost cercetat si atacat, dar în ciuda acestui fapt, RSA a ramas un criptosistem sigur. Singurele atacuri cu rezultate practice sunt `atacurile cronometru', dar acest fapt nu rezulta din slabiciuni ale algoritmului de criptare, dar si mai mult, exista tehnici de protectie împotriva acestor atacuri.

RSA este un exponent de marca al criptografiei cu chei publice. Algoritmul este folosit pe scara larga si este disponibil gratuit (Licenta a expirat). Este inclus în sistemele de operare de catre Microsoft, Apple, Sun si Novell. Sub forma de implementari hardware, RSA este folosit pe telefoane securizate, placi de retea Ethernet si smartcard-uri. Este incorporat în protocoalele majore ale Internetului ca S/MIME, SSL, S/WAN. Cele mai securizate tranzactii pe internet folosesc SSL (Secure Socket Layer), care foloseste RSA.

2.2 Criptosistemul Rabin

Criptosistemul a fost publicat în anul 1979, de catre Michael O. Rabin [28]. Criptosistemul Rabin este o tehnica asimetrica de criptare, care la fel ca RSA, se bazeaza pe problema dificila a factorizarii. Criptosistemul Rabin este o alternativa buna la criptosistemul RSA.

2.2.1 Descrierea criptosistemului Rabin

Similar criptosistemului RSA, algoritmul de creare a cheilor genereaza doua numere prime p, q si calculeaza modulul n=pq. Cheia publica este n, iar cea privata este reprezentata de perechea (p, q).

Algoritm 2. 5 Criptosistemul Rabin. Crearea cheilor

Fiecare entitate A îsi creeaza o cheie publica si o cheie privata corespunzatoare;

1. Se genereaza doua numere mari, aleatoare, prime (distincte) p si q;

2. Se calculeaza n = pq;

3. Cheia publica este n. Cheia privata este (p, q).

Algoritmul de criptare specifica felul în care mesajul este criptat. Algoritmul de criptare este determinist si are la intrare cheia publica n=pq si genereaza ca output criptotextul c. A se observa ca algoritmul foloseste exponentiere modulara (ridicare la patrat), prin urmare este foarte eficient.

Algoritm 2. 6 Criptosistemul Rabin. Criptare

Fiecare entitate B cripteaza un mesaj M pentru A, mesaj pe care A îl va decripta;

B va face urmatoarele:

1. Se obtine cheia publica ce apar tine lui A (optional, verifica autenticitatea);

2. Se reprezinta mesajul ca un întreg din intervalul [0, n-1];

3. Se calculeaza c = M² mod n ;

4. Se trimite criptotextul c lui A.

Algoritmul de decriptare are la intrare cheia privata si criptotextul, iar ca output mesajul (plaintextul) M.

Algoritm 2. 7 Criptosistemul Rabin. Decriptare

Pentru a decripta c, A va face urmatoarele:

1. Se gasesc cele patru radacini patratice m₁, m₂, m₃, m₄ ale lui c modulo n;

2. Mesajul trimis de B este m₁, m₂, m₃, m₄ sau m₄.

A va decide care mesaj este M.

Gasirea radacinilor patratice

Propozitia 1 Data factorizarea lui n = pq în numere prime (distincte), ce au fost alese ca fiind congruente cu 3 (mod 4), atunci calcularea radacinilor patratice modulo n este o problema simpla.

Se foloseste algoritmul extins al lui Euclid pentru a gasi întregii a si b ce satisfac ap + bq = 1;
Se calculeaza r = c^(p+1)/4 mod p;
Se calculeaza s = c^(q+1)/4 mod q;
Se calculeaza x = (aps + bqr) mod n;
Se calculeaza y = (aps - bqr) mod n;
Cele patru radacini patratice ale lui c mod n sunt: ± x mod n, ± y mod n.

--------------------------------------
Exemplu (Criptosistemul Rabin)

Crearea cheilor. Entitate A alege p = 7 q = 1 si calculeaza n = pq = 77. Atunci (-3)7 + (2)11 = 1 astfel încât a=-3 si b=2.

Criptare. Fie mesajul M = 101₂ = 5₁₀ . Îl duplicam (procedeu descris în sectiunea imediat urmatoare) si obtinem M = 101101₂ = 45₁₀. Calculam c = M² mod 77 = 23.

Decriptare. Pentru a decripta c, A calculeaza r = 23² mod 7 = 4, s = 23³ mod 11 = 1, si

x = ((-3)·7 ·1 + 2 ·2 ·11 ·4) mod 77 = 67

y = ((-3)·7 ·1 - 2 ·2 ·11 ·4) mod 77 = 45

Acestea sunt doua dintre cele 4 radacini patratice. Celelate sunt (- x) mod 77 = 10, (- y) mod 77 = 32. În binar 67 = 1000011, 45 = 101101, 10 = 001010, si 32 = 100000. Numai 45 are redundanta corecta, ca urmare acesta este rezultatul decriptarii.
--------------------------------------

2.2.2 Securitatea criptosistemului Rabin

Problema determinarii radacinii patratice, a fost demonstrata ca fiind la fel de grea ca problema factorizarii întregilor. Astfel criptosistemul Rabin va ramane sigur pâna când se va gasi o solutie generala la problema factorizarii. Totusi, un atacator poate `sparge' sistemul prin folosirea atacurilor de plaintext ales. Un astfel de atac poate fi descris dupa cum urmeaza. Atacatorul alege aleator un întreg M din Z^*_n si calculeaza c = M² mod n. Atacatorul trimite c lui A, care decripteaza c si returneaza un plaintext y. Din moment ce A nu cunoaste M, plaintextul y nu e neaparat la fel ca M. Cu probabilitatea [1/2], y ¹ ±M mod n, caz în care cmmdc(M-y, n) este unul din factorii primi ai lui n. Daca y º ±M mod n, atunci atacul este repetat cu un nou M.

Pentru a distinge mesajul valid dintre celelalte trei radacini patratice e necesar sa adaugam informatie redundanta în mesaj. În general, se sugereaza replicarea ultimilor 64 de biti din mesaj (sau sa se foloseasca 0-uri ca ultimii 64 biti). În astfel de cazuri, sistemul va fi programat sa întoarca mesajul cu redundanta corecta. Astfel se poate evita si atacul descris mai sus.

Masuri preventive
Criptosistemul Rabin este bazat pe dificultatea factorizarii modulului n, acesta fiind cel mai important parametru de securitate. Modulii de dimensiune mai mare ca 1024 biti sunt considerati a fi siguri.

Concluzii asupra criptosistemului Rabin
Desi acest criptosistem este functional si a fost dezvoltat imediat dupa aparitia RSA, nu s-a bucurat de popularitatea acestuia din urma. Faptul ca sunt patru posibile decriptari corespondente plaintextului, a contribuit la aceasta popularitate scazuta. Desi aceasta din urma problema poate fi usor rezolvata, consideram ca este greu de crezut ca pe viitor, criptosistemul Rabin va juca un rol mai important pe scena criptografiei cu chei publice.

2.3 Criptosistemul Paillier

Criptosistemul Paillier [24] este un algoritm asimetric probabilist, inventat de Pascal Paillier în anul 1999. Problema calcularii claselor celui de-al n reziduu este considerata a fi intractabila. Aceasta problema sta la baza sistemului criptografic Paillier. Schema sa are proprietati homomorfice aditive, în sensul ca date fiind cheile publice si criptarile mesajelor m₁ si m₂, se poate calcula criptarea lui m₁+m₂.

2.3.1 Preliminarii matematice

Definitia 1 Un element x Î Z^*_n² se numeste reziduu de ordin n, daca exista un alt element y Î Z^*_n² astfel încât

x = yⁿ mod n²

Fie g Î Z^*_n² si e_g o functie, e_g: Z_n × Z^*_n² ® Z^*_n² definita prin

e_g(x, y) = g^x yⁿ mod n²

Vom prezenta mai întâi câteva rezultate care ne vor ajuta la demonstrarea corectitudinii criptosistemului.

Lema 1 Daca ordinul lui g este un multiplu de n atunci e_g este bijectiva.

Notam cu B mul timea elementelor de ordin multiplu de n.

Definitia 2 Fie g Î B . Dat w Î Z^*_n², vom numi n clasa reziduala a lui w, fata de g, unicul x Î Z_n pentru care exista y Î Z^*_n, astfel încât e_g(x, y) = w.

Criptosistemul Paillier se bazeaza pe urmatoarele doua proprieta ti (notam cu l functia Carmichael):

Pentru orice w continut în Z^*_n², congruenta urmatoare este adevarata

w^l(n) º 1 mod n

(2.4)
Pentru orice w continut în Z^*_n², congruenta urmatoare este adevarata

w^nl(n) º 1 mod n²

(2.5)

2.3.2 Descrierea criptosistemului Paillier

Similar criptosistemului RSA, algoritmul de creare a cheilor genereaza doua numere prime p, q si calculeaza n=pq, dar se lucreaza în modulo n². Cheia publica este (n, g), iar cheia privata este (l, m).

Algoritm 2. 8 Criptosistemul Paillier. Crearea cheilor

Fiecare entitate A îsi creeaza o cheie publica si o cheie privata corespunzatoare;

1. Se genereaza doua numere mari, aleatoare, prime (distincte) p si q;

2. Se calculeaza n = pq si l = cmmmc(p-1, q-1);

3. Se alege aleator un întreg g, unde g Î Z^*_n²;

4. Se garanteaza ca n divide ord(g) prin analiza existentei inversului modular

multiplicativ m = (L(g^l mod n²))^-1 mod n unde functia L este definita

astfel: L(u) = (u-1)/n;

5. Cheia publica este (n, g). Cheia privata este (l, m).

Algoritmul urmator specifica felul în care se cripteaza un mesaj m, ce satisface relatia m < n. O valoare r este aleasa aleator din Z^*_n, iar criptotextul c este calculat dupa cum urmeaza.

Algoritm 2. 9 Criptosistemul Paillier. Criptare

Fiecare entitate B cripteaza un mesaj m pentru A, mesaj pe care A îl va decripta;

B va face urmatoarele:

1. Se obtine cheia publica ce apar tine lui A (optional, verifica autenticitatea);

2. Fie m mesajul ce va fi criptat, unde m Î Z_n;

3. Se alege aleator r, unde r Î Z^*_n;

4. Se calculeaza c = g^m · rⁿ mod n²;

5. Se trimite criptotextul c lui A.

functia L(u) = (u-1)/n este folosita pentru decriptare. Procesul de decriptare decurge în felul urmator.

Algoritm 2. 10 Criptosistemul Paillier. Decriptare

Pentru a decripta c, A va face urmatoarele:

1. Se calculeaza m = L(c^l mod n²) · m mod n .

Corectitudinea criptosistemului

Corectitudinea criptosistemului se bazeaza pe o demonstratie greu de urmarit. Ca atare, nu va fi tratata aici! Daca cititorul este interesat de aceasta demonstratie este rugat sa trimita un mesaj la ed.thyme at gmail.com.

--------------------------------------
Exemplu (Criptosistemul Paillier)

Crearea cheilor. Entitate A alege p = 163 q = 151 si calculeaza n = pq = 24613, l = 4050. A alege g = 2 si calculeaza m = 16767. Cheia publica este (24613, 2). Cheia privata este (4050, 16767).

Criptare. Fie mesajul m = 27 . B alege r = 29440 si calculeaza

c = 2²⁷ ·29440²⁴⁶¹³ mod 24613² = 266878841.

Decriptare. Pentru a decripta c, A calculeaza

m = L(266878841⁴⁰⁵⁰ mod 24613²) · 16767 mod 24613 = 27.

--------------------------------------

Proprietati homomorfice
O caracteristica notabila a criptosistemului Paillier sunt proprietatile sale homomorfice. Cum functia de criptare este aditiv homomorfica, au loc urmatoarele identitati:

Adunare homomorfica de plaintexte

Produsul a doua criptotexte se va decodifica în suma plaintextelor corespunzatoare,

D(E(m₁, r₁) ·E(m₂, r₂) mod n²) = m₁ + m₂ mod n.

Produsul unui criptotext cu g^m₂, m₂ reprezentând un plaintext, se va decodifica în suma plaintextelor corespunzatoare,

D(E(m₁, r₁) ·g^m₂ mod n²) = m₁ + m₂ mod n.

Înmultire homomorfica de plaintexte

Un criptotext ridcat la puterea unui alt plaintext, se va decodifica în produsul plaintextelor corespunzatoare,

D(E(m₁, r₁)^m₂ mod n²) = m₁ ·m₂ mod n.

D(E(m₂, r₂)^m₁ mod n²) = m₁ ·m₂ mod n.

În general, un criptotext ridicat la o putere constanta k se va decodifica în produsul dintre constanta si plaintext,

D(E(m₁, r₁)^k mod n²) = k·m₁ mod n.

2.3.3 Securitatea criptosistemului Paillier

Criptosistemul descris mai sus este sigur în ceea ce priveste atacurile cu plaintext ales. Abilitatea de a distinge cu succes criptotextul este echivalenta cu abilitatea de calculare a claselor celui de-al n reziduu. Acest lucru este considerat a fi intractabil. Datorita proprietatilor homomorfice mentionate mai sus, sistemul este considerat a fi maleabil, si prin urmare nu se bucura de cea mai mare securitate împotriva atacurilor adaptive cu plaintext ales. De obicei, în criptografie, proprietatea de maleabilitate nu este vazuta ca un avantaj, dar în unele aplicatii cum ar fi vot secret sau criptosisteme partajate, aceasta proprietate este necesara.

Concluzii asupra criptosistemului Paillier
Acest criptosistem este folosit în general în aplicatiile de vot electronic. Sa consideram un vot binar simplu (1-pentru, 0-împotriva). Cei m votanti îsi aleg optiunea. Fiecare votant îsi cripteaza votul înainte de a-l trimite. Sistemul calculeaza produsul celor m voturi, îl decripteaza si obtine o valoare n ce reprezinta suma tuturor voturilor. Astfel, se cunoaste ca n dintre votanti au votat `pentru' si m-n au votat împotriva.
O alta aplicatie a acestui criptosistem sunt banii electronici, implicit abilitatea de a cumpara un produs online, fara ca vânzatorul sa cunoasca numarul de card, respectiv identitatea cumparatorului. Scopul este de a asigura validitatea `monezii' si în acelasi timp sa nu dezvaluie identitatea persoanei cu care este asociata.

Capitolul 3

Criptosisteme bazate pe problema rucsacului

Problema rucsacului Având o multime {b₁, b₂, . ., b_n} de întregi pozitivi, numita secventa rucsac, si un întreg pozitiv s, sa se determine daca exista o submultime de elemente b_j ale caror suma sa fie s. Echivalent, sa se determine daca exista sau nu x_i Î {0, 1}, 1 £ i £ n, astfel încât åⁿ_i=1b_i x_i = s.

Ideea principala este sa selectam o instanta a problemei ce este usor de rezolvat si sa o mascam într-o instanta dificila. Instanta usoara poate sa deserveasca ca o cheie privata, iar instanta grea sa fie cheia publica. Criptosistemul Merkle-Hellman a fost gasit ca fiind nesigur, însa merita sa fie examinat deoarece demonstreaza cum o problema NP-completa poate fi folosita în criptografia cu chei publice.

3.1 Criptosistemul Merkle-Hellman

Criptosistemul Merkle-Hellman [19] a fost printre primele criptosisteme cu cheie publica. Inventatorii sai, Ralph Merkle si Martin Hellman au publicat acest criptosistem în anul 1978. Acest algoritm putea fi folosit doar pentru criptare, desi mai târziu Adi Shamir a adaptat sistemul pentru semnaturi digitale.
Securitatea acestui algoritm se bazeaza pe problema rucsacului, problema ce este NP-completa. Schema de criptare Merkle-Hellman mascheaza o instanta usor de rezolvat a problemei rucsacului si anume, gasirea unei submultimi de suma data într-o secventa supercrescatoare.

Definitia 3 O secventa supercrescatoare este o secventa (b₁, b₂, ¼, b_n) de întregi pozitivi cu proprietatea b_i > å^i-1_j=1b_j, oricare ar fi i, 2 £ i £ n.

Problema gasirii unei submultimi de suma data în cazul secventelor supercrescatoare este rezolvata de urmatorul algoritm.

Algoritm 3.1 Gasirea unei submultimi de suma data într-o secventa supercrescatoare

INTRARE: o secventa supercrescatoare (b₁, b₂, ¼, b_n) si un întreg s ce reprezinta

suma elementelor unei submultimi apartinând secventei;

IESIRE: (x₁, x₂, ¼, x_n), x_i Î {0, 1}, astfel încât åⁿ_i=1b_i x_i = s;

1. i=n;

2. Cât timp i ³ 1

2. 1 Daca s ³ b_i Atunci x_i=1 si s = s - b_i; Altfel x_i=0;

2. 2 i = i - 1;

3. Daca s=0 Atunci Întoarce (x₁, x₂, ¼, x_n);

Altfel Întoarce `Nu este solutie'.

Solutia la problema rucsacului folosind secvente supercrescatoare este usor de gasit. Se ia s si se compara cu cel mai mare numar din secventa (în cazul nostru, acesta este ultimul numar din secventa). Daca s e mai mic decât numarul respectiv, atunci numarul nu este în submultime. Daca s e mai mare sau egal decât numarul respectiv, atunci numarul este în submultime. Se scade din s, valoarea gasita si se trece la urmatorul numar din secventa. Se repeta pasii pâna la terminare. Daca s=0 la final, atunci avem o solutie. Altfel, nu avem solutie.

3.1.1 Descrierea criptosistemului Merkle-Hellman

Cheia privata este o secventa supercrescatoare. Cheia publica este o secventa rucsac arbitrara cu aceea si solutie. Merkle si Hellman au dezvoltat o tehnica de a transforma instanta usoara (problema rucsacului folosind secven te supercrescatoare) într-o instanta grea (problema rucsacului folosind secvente rucsac arbitrare). Au realizat acest lucru prin aritmetica modulara. Practic, se ia o secventa supercrescatoare si se înmultesc toate valorile cu un numar ales aleator W, modulo M. Modulul este un numar mai mare decât suma tuturor elementelor din secventa. Elementul W nu trebuie sa aiba factori comuni cu modulul M. În cele ce urmeaza vom vedea ca este usor sa criptam folosind secventa rucsac arbitrara, iar cu ajutorul cheii private este usor sa decriptam criptotextul. Fara cheia privata, problema recuperarii plaintextului din criptotext pare foarte dificila.

Algoritm 3.2 Criptosistemul Merkle-Hellman. Crearea cheilor

1. Se alege n ca parametru de sistem;

2. Fiecare entitate A va parcurge pasii 3-7;

3. Se alege o secventa supercrescatoare (b₁, b₂, ¼, b_n) si modulul M astfel

încât M > åⁿ_i=1b_i;

4. Se alege aleator un întreg W, 1 £ W £ M, astfel încât cmmdc(W, M)=1;

5. Se alege aleator o permutare p a întregilor {1, 2, ¼, n};

6. Se calculeaza a_i = W b_p(i) mod M, cu i = 1, 2, ¼, n;

7. Cheia publica este (a₁, a₂, ¼, a_n).

Cheia privata este (p, M, W, (b₁, b₂, ¼, b_n)).

Pentru a cripta un mesaj binar, se împarte mesajul în blocuri. Lungimea blocurilor este egala cu numarul de valori din secventa rucsac. Cifra 1 va indica faptul ca elementul din secventa va fi prezent în suma totala, 0 indica absenta (m_i Î {0, 1}). Algoritmul este urmatorul:

Algoritm 3.3 Criptosistemul Merkle-Hellman. Criptare

Fiecare entitate B cripteaza un mesaj m pentru A, mesaj pe care A îl va decripta;

B va face urmatoarele:

1. Se obtine cheia publica ce apartine lui A (optional, verifica autenticitatea);

2. Se reprezinta mesajul m ca un sir binar de lungime n, m = m₁m₂¼m_n;

3. Se calculeaza c = åⁿ_i=1m_i a_i;

4. Se trimite criptotextul c lui A.

Pentru decodificare este necesara cheia privata: secventa rucsac supercrescatoare, valorile lui W si M folosite pentru transformarea în secventa rucsac arbitrara. Apoi, se determina W^-1. Se înmulteste criptotextul c cu W^-1 modulo M, iar apoi folosind secventa rucsac supercrescatoare se recupereaza plaintextul. Algoritmul este urmatorul:

Algoritm 3.4 Criptosistemul Merkle-Hellman. Decriptare

Pentru a decripta c, A va face urmatoarele:

1. Se calculeaza d=W^-1c mod M;

2. Cu ajutorul Algoritmului (3.1), gasesc întregii r₁, r₂, ¼, r_n Î {0, 1}, astfel

încât d = åⁿ_i=1r_i b_i;

3. Bitii mesajului sunt m_i = r_p(i), i = 1, 2, ¼, n.

Corectitudinea criptosistemului

Algoritmul de decriptare (3. 4) permite recuperarea mesajului original deoarece,

d º W^-1 c mod M º W^-1

n
å
i=1

m_ia_i mod M º

n
å
i=1

m_ib_p(i) mod M.

Avem 0 £ d £ M, d = åⁿ_i=1 m_ib_p(i) mod M , iar din solutia la problema gasirii unei submultimi de suma data într-o secventa supercrescatoare (pasul 2) vor rezulta bitii mesajului, dupa aplicarea permutarii.

--------------------------------------
Exemplu (Criptosistemul Merkle-Hellman)

Crearea cheilor. Fie n=5. Entitatea A alege secventa rucsac supercrescatoare (1, 2, 4, 8, 16), M = 31, W = 30, si permutarea p = {1, 2, 3, 4, 5}. Cheia publica a lui A este secventa rucsac (30, 29, 27, 23, 15).
Cheia privata este (p, M, W, (1, 2, 4, 8, 16)).

Criptare. Fie mesajul m = 11010₂. B calculeaza

c = 30 + 29 + 23 = 82

Decriptare. Pentru a decripta c, A calculeaza d = W^-1c mod M = 11.

11 = 1·r₁ + 2·r₂ +4·r₃ +8·r₄ +16·r₅

Gasim r=(1, 1, 0, 1, 0). Dupa aplicarea permutarii rezulta mesajul m = 11010.
--------------------------------------

3.1.2 Securitatea criptosistemului Merkle-Hellman

Definitia 4 Fie S = a₁, a₂, ¼, a_n secventa rucsac. Densitatea lui S este

d = n
max{log₂ a_i | 1 £ i £ n}

Din nefericire, criptosistemul Merkle-Hellman este nesigur. A fost `spart' câtiva ani mai târziu de la publicare, în anul 1983, de catre Adi Shamir [33]. Ideea de baza este ca un `rucsac arbitrar', ce este derivat dintr-o secventa supercrescatoare, nu este cu adevarat un rucsac arbitrar. De fapt este un caz foarte special al rucsacului. Problema poate fi rezolvata daca gasim un vector mic într-o latice. Intuitiv, o latice reprezinta multimea combinatiilor linare a unor vectori constanti dati. Gasirea unui vector mic într-o latice este cunoscuta ca fiind grea, dar care este usoara în multe cazuri. Faimosul algoritm L³ [18] poate fi folosit pentru reducerea laticilor si compromiterea unor sisteme ca Merkle-Hellman. Algoritmul L³ este eficient daca vectorul rucsac are densitatea mai mica de 0. 9408 [7]. Acest lucru este semnificativ deoarece altfel ar fi mai multe submultimi cu acceasi suma, caz în care criptotextele nu ar fi decriptate în mod unic.

De asemenea, se cunoaste un algoritm de timp polinomial ce compromite schema Merkle-Hellman. Având o `multime rucsac', acest algoritm gaseste o pereche de întregi (U¢, M¢), astfel încât U¢/M¢ e apropiat de U/M (unde W si M sunt componente ale cheii private si U = W^-1 mod M. ), iar întregii b^¢_i = U¢a_i mod M, 1 £ i £ n formeaza o secventa supercrescatoare. Aceasta secventa poate fi folosita de un atacator în locul secventei (b₁, b₂, ¼, b_n) pentru a decripta mesajul (pentru mai multe detalii, a se vedea [2]).

Masuri preventive
În implementari practice, un `vector rucsac' ar trebui sa contina cel putin 250 de elemente. Dimensiunea fiecarui termen din secventa supercrescatoare trebuie sa varieze între 200 si 400 biti, iar modulul între 100 si 200 biti. Cu asemenea `rucsaci' este inutil un atac prin forta bruta. Daca un calculator ar putea încerca un milion de posibilitati pe secunda, atunci încercarea tuturor posibilitatilor ar dura 10⁴⁶ ani.

Concluzii asupra criptosistemului Merkle-Hellman
Majoritatea criptosistemelor rucsac sunt compromise, foarte putine rezistând tuturor atacurilor. Unul dintre cele mai atractive criptosisteme rucsac este schema Chor-Rivest [5]. Totusi, multi oameni sunt refractari în folosirea unor astfel de sisteme din moment ce termenul de 'rucsac' continua sa fie asociat cu termenul `compromis'. Cercetarea în domeniul criptosistemelor rucsac continua atât datorita vitezei mari de criptare cât si din motivul diversificarii criptosistemelor.

Capitolul 4

Criptosisteme bazate pe problema logaritmului discret

Problema logaritmului discret Fie p numar prim si a, b Î Z_p, b ¹ 0. Sa se determine a Î Z_p-1 astfel încât a^a º b (mod p). Acest întreg a (daca exista) este unic si se noteaza log_ab.

Securitatea unor tehnici de criptare ca ElGamal, DSS sau ECC se bazeaza pe intractabilitatea problemei logaritmului discret. Nu exista un algoritm eficient, în timp polinomial, care sa rezolve aceasta problema. Însa daca toti divizorii primi ai lui p-1 sunt mici, problema este rezolvata eficient de algoritmul Pohlig-Hellman [25]. Pentru siguranta, p se alege de minim 512 biti, iar p-1 sa aiba cel putin un divizor prim `mare' (160 biti). Utilitatea acestei cerinte rezida în faptul ca, desi este foarte dificil de calculat un logaritm discret, operatia inversa (de exponentiere) este foarte simpla.

4.1 Criptosistemul ElGamal

Criptosistemul ElGamal a fost propus în anul 1985, de catre Taher ElGamal [11]. Algoritmul ElGamal poate fi folosit atât pentru criptare cât si pentru semnaturi digitale. Securitatea acestui criptosistem se bazeaza pe intractabilitatea problemei logaritmului discret. Este un sistem de criptare probabilist, în sensul ca unui plaintext îi pot corespunde mai multe criptotexte (relatie `one-to-many'). Un dezavantaj al criptosistemului ElGamal este expansiunea mesajului cu un factor 2. Cu alte cuvinte, criptotextul este de doua ori mai mare fata de textul clar. Criptosistemul ElGamal este folosit în programul gratuit GNU Privacy Guard si în versiuni recente ale programului PGP. În continuare, iata un algoritm eficient pentru gasirea unui generator a unui grup ciclic (preluat din [2]). Vom folosi acest algoritm în procesul de generare al cheilor în cadrul algoritmului de criptare ElGamal.

Algoritm 4.1 Gasirea unui generator al unui grup ciclic

INTRARE: un grup ciclic G cu ordinul n, si descompunerea în factori primi

n=p^e₁₁p^e₂₂¼p^e_k_k;

IESIRE: un generator a a lui G;

1. Se alege un element aleator a din G;

2. Pentru i=1, ¼, k;

2.1 Se calculeaza b=a^n/p_i;

2.2 Daca b=1 Atunci Salt la pasul 1;

3. Întoarce (a).

4.1.1 Descrierea criptosistemului ElGamal

În prima instanta se genereaza un numar prim mare p. Cheia privata este un numar întreg a ales aleator astfel încât 1 £ a £ p-2. Cheia publica este reprezentata de trei valori (p, a, b). Algoritmul de creare a cheilor este urmatorul:

Algoritm 4.2 Criptosistemul ElGamal. Crearea cheilor

Fiecare entitate A îsi creeaza o cheie publica si o cheie privata corespunzatoare.

1. Se genereaza un numar prim mare p si un generator a al grupului

multiplicativ Z^*_p (Algoritmul 4.1);

2. Se selecteaza un numar întreg a, 1 £ a £ p-2 si calculeaza b = a^a mod p;

3. Cheia publica este (p, a, b). Cheia privata este a.

Pentru criptare se alege aleator un numar întreg astfel încât k, 1 £ k £ p-2. Criptotextul este reprezentat de perechea (g, d)=(a^k mod p, m ·b^k mod p).

Algoritm 4.3 Criptosistemul ElGamal. Criptare

Fiecare entitate B cripteaza un mesaj m pentru A, mesaj pe care A îl va decripta;

B va face urmatoarele:

1. Se obtine cheia publica ce apartine lui A (p, a, b) (optional, verifica

autenticitatea);

2. Se reprezinta mesajul m ca un întreg din intervalul [0, p-1];

3. Se selecteaza aleator un numar întreg k, 1 £ k £ p-2;

4. Se calculeaza g = a^k mod p si d = m ·b^k mod p;

4. Trimite criptotextul c = (g, d) lui A.

Pentru a decodifica criptotextul este necesara cheia privata. Procesul decurge dupa cum urmeaza.

Algoritm 4.4 criptosistemul ElGamal. Decriptare

Pentru a decripta c, A va face urmatoarele:

1. Se foloseste cheia privata a pentru a calcula y=g^p-1-a mod p;

( Obs. g^p-1-a = g^-a = a^-ak = b^-k)

2. Plaintextul trimis de B este m = (y·d mod p).

Corectitudinea criptosistemului

Algoritmul de decriptare (4.4) permite recuperarea mesajului original deoarece

g^-a · d º a^-akma^ak º m mod p.

--------------------------------------
Exemplu (Criptosistemul ElGamal)

Crearea cheilor. Entitatea A alege numarul prim p=2357 si generatorul a = 2 din Z^*₂₃₅₇. A alege cheia privata a=1751 si calculeaza:

b = a^a mod p = 2¹⁷⁵¹ mod 2357 = 1185.

Cheia publica a lui A este (2357, 2, 1185).

Criptare. Fie mesajul m = 2035. B alege k=1520 si calculeaza

g = 2¹⁵²⁰ mod 2357 = 1430

d = 2035 ·1185¹⁵²⁰ mod 2357 = 697.

Criptotextul este c = (1430, 697).

Decriptare. Pentru a decripta c, A calculeaza

y = g^p-1-a mod p = 1430⁶⁰⁵ mod 2357 = 872

iar pentru a recupera plaintextul, calculeaza

m = 872 · 697 mod 2357 = 2035.

--------------------------------------

4.1.2 Securitatea criptosistemului ElGamal

Sunt destui algoritmi ce încearca sa rezolve problema logaritmului discret. Rata lor de succes depinde foarte mult de parametrii de intrare. În continuare vom prezenta un astfel de algoritm.

Algoritmul Pohlig-Hellman [25]
Fie n = p₁^e₁p₂^e₂¼p_r^e_r descompunerea în factori primi a lui n. Daca x = log_ab trebuie sa determinam x_i = x mod p^e_i_i pentru 1 £ i £ r, iar apoi se aplica algoritmul lui Gauss pentru a recupera x mod n.

Algoritm 4.5 Algoritmul Pohlig-Hellman pentru calcularea logaritmului discret

INTRARE: un generator a al grupului ciclic G de ordin n si un element b Î G;

IESIRE: logaritmul discret x = log_ab;

1. Se gaseste descompunerea în factori primi a lui n = p₁^e₁p₂^e₂¼p_r^e_r;

2. Pentru i = 1, ¼, r;

(Calculeaza x_i = l₀+l₁p_i+¼+ l_{e_i}