Elliptikus görbén alapuló titkosírás

Csirmaz Laszlo <laci@degas.ceu.hu>

CEU

A nyilvános kulcsú titkosírás hátterében egy-egy matematikai probléma áll, melyr?l azt tételezzük fel, hogy nehéz megoldani. Az RSA azt használja, hogy míg viszonylag egyszer? eldönteni egy több száz jegy? számról, hogy összetett-e, addig prímtényez?ire bontani már reménytelenül nehéz feladat. A Diffie--Hellman módszer hátterében az úgynevezett diszkrét logaritmus probléma áll: adott az alap és a hatványozás eredménye, keressük meg a kitev?t. A hatványozás természetesen ismételt szorzás, viszont a szorzást nem a szokásos módon kell elvégezni, hanem maradékosan, valamilyen el?re meghatározott prímszám modulussal. A problémát általánosan is meg lehet fogalmazi: definiáljunk valahogyan egy szorzásnak nevezett m?veletet sok (tipikusan 10¹⁰⁰ ) elem között, választunk egy g alapot, egy n kitev?t, és kiszámítjuk az y=gⁿ hatványt. A feladat y és g ismeretében megkeresni az n kitev?t. Az elliptikus görbék olyan matematikai eszközt adnak, aminek segitségével a fenti szorzás viszonylag egyszer?en definiálható, gyorsan számítható, és az adódó diszkrét logaritmus probléma megoldására csak az általános (és ezért kivárhatatlan idej?) algoritmusok ismeretesek. Az elliptikus görbék elméletét a matematika talán legszebb, és egyik legnehezebb része, az algebrai geometria tárgyalja. Ezek a görbék a középiskolából jól ismert kör, ellipszis, parabola, hiperbola általánosításai. Míg például az egységkör a síknak azokból az (x,y) koordinátájú pontjaiból áll, amikre x²+y²=1, addig például az y²=x³+ax+b egyenletet kielégít? pontok egy elliptikus görbét határoznak meg. Ilyen görbék pontjain tudunk szorzást definiálni, és ezt a szorzást használjuk fel a fentiekben bemutatott módon egy nyilvános kulcsú titkosírás definiálására.