Rónyai Lajos

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

Az Amerikai Egyesült Államok Nemzeti Szabványügyi és Technológiai Intézete (NIST) digitális aláírás képzésére vonatkozó 2000. januári szabványában több véges elliptikus görbét is javasol a titkos kommunikáció céljaira. Ezek egyike a P-192 jelű görbe: E : y² = x³ - 3x + b, ahol
b = 2455155546008943817740293915197451784769108058161191238065, a prímszám pedig az 58-jegyű
p = 6277101735386680763835789423207666416083908700390324961279. Az E_p pontjainak száma
N_p = 6277101735386680763835789423176059013767194773182842284081 maga is prím.

A diszkrét logaritmus-feladat az a matematikai rejtvény, amely a megoldásának nehézsége miatt alkalmasnak látszik arra, hogy segítségével a titkot elrejthessük a kandi kíváncsiskodók elől. Mai tudásunk szerint a diszkrét logaritmus számítása rendkívül időigényes feladat. Ilyen értelmű nehézségét viszont sajnos nem tudjuk matematikai szigorúsággal bizonyítani. Azt mondhatjuk ugyanakkor, hogy igen sok és komoly erőfeszítés ellenére sem ismert olyan módszer, amely hatékonyan és kellően általánosan meg tudna birkózni vele. Alkalmasnak látszik tehát arra - a matematikusok és a kommunikációs szakemberek szerint is -, hogy vele az igazi üzenet apró tűjét hatalmas szénakazalba rejtsük. A rá építő titkosítási módszerek ma már népes családjából a közös titok képzésére szolgáló Diffie-Hellman-protokollt nézzük meg részletesebben.

Képzeljük el, hogy két egymástól távol levő, de az interneten egymást elérni képes személy meg szeretne egyezni valami közös titokban, amit ők ketten tudnak, és mások akkor sem, ha az összes üzeneteiket el tudják olvasni. Legyen, mondjuk, a két személy Rómeó és Júlia, mindketten bezárva otthon, zord atyáik házába. Tegyük fel, hogy egy közös titkos jelszót akarnak képezni a veronai junior bankszámlájukhoz. Mindketten rendelkeznek számítógéppel és internetes kapcsolattal. A titokképző protokoll lépései a következők:

1. Először közösen választanak egy E_p görbét, ez lehet például a NIST P-192, és azon egy pontot.

2. Rómeó titokban választ egy véletlen r egészet, amelyre , kiszámítja az rQ pontot, és ezt (ennek a koordinátáit) elküldi Júliának. Júlia ugyanígy sorsol magának titokban egy j egészet, és a jQ pontot kiszámítja, majd elküldi Rómeónak.

3. Rómeó kiszámolja a Júliától kapott jQ pont r-szeresét, vagyis az r(jQ) pontot. Ugyanígy, Júlia meghatározza a Rómeótól kapott pont j-szeresét, ami j(rQ).

A pontösszeadás tulajdonságai miatt ott van mindkettőjüknél ugyanaz a pont, jelesül (rj)Q, hiszen (rj)Q=r(jQ)=j(rQ).

A protokoll lépései a könnyű feladat ismételt elvégzésével hatékonyan megvalósíthatók. Most pedig megmutatjuk, hogy a közös pont koordinátáit leíró számok, vagy azok egy darabja, mondjuk a leírás első néhány számjegye, használható közös titokként. Mi az, amit az üzenetcserét lehallgató kíváncsiskodó megtudhat? Ismerheti az E_p görbét, a Q, az rQ és a jQ pontokat. Ebből kellene kitalálnia az S=(rj)Q pontot. Erre jobb módszert nem ismerünk, mint meghatározni az r és j számokat, amelyek ismeretében S már könnyen adódik. Az r és a j számítása pedig éppen a diszkrét logaritmus-feladat.

A biztonságot illetően az igazi az lenne, ha matematikai bizonyítást tudnánk adni arra, hogy a titok megfejtése legalább olyan nehéz számítási feladatot jelent, mint a hírhedten kemény diszkrét logaritmus-feladat. Ilyen bizonyítás egyelőre nincs, de vannak fontos eredmények, amelyek ebbe az irányba mutatnak (pl. U. Maurer, S. Wolf, 2000). A gyakorlatban használatos konkrét görbék esetében jobb a helyzet. A. Muzereau, N. P. Smart és F. Vercauteren friss eredménye szerint egy sor, a szabványokban javasolt görbére, így a példánkban használt P-192-re is létezik ilyen visszavezetés. Ez úgy képzelhető el, mint egy gyors számítógépes program, amely az adott görbére vonatkozó diszkrét logaritmusok számítását visszavezeti az ugyanazon görbéhez tartozó Diffie-Hellman-protokoll feltörésére. Tehát például, ha valaki gyorsan meg tudná fejteni a P-192 görbe segítségével a protokoll szerint képzett titkokat, akkor ugyanezen görbén gyorsan tudna diszkrét logaritmust számítani.

Jelenleg több titkosítással kapcsolatos alapfeladatra az elliptikus görbéken alapuló megoldások látszanak a legolcsóbbaknak abban az értelemben, hogy egy adott biztonsági szint eléréséhez ezek a módszerek igénylik a legkisebb számítási teljesítményt az ismert rendszerek közül. Ezért különösen alkalmasak a szerényebb számítási erejű eszközökön való működésre, mint amilyenek az intelligens kártyák vagy a mobil eszközök. Hasonló okok miatt kezdenek teret hódítani az internetes böngészőprogramok biztonsági megoldásaiban is. Mindezek fényében egyáltalán nem meglepőek azok a jóslatok, amelyek az elliptikus görbéken alapuló titkosítás erőteljes előretörését ígérik az infokommunikáció több területén is.