Rónyai Lajos

Elliptikus görbék - a geometriától a titkos kommunikációig

16. ábra

pEE_pE_pp

Az E_p görbe pontjain (ideértjük -t is) értelmes a művelet. Bevezetünk egy rövidítést: legyen Q az E_p görbe tetszőleges pontja. Jelölje kQ a Q pont k-szorosát, azaz a görbe pontját, ahol a kifejezésben Q éppen k-szor szerepel. A korábban taglalt műveleti szabályokból könnyen következik, hogy ha k₁ és k₂ két egész, akkor k₁(k₂Q) = k₂(k₁Q) = (k₁k₂)Q.

Az első, a könnyű feladat a következő: adott egy E : y² = x³ - ax + b elliptikus görbe, egy p prímszám, az E_p egy Q = (u,v) pontja és egy k egész szám, határozzuk meg a kQ pontot. Ez a feladat valóban gyorsan (kevés művelettel) megoldható még akkor is, ha k nagy, pl. 100-jegyű egész. Az ilyen roppant nagy k kizárja, hogy sorban egyesével számítsuk a Q,2Q,3Q,...,kQ pontokat. Ez ugyanis a jelenlegi leggyorsabb számítógépen is sokkal több időt igényelne, mint a Föld kora (ami kb. 4,5 milliárd év). A hatékony módszer működését egy példával érzékeltetjük: a 20Q pontot a 19 pontösszeadás helyett 5-tel is megkaphatjuk, ha rendre a , , , , pontokat számítjuk. Az itt bemutatott duplázós ötlet elképesztően régi, már az i. e. 1650 táján keletkezett egyiptomi Rhind-papiruszon is szerepel, mégpedig egészek szorzásával kapcsolatban.

A nehéz feladat neve diszkrét logaritmus-feladat, bizonyos értelemben az előző fordítottja. Ismét adott az E : y² = x³ - ax + b elliptikus görbe, a p prímszám, továbbá az E_p véges görbe Q és R pontjai. Olyan k egészet keresünk (ha van egyáltalán), amelyre kQ=R teljesül. Ahhoz, hogy ez tényleg nehéz legyen, meg kell követelnünk, hogy a p prímszám nagy legyen, és azt is, hogy az E_p görbe N_p pontszámának legyen nagy prímosztója. Itt a nagy jelentése függ az elérni kívánt biztonsági szinttől. Azt is elvárjuk, hogy az E_p ne legyen túlságosan speciális. Nem jó például, ha N_p = p + 1, mert az ilyen véges görbék (ún. szuperszinguláris görbék) esetében a diszkrét logaritmus-feladat sokkal könnyebben megoldható, mint általában. Vannak olyan egyszerűbb, például üzleti alkalmazások, amelyek 60-80 jegyű prímekkel működnek. A komolyabb biztonsági igényű területeken (nemzetbiztonság, honvédelem) nagyobb prímekre van szükség.