Definitie 1 Se numeste criptosistem este un tuplu (P,C,K,E,D)

• P este multimea finita a mesajelor originale.

• C este multimea mesajelor criptate.

• K este multimea finita a cheilor de criptare.

• pentru orice k ∈ K, exista ek ∈ E si dk ∈ D. E se numeste spatiulfunctiilor de criptare, iar D este spatiul functiilor de decriptare.

• dk(ek(w)) = w, pentru orice k ∈ K si pentru orice mesaj original w.

Se numeste criptosistem simetric un criptosistem ın care cheile de criptare,respectiv de decriptare sunt identice, sau se deduc imediat una din alta.

Criptanaliza se ocupa cu gasirea cheilor de decriptare, sau a chilor decriptare, sau cel putin cu producerea unei metode prin care sa se obtinainformatii despre mesajele criptate. Pot fi disponibile urmatoarele tipuri deinformatii

(CO) unele (aleator) mesaje criptate (cryptotext only).

(KP) unele (aleator) mesaje originale si mesajele criptate corespunzatoare(known plaintext).

(CP) un mesaj original ales si criptotextul corespunzator (chosen plaintext).

(CK) un criptotext ales si mesajul original corespunzator (chosen cryptotext).

1 Criptosisteme clasice

1.1 Criptosistemul afin

Pentru a putea folosi rezultatele de teoria numerelor, textele si simbolurilesunt codate ca numere si clase de resturi. Daca se doreste criptarea a Msimboluri, se pot folosi clasele de resturi modulo M.

Un mesaj simbol i (adica o clasa de resturi modulo M din sistemul declase de resturi pozitiv) este criptat astfel

ek1(i) = (ai+ b) mod M,

1

unde a, b sunt numere ıntregi, gcd(a,M) = 1. Cheia de criptare este

k1 = (a, b),

iar cheia de decriptare este

k2 = (c, b), c = a−1 mod M.

Functia de decriptare este

dk2(j) = c(j − b) mod M.

Situatia particulara cu a = 1 se numeste criptosistem CAESAR.

1.2 Criptosistemul Hill

S i ın acest caz imbolurile sunt codate clasele de resturi modulo M. Un mesajeste un d−vector format din d clase de resturi modulo M,

i = (i1, · · · , id).

Cheia de criptare este o d × d matrice H care are inversa K modulo M .Functia de criptare este

ek(i) = iH mod M,

iar functia de decriptare este

dk(j) = jK mod M.

Clasele de resturi sunt considerate ın sistemul pozitiv de clase de resturi.

1.3 Criptosistemul afin-Hill

Pentru a putea folosi rezultatele de teoria numerelor, textele si simbolurilesunt codate ca numere si clase de resturi. Daca se doreste criptarea a Msimboluri, se pot folosi clasele de resturi modulo M. Cheia de criptare este

k1 = (H, b),

iar cheia de decriptare este

k2 = (K, b), K = H−1 mod M.

2

Functia de criptare este

ek1(i) = (iH + b) mod M,

unde a, b sunt numere ıntregi, gcd(a,M) = 1. Functia de decriptare este

dk2(j) = (j − b)K mod M.

Situatia particulara cu H = Id se numeste criptosistem VIGENERE.

2 RSA

Cheia secreta k2 = (p, q, b) unde p, q sunt doua numere prime mari p, qde lungime aproximativ egala si un numar ıntreg b (numi exponent de de-criptare) cu proprietatea

gcd(b, φ(p, q)) = gcd(b, (p− 1)(q − 1)) = 1.

Cheia publica k1 = (n, a), unde n = p · q, iar a (exponentul de criptare) esteıntregul

ab ≡ 1 mod φ(n).

Functia de criptare este

ek1(w) = wa mod n,

iar functia de decriptare este

ek2(w) = cb mod n

si0 ≤ w ≤ n− 1.

Lema 2 x ≡ y mod n daca si numai daca au loc ambele relatii x ≡ y mod psi x ≡ y mod q.

Constructie RSA

• Se genereaza aleator numerele prime p si q de lungime dorita.

• Se calculeaza n = p · q si se calculeaza φ(n) = (p− 1)(q − 1).

3

• Se determina b aleator ın intervalul 1 ≤ b ≤ φ(n) − 1 astfel ıncatgcd(b, φ(n)) = 1, generand numere aleator ın acest interval si calculandgcd.

• Se calculeaza a = b−1 mod φ(n).

• Se publica k1 = (n, a).

Verificare decriptare

Daca gcd(w, n) = 1, cu teorema Euler

cb ≡ (wa)b = wab = w1+lφ(n) = w(wφ(n))l ≡ w · 1 = w mod n.

Daca gcd(w, n) 6= 1, avem urmatoarele trei situatii

• w = 0. Atuncicb ≡ (wa)b = 0b = 0 mod n.

• p/w, dar w 6= 0. Atunci w = pt, gcd(q, t) = 1. Atunci

cb ≡ (wa)b ≡ w mod p.

Pe de alta parte, cu teorema lui Fermat, avem

wab = w1+lφ(n) = w(wφ(n))l = w(wq−1)l(p−1) ≡ w · 1 = w mod q.

Folosind Lema rezulta ca

cb ≡ (wa)b ≡ w mod n.

• q/w, dar w 6= 0. Se trateaza similar cu situatia precedenta.

3 Criptosistemul Elgamal

Se poate defini ın orice grup finit G = (A, ·, 1) care are proprietatea ca ıngrupul ciclic < a >⊂ G, logaritmul discret loga este dificil de calculat.

Grupul G poate fi, spre exemplu, Z∗p, mai general F∗pn , ın particular F∗2nsi curbe eliptice peste corpuri finite.

• Cheia publica este tripletul k1 = (G, a, b), unde b = ay.

4

• Cheia secreta este k2 = y. Se observa ca cheia publica contine informatiidespre cheia privata deoarece y = logab, dar logaritmul discret este greude calculat.

• Se alege x arbitrar, 0 ≤ x ≤ l − 1, unde l este ordinul lui a. Daca nudorim sa pulicam l, sau nu se cunoaste, putem ınlocui l, spre exemplu,cu numarul de elemente al lui G, numar ce are ca factor pe l (conformteoremei lui Lagrange). Functia de criptare este

ek1(w, x) = (ax, w · bx) = (c1, c2).

• Functia de decriptare este

dk2(c1, c2) = c2 · c−y1 .

• Se verifica imediat ca

dk2(ax, w · bx) = w · bx · (ax)−y = w · axy · a−xy = w.

Spre exemplu, ın grupul comutativ Z∗p, p prim, se considera a o radacinaprimitiva modulo p. p trebuie ales astfel ıncat p − 1 sa aiba un factor primmare astfel ıncat logaritmul discret sa nu poata fi usor calculat.

1. Se aleg aleator q numar prim mare si un numar mai mic r care poatefi factorizat.

2. Daca 2qr + 1 este prim, atunci

p← 2qr + 1.

In acest caz p− 1 are factorul prim q mare. Altfel se revine la pasul 1.

3. Se alege aleator a ın intervalul 1 ≤ a ≤ p− 1.

4. Se testeaza cu criteriul lui Lucas daca a este rada cina primitiva modulop. Factorii primi ai lui p− 1, de care avem nevoie, sunt 2, q si factoriiprimi cunoscuti ai lui r.

5. Daca a este radacina primitiva modulo p, se alege aleator y ın intervalul1 ≤ y < p, se returneaza p, a, y si STOP. Altfel, se revine la pasul 3.

5

4 Criptosistemul Menzes-Vanstone (bazat pe

curbe eliptice)

• Cheia publica este tripletul k1 = (E,α, β), unde E este o curba elipticapeste corpul finit Zp (p > 3), α este un generator al unui subgrup al luiE, iar β = aα.

• Cheia secreta este k2 = a.

• Functia de criptare este

ek1((w1, w2), x) = (y0, y1, y2),

undey0 = xα, y1 = c1w1 mod p, y2 = c2w2 mod p,

x aleator, iar c1, c2 sunt obtinute reprezentand xβ = (c1, c2) punct pecurba eliptica ın sistemul rezidual pozitiv. x trebuie ales astfel ıncatc1, c2 6≡ 0 mod p.

• Functia de decriptare este

dk2(y0, y1, y2) = (y1c−11 mod p, y2c

−12 mod p).

• Se verifica imediat ca

ay0 = a(xα) = (ax)α = x(aα) = xβ = (c1, c2).

5 Criptosistemul NTRU

Sistemul simetric de clase de resturi

m par: −m−22, · · · , 0, 1, · · · , m

2.

m impar: −m−12, · · · , 0, 1, · · · , m−1

2.

Fie a(x) ∈ Zp[X],

a(x) =k∑i=0

aixi (ai ∈ {0, 1, · · · , p− 1}).

6

Polinomul obtinut din a(x) reducandu-i coeficientii ın sistemul simetric mod-ulo p este polinomul a′(x) ∈ Z[X], care satisface

a′(x) mod p = a(x)

si ai carui coeficienti se afla ın intervalul

−p2< ai ≤

p

2.

Se considera functiile secrete f, g ∈ Z[X], de grad ≤ n − 1. Notam cuf(p), g(p) ∈ Zp[X]/(xn − 1) polinoamele obtinute din f si g reducandu-lecoeficientii ın sistemul simetric de clase de resturi modulo p, iar cu f(q), g(q) ∈Zq[X]/(xn − 1) polinoamele obtinute din f si g prin reducerea coeficientilorın sistemul simetric de clase de resturi modulo q. Se cere, de asemenea, saexiste polinoamele Fp(x) ∈ Zp[X], Fq(x) ∈ Zq[X], de grad cel mult n − 1astfel ıncat

Fp(x)f(p)(x) ≡ 1 mod xn − 1

siFq(x)f(q)(x) ≡ 1 mod xn − 1.

Se calculeazah(x) ≡ Fq(x)g(q)(x) mod xn − 1,

h ∈ Zq[X]/(xn − 1).

• Cheia publica este (n, p, q, h(x)).

• Cheia privata este (f, g).

• Un mesaj este un polinom w(x) ∈ Zp[X], de grad cel mult n − 1. Inparticular w este reprezentat utilizand sistemul simetric de clase deresturi modulo p. Se alege polinomul aleator (cheia efemera) φ(x) degrad maxim n− 1.

Functia de criptare este

c(x) ≡ pφ(q)(x)h(x) + w(q)(x) mod xn − 1.

• Functia de decriptare este

a(x) ≡ f(q)(x)c(x) mod xn − 1,

w′(x) ≡ Fp(x)a(p)(x) mod xn − 1.

7

Notatii

• Fie

R = Z[X]/(xn − 1), Rq = Zq[X]/(xn − 1), Rp = Zp[X]/(xn − 1).

• Daca a, b ∈ R, definim convolutia polinoamelor a si b prin formula

a(x) ? b(x) = c(x), ck =∑

i+j≡(k mod n), 0≤i,j≤n−1

aibk−i.

Daca a, b ∈ Rq, atunci convolutia polinoamelor a si b se definestefolosind aceeasi formula, reducand modulo q coeficientii ck ai polino-mului c.

• Pentru d1, d2 numere ıntregi pozitive, definim

P(d1, d2) = {a ∈ R : polinomul a(x) are d1 coeficienti egali cu 1,d2 coeficienti egali cu − 1 si restul coeficientilor egali cu 0}.

Exemplu de criptosistem NTRU

• Cheia publica este (n, p, q, d, h) N, p numere prime, (p, q) = (n, q) = 1,q > (6d+ 1)p.

• Cheia privata este (f, g), unde f ∈ P(d + 1, d este inversabil ın Zp[X]si ın Zq[X], iar g ∈ P(d, d). Se calculeaza

Fq = f−1 ın Rq, Fp = f−1 ın Rp, h = Fq ? g.

• Se alege m(x) ∈ Rp si cheia efemera φ(x) ∈ P(d, d). Mesajul criptateste

c(x) ≡ pφ ? h+m(mod q).

• Pentru decriptare se calculeaza

a(x) ≡ f ? c(mod q),

se reduc coeficientii lui a ın sistemul simetric modulo p si se calculeaza

m ≡ Fp(x) ? a(mod p).

8