Metoda Curbelor Eliptice

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 ε (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 ε 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 {0,1728}, 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 ε (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 :

φ:C|L→E cu φ(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 LenstraAlgoritmul lui Lenstra functioneaza astfel: pentru inceput alegem

aleator elemente a€Z\N, P0=(x0,y0)€(Z\N)2 si determinam o valoare b care

apartine lui (Z\N) 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(Z\

p) ca o curba eliptica definita prin aceasta ecuatie modulo p si avand G(N)= ∏p\

N Ea,b(Z\p). Omomorfismele βp:G(N)→G(p) sunt proiectii naturale.

Daca deducem ca G(p)’=G(p)\{0} este o parte afina a lui G(p),

atunci G(N)’=∏p\NG(p)’ este complementul lui Up\NKerf(β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 Z\N 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≠1. 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*46597757852200185432645607430767781

92897*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 DEC\VAX11\80.

In cadrul proiectului ECMNET s–au gasit urmatorii factori:

digits factor from B1 sigma date who

66 709601635082267320966424084955776789770864725643996885415676682297 3466+1 110000000 1875377824 06 Apr 2005 B. Dodson

62 31069150378873790895208046895771360949463293546412105951449429 22034+1 11e7 1507467457 10 Apr 2005 B. Dodson

59 20131492120828919814484857298874674155298711142397769181347 10233-1 260000000 4114600819 20 Feb 2005 B. Dodson

57 105778944142118900777500898708378586145093313765798058097 371937-1 11e6 20538780 22 Apr 2005 P. Ochem

56 12577428828773105721352890258033044293734071019770385547 10064811804113-1 5e7 3294558376 12 Apr 2005 P. Ochem

54140183614482450346632384931984512181340021597814186079

21083-1 43000000 426275289 28 Jan 2005 K. Aoki

54 126524320109965088424895868811 7272+1 43e6 2895810102 21 Apr 2005 B. Dodson

796346209735189444854017

54 110995096534055033775812456877810354806490499839538741

31683+1 11e7 3941580871 03 May 2005 J. Becker

51 285808992196770201430795577666066511096880150440101

HP300(95) 43e6 2976576632 20 Mar 2005 A. Michon

51 155137816977180947152785562601502526330318743274151

21105-1 43000000 2895414225 09 May 2005 K. Aoki