[Prethodna tema]   [Sljedeća tema]

6.4. Izbor parametara kriptosustava

Dva su osnovna koraka kod izbora parametara za kriptosustav zasnovan na eliptičkim krivuljama: Kod izbora polja, dvije su osnovne mogućnosti: ili je q = p prost broj ili q = 2m potencija broja 2. Ako su p i 2m približno iste veličine, ova dva izbora pružaju istu razinu sigurnosti.

Među poljima Fp, da bi se minimiziralo vrijeme potrebno za modularno množenje, preporuča se da p ima oblik 2k +- c za neki mali prirodni broj c (npr. Mersenneovi prosti brojevi oblika 2k - 1, 2160 + 7, 2255 + 95, i sl.).

Kod polja karakteristike 2, osim broja elemenata, moramo odabrati i način reprezentacije elemenata. Najčešće se koriste trinomijalne i optimalne normalne baze. Kao što smo ranije napomenuli, izbor takvih baza omogućuje efikasniju implementaciju. No, takve baze ne postoje za svako konačno polje karakteristike 2, pa i to utječe na izbor polja. Neki popularni izbori su npr. 2163, 2191, 2239 i 2431.


Kod izbora eliptičke krivulje trebamo paziti da problem diskretnog logaritma bude "težak". Kako smo već više puta napomenuli, ECDLP je, prema svemu što vam je danas poznato, vrlo težak problem. Međutim, postoje tipovi eliptičkih krivulja kod kojih je taj problem nešto (ali čak puno) lakši. Zato takve krivulje treba izbjegavati. Situacija je vrlo slična kao kod kriptosustava koji svoju sigurnost zasnivaju na teškoći faktorizacije velikih prirodnih brojeva (npr. RSA ili Rabinov). I tamo je tvrdnja da je broj oblika pq, gdje su p i q veliki prosti brojevi, teško rastaviti na faktore točna samo ako se p i q odaberu pažljivo (npr. p i q ne smiju biti jako bliski; brojevi p - 1 i q - 1 moraju imati barem jedan veliki prosti faktor).

Navest ćemo sada tipove eliptičkih krivulja koje treba izbjegavati:

Vidimo da je lako odlučiti da li je konkretna eliptička krivulja dobra za primjenu u kriptografiji ukoliko znamo red grupe E(Fq).


Primjer: Navest ćemo jedan primjer koji zadovoljava sve gore navedene savjete i zahtjeve na izbor polja i eliptičke krivulje. Neka je krivulja E zadana jednadžbom

y2 = x3 + x + 1010685925500572430206879608558642904226772615919

nad poljem E(Fp), gdje je p = 2160 + 7. Tada je #E(Fp) = 1461501637330902918203683038630093524408650319587. Može se dokazati (npr. metodom dokazivanja prostosti pomoću eliptičkih krivulja!) da su brojevi p i #E(Fp) prosti.



Zadatci:

  1. Pronađite barem jednu anomalnu i barem jednu supersingularnu eliptičku krivulju nad F17.

  2. Pronađite barem jednu neanomalnu eliptičku krivulju E nad F23 sa svojstvom da je #E(F23) prost broj.



[Prethodna tema]   [Sljedeća tema]
Web stranica seminara Andrej Dujella - osobna stranica