Metoda curbelor eliptice - criptografia si descompunerea in factori primi

Introducere

Criptografia reprezinta studiul tehnicilor matematice cu privire la securitatea informatiei cum ar fi confidentialitatea, integritatea datelor, autenticitatea entitatilor si originea autenticitatii datelor.
In anul 1985, Neal Koblitz si Victor Muler, au introdus , independent, sistemul de criptare cu ajutorul curbelor eliptice ca a alternativa la sistemul de criptare cu cheie publica. Securitatea (siguranta) sa consta in dificultatea
problemei logaritmului discret a curbelor eliptice care permite generarea celei mai mari puteri “per bit” dintre toate sistemele de criptare cu cheie publica cunoscute. Nivelul de securitate este determinat de dimensiunea si structura grupului de puncte rationale de pe curba eliptica definit de un camp finit.
Problema logaritmului discret la curbele eliptice: (ECDLP
Fie E o curba eliptica peste un camp finit F_q. Presupunem P un punct ce apartine curbei E (F_q) si fie Q un punct in <P>. Trebuie sa se gaseasca un intreg t astfel incat Q = [t] P
Se considera in mod unanim ca problema logaritmului discret a curbelor eliptice este greu de rezolvat in cazul in care punctul P are un ordin primalitate mare.
Metode cunoscute pentru a rezolva ECDLP sunt
• Algoritmul Pohlig-Hellman ( care reduce problema la subgrupuri de de ordine de primalitate)
• Metoda lui Shank “Baby-step-giant-step”
• Metoda lui Pollard
• Atacul Menezes-Okamoto-Vanstone (MOV).
• Atacurile asupra curbelor eliptice considerate anomalii ( de exemplu curbele eliptice peste F_p care au p puncte ) create de Semaev, Satoh-Araki si Smart.
• Atacul Frey-Rueck.
In prezent exista doar trei clase de sisteme de criptare cu cheie publica care sunt considerate a fi atat eficiente cat si sigure. Sunt clasificate mai jos in functie de problema matematica pe care sunt bazate
• Sistemul de factorizare a numerelor intregi.
• Sistemul logaritmului discret.
• Sistemul curbelor eliptice.

Descompunerea in factori primi

Problema descompunerii in factori primi consta in: fiind dat un numar intreg pozitiv , sa se scrie ca un produs de numere prime.De exemplu: fiind dat numarul 45 , descompunerea lui in factori primi este: 32 *5.Descompunerea este intotdeauna unica conform teoremei fundamentale aritmetice.
Fiind date doua numere prime mari, este usor sa le gasesti produsul. Insa, fiind dat produsul lor este mai dificil sa le gasesti factorii. Acest lucru este relevant pentru multe sisteme moderne in criptografie. Daca o metoda rapida pentru problema descompunerii in factori primi este gasita , atunci numeroase sisteme in criptografie vor fi ‘sparte’, inclusiv alogoritmul RSA, cu cheie publica si generatorul de numere aleatoare Blum Blum Shub.
Chiar daca descompunerea in factori primi este o metoda de a ‘sparge’ aceste sisteme exista si alte metode de a le sparge fara a fi folosita descompunerea. Astfel este posibil ca problema descompunerii in factori primi sa fie grea dar sistemele sa fie totusi sparte rapid. O exceptie este generatorul Blum Blum Shub. A fost demonstrat faptul ca aceste este la fel de dificil ca si descompunerea in factori primi. Nu exista nici o metoda de a-l sparge fara a rezolva rapid descompunerea in factori primi.
Principalele metode dezvoltata pana astazi pentru descompunerea in factori primi a numerelor sunt: ECM(Elliptic Curve Method), MPQS (Multiple Polynomial Quadratic Sieve), NFS (Number Field Sieve).

Ce este o curba eliptica?
O curba eliptica E definita pe un camp finit Fp, unde p>3, poate fi data sub forma:
E(Fp): y2=x3+a*x+b , a,b e (Fp) (1)
impreuna cu un punct special numit punct de infinit.Ecuatia este numita “eliptica” deoarece este folosita in calcularea lungimilor de arc ale elipselor.
Asociate curbei eliptice sunt doua entitati importante discriminantul:
?= -16 (4a3+27b2) (2)
?j-invariant:
j=1728(4a3)/? , unde ??0. (3)
Lema1 Fiind dat j0 e Fp exista o curba eliptica E definita pe Fp astfel incat j(E)= j0.
O curba eliptica cu un j-invariabil , j0, dat, se poate construi usor. Consideram j0 care nu apartine , aceste cazuri speciale sunt de asemenea usor de rezolvat. Fie k= j0 1728- j0), j0€(Fp) atunci ecuatia:
E: y2=x3+3kx+2k. (4
determina o curba eliptica cu j-invariant j(E)= j0 .
Teorema 1: Curbele eliptice izomorfe au acelasi j-invariant.
Teorema 2: (HASSE) Fie # E(Fp) numarul punctelor pe curba eliptica E(Fp). Daca # E(Fp) = p+1-t , atunci | t |<= 2*sqrt(p).
Definitia 1: (Torsiunea) Fiind data E: y2=x3+a*x+b , a,b e (Fp) , torsiunea elipsei in punctul c este curba eliptica daca de Ec: y2=x3+a*c2*x+b*c3, unde c€(Fp).
Teorema 3: Fie E definita pe (Fp) si ordinul sau # E(Fp) =p+1-t.
Ordinul torsiunii este dat de:
# Ec(Fp*) = p + 1 – t , daca c este patrat perfect in (Fp) (6)
= p + 1 + t, in caz contrar
Teorema 4: (Atkin-Morain) Fie p un numar prim astfel incat 4*p=t+D*s2 (7), oricare ar fi t,s € Z. Atunci exista o curba eliptica E definita pe (Fp) astfel incat # E(Fp) = p + 1 – t.
Metoda de generare a curbelor eliptice poarta numele de Complex Multiplcation (CM) . Aceasta metoda consta in
• Fiind dat un numar prim p se gaseste cel mai mic D in (7) si t asociat acestuia.
• Ordinele curbelor eliptice care pot fi construite este # E(Fp) = p + 1 ± t. Se verfica daca unul din ordine are o factorizare admisibila (prin factorizare admisibila se intelege un numar prim sau aproape prim). In cazul in care nu este indeplinita aceasta conditie se cauta un alt D si un t corespunzator acestuia. Se repeta acest pas pana cand se gaseste o factorizare admisibila.
• Se construieste o clasa polinomiala Hs(x) utilizand formulele corespunzatoatre.
• Se gaseste un j0 € Hs(x) (mod p). Acest j0 este j-invariantul al curbei ce trebuie construita.
• Fie k= j0 / (1728 - j0 ) (mod p) si curba va fi:
? E: y2=x3+3*k*x+2*k
• Se verifica ordinul curbei. Daca este nu este p + 1 – t atunci se construieste torsiunea folosind un c € (Fp) la alegere.

Acest algoritm de generare a curbelor eliptice a fost testat pe un Pentium II la 450- Mhz. S-a ales t = 2*v + 1 si s = 2*w + 1, unde v,w € Z. Numerele prime gasite sunt de forma p = v 2 + v + ( w2 + w ) D + (D+1)/4 (8) , iar D = 3 (mod 4).


Aceste diagrame arata activitatea metodei in functie de clasele de numere obtinute.
Curbele eliptice sunt folosite in demonstrarea ultimei teoreme a lui Fermat si au numeroase aplicatii in criptografie.
Intre punctele unei curbe eliptice se pot defini operatii binare intr-un mod natural, ceea ce face ca aceste puncte sa formeze un grup abelian.
Curbele eliptice tipice pentru multimea numerelor reale sunt date prin ecuatiile
y²=x³-x si y²=x³-x+1.

Curbele eliptice pot fi definite peste orice multime K,definitia formala a unei curbe eliptice spune ca acestea sunt ecuatii algebrice proiective non-singulare peste K de tipul 1.Daca caracteristica lui K nu este 2 sau 3,curba eliptica peste K poate fi scrisa sub forma: y²=x³-px-q ,unde p si q apartin lui K , iar ecuatia nu are nici o radacina dubla.
Toate punctele (x,y) care satisfac relatia data au pe x si y elemente ale lui K.Punctele de pe curba ale caror coordonate apartin lui K sunt numite K-puncte rationale.
Prin adaugarea unui punct la infinit obtinem versiunea proiectiva a acestei curbe.Proprietatea matematica care face ca aceste curbe sa fie folosite in criptografie este aceea ca: luand doua puncte distincte de pe curba,dreapta care trece prin ele va intersecta curba in al treilea punct(deoarece avem o ecuatie cubica).
Fie P si Q doua puncte distincte de pe curba.P are coordonatele (x1,y1). –P are coordonatele (x1,-y1) ,deoarece curba eliptica este simetrica fata de axa OX. Astfel, cel de-al treilea punct de pe curba este P+Q. In acest fel se dovedeste ca aceasta corespondenta satisface proprietatile algebrice uzuale pe care le asociem numerelor intregi.
In termeni matematici : putem defini un grup abelian finit din punctele de pe curba, O fiind punctul la infinit. In particular , daca lasam ca punctele P si Q sa coincida , putem defini P+P ,notat 2P.Extinzand ideea, putem defini kP ( pentru orice intreg k ) si ordinul lui P ,ca fiind cel mai mic intreg k astfel incat kP=O (punctul la infinit ) .

Grupul poate fi descris si algebric ,nu doar geometric. Fiind data curba : y²=x³-px-q peste multimea K (ale carei caracteristici nu sunt 2 sau 3), si punctele P(xp,yp) , Q(xq,yq) pe curba , presupunem mai intai ca xq?xp. Fie s yp-yq)|(xp-xq). Din moment ce K este o multime , s este bine definit. Apoi se poate defini R=P+Q (R(xr,yr)) prin :
xr=s²-xp-xq, yr=-yp+s(xp-xr).
Daca xp=xq , atunci avem doua optiuni :
a) daca yp=-yq ,atunci suma este definita ca 0.Astfel, punctul invers al fiecarui punct de pe curba este simetricul fata de axa OX.
b) Daca yp=yq?0, atunci R=P+P=2P , R(xr,yr) date prin :
s=(3xp²-p)|(2yp)
xr=s²-2xp
yr=-yp+s(xp-xr).
Daca yp=yq=0 atunci P+P=0.
Teorema lui Mordell-Weil afirma ca daca multimea K este multimea numerelor rationale, atunci grupul K-puncte rationale este finit.
Este relativ usor sa determini torsiunea subgrupului E(K), insa nici un algoritm general nu este cunoscut pentru a-i afla rangul. O formula pentru acest punct este data de ipoteza la Birch si Swinnerton-Dyer.
Demonstratia recenta a ultimei teoreme a lui Fermat gaseste solutia unui caz special al presupunerii lui Taniyama-Shimura, folosind curbele eliptice peste multimea numerlor rationale.
Daca multimea K este o multime de numere complexe , atunci orice curba eliptica poate fi parametrizata printr-o functie eliptica. Mai precis, pentru fiecare curba eliptica E exista o latice L si o functie eliptica Wierstrass specifica astfel incat :
f:C|L?E cu f(z)=C(?(z), ?’(z)) este un grup izomorf
al suprafetelor Riemann.

Metoda curbelor eliptice

Metoda curbelor eliptice este un algoritm probabilistic rapid pentru descompunerea numerelor intregi care implica folosirea curbelor eliptice. El a fost inventat in 1985 de Hendrik Lenstra Jr Aceasta metoda a fost cel mai bun algoritm pentru descompunerea numerelor intregi pana ce NFS a fost descoperit. Metoda este inca buna pentru a gasi factori a caror dimensiune nu depaseste 20 de cifre(64 de biti), deoarece timpul algoritmului depinde de dimensiunea factorului p.
ECM este o imbunatatire a vechii metode de descompunere Pollard p-1. In metoda lui Pollard s-a presupus ca un numar dat n are un divizor prim p daca p-1 are numai factori primi mici. Apoi , prin mica teorema a lui Fermat (ae=1 mod p, unde p-1 divide pe e si p nu divide pe a), luand pe e ca un produs de numere prime mici ridicate la puteri mici si a sa fie un rest aleator mod n , putem descompune numarul n prin aflarea celui mai mare divizor comun a lui n si an-1 , asa cum alti divizori q ai lui n nu au proprietatea ca q-1 sa divida pe e. Oricum noi nu vom putea descompune pe n daca n nu are un factor prim p cu p-1 “fin”.
Metoda curbelor eliptice a lui Lenstra trece peste acest obstacol considerand un grup de curbe eliptice aleatoare peste grupul finit Zn ,mai degraba decat a considera grupul multiplicativ a lui Zn care are intotdeauna ordinul n-1.Numarul de ordine al grupului de curbe eliptice aleatoate peste Zn este intre p si 2p ceea ce este convenabil pentru anumite curbe eliptice.
ECM pentru un numar n functioneaza astfel
- se alege o curba eliptica peste Z si un punct A pe ea. Apoi , se considera legea grupului pe aceasta curba mod n(acest lucru este posibil deoarece toate resturile obtinute mod n au invers care poate fi gasit folosind algoritmul lui Euclid);
- se calculeaza eA in acest grup, unde e este un produs de numere mici ridicate la puteri mici la fel ca in metoda Pollard p-1. Pentru eficienta se poate da un numar prim;
- din fericire , eA este un element 0 al grupului de curbe eliptice in Zn si nu in Zq pentru un alt divizor prim q a lui n(la fel ca in metoda Pollard p-1 nu este de preferat ca ambele grupuri sa aiba numarul de ordine un divizor a lui e);
- apoi sa afla un divizor a lui n prin gasirea celui mai mare divizor comun dintre prima coordonata a lui A si n , coordonata va fi 0 in Zq ;
- daca nu merge algoritmul , se va incerca o alta curba si un alt punct.

Factorizarea

Metoda curbelor eliptice propusa de Lenstra este o generalizare a asa-numitului (p-1) algoritm de factorizare a lui Pollard.
Algoritmul lui Lenstra
Algoritmul lui Lenstra functioneaza astfel: pentru inceput alegem aleator elemente a€ZN, P0=(x0,y0)€(ZN)2 si determinam o valoare b care apartine lui (ZN) astfel incat y02=x03+ax0+b mod N.
In putine cazuri vom avea gcd(4a3+27b2, N)?1. Apoi vom gasi un divizor netrivial al lui N si putem opri algoritmul sau altfel:N divide 4a3+27b2 , ceea ce inseamna ca trebuie sa incepem din nou cu alegerea aleatoare a valorilor a,x0,y0.Daca gcd(4a3+27b2, N)=1 consideram ecuatia y2=x3+ax+b.
Pentru fiecare divizor prim a lui N, vom defini grupul G(p)= Ea,b(Zp) ca o curba eliptica definita prin aceasta ecuatie modulo p si avand G(N)= ?pN Ea,b(Zp). Omomorfismele ßp:G(N)?G(p) sunt proiectii naturale.
Daca deducem ca G(p)’=G(p) este o parte afina a lui G(p), atunci G(N)’=?pNG(p)’ este complementul lui UpNKerf(ßp). Punctele lui G(N)’ pot fi reprezentate prin perechi (x,y) de intregi care satisfac ecuatia aleasa modulo N.
Astfel, am construit deja un punct P0=(x0,y0) a lui G(N)’.Folosind principiul general al algoritmului de factorizare prezentat anterior, vom calcula multiplul Q(B)* P0 (pentru o alegere potrivita a lui B). Aceste lucru se poate face in O(log(Q(B))) pasi prin dublare repetata si adunare.
Grupul permite sa adaugam: P1 si P2, punctul P3= P1+ P2 fiind dat de formula:
x3=?2-x1-x2 , y3=?(x1-x3)-y1, unde ?=(y2-y1)/(x2-x1), daca x1?x2 si ?=(3x12+a)/(2y1) daca P1 = P2.
Singura problema in efectuarea acestei operatii in ZN este calculul elementelor inverse. Aceste elemente , daca exista in Z/N, pot fi calculate folosind algoritmul lui Euclid pentru a calcula gcd-ul dintre elementul ce trebuie inversat si N. Daca gcd=1 , inversul poate fi calculat si putem continua algoritmul.
Cazul exceptional este atunci cand gcd este un numar d . Daca d diferit de N , suntem in cazul norocos pentru ca am gasit un divizor al lui N. Daca una din curbele eliptice G(p) are un ordin ce divide Q(B), un caz exceptional oricum apare in timpul calculului lui Q(B)* P0, deoarece atunci Q(B)* P0 nu este un element din G(N)’.
Daca nu gasim un caz norocos nu suntem complet pierduti , deoarece putem incepe din nou cu o noua alegere aleatoare a parametrilor a0,x0,y0 astfel incat curbele eliptice G(p) sa aiba alte ordine.
O parte draguta a alogoritmului de factorizare folosind metoda curbelor eliptice este aceea ca ele pot fi usor puse in paralel , pentru ca putem lasa multe calculatoare sa factorizeze acelasi numar N folosind curbe eliptice diferite.

CONCLUZII

1.Complexitatea algoritmului depinde este O(exp(c(ln(p)ln(ln(p)))1/2)(ln(n))2), unde c este aproximativ 2 (valoarea lui este constanta) , n este numarul ce trebuie descompus, p este un factor nontrivial al lui n. Este un timp sub-exponential care depinde de lungimea factorului p.
2.Proiectul ECMNET ,inceput in 1998 ,pentru a gasi factori mari folosind ECM a avut succes,gasindu-se factori cu 50 de cifre(166 de biti) si mai mult.
Cel mai mare factor prim gasit folosind ECM are 54 de cifre(180 de biti) si este: 484061254276878368125726870789180231995964870094916937, adica (643-1)4*2+1 si a fost gasit de Nick Lygeros si Michael Mizony cu programul GMP-ECM al lui Paul Zimmermann in decembrie 1999.
3.In 1995 a fost descoperita descompunerea numarului lui Fermat F10=220+1 de 309 cifre(1025 biti).
F10=45592577*6487031809*4659775785220018543264560743076778192897*p252, unde 4659 . 92897 are 40 de cifre.Descompunerea a luat 240
Mips-ani.Un Mips-an este multimea de descompuneri ce pot fi facute intr-un an de un singur DECVAX1180.

In cadrul proiectului ECMNET s–au gasit urmatorii factori:

• digits factor from B1 sigma date who
66 709601635082267320966424084955776789
770864725643996885415676682297 3466+1 110000000 1875377824 06 Apr 2005 B. Dodson
62 3106915037887379089520804
6895771360949463293546412105951449429 22034+1 11e7 1507467457 10 Apr 2005 B. Dodson
59 2013149212082891981448485729887467415
5298711142397769181347 10233-1 260000000 4114600819 20 Feb 2005 B. Dodson
57 10577894414211890077750089870837858614
5093313765798058097 371937-1 11e6 20538780 22 Apr 2005 P. Ochem
56 125774288287731057213528902580330442937
34071019770385547 10064811804113-1 5e7 3294558376 12 Apr 2005 P. Ochem
54 140183614482450346632384931984
512181340021597814186079 21083-1 43000000 426275289 28 Jan 2005 K. Aoki
54 126524320109965088424895868811
796346209735189444854017 7272+1 43e6 2895810102 21 Apr 2005 B. Dodson
54 11099509653405503377581245687781
0354806490499839538741 31683+1 11e7 3941580871 03 May 2005 J. Becker
51 285808992196770201430795577666066
511096880150440101 HP300(95) 43e6 2976576632 20 Mar 2005 A. Michon
51 155137816977180947152785562601502
526330318743274151 21105-1 43000000 2895414225 09 May 2005 K. Aoki