Ugrás a tartalomhoz

Kriptográfia

Liptai Kálmán

Kempelen Farkas Hallgatói Információs Központ

Diszkrét logaritmus

Diszkrét logaritmus

A knapsack rendszer bevezetésénél már említettük, hogy minden nyilvánoskulcsú kriptorendszer alapja egy olyan probléma, amit gyakorlatilag lehetetlen megoldani. Ez számunkra azt jelenti, hogy, hogy a megfejtéshez szükséges idő sokkal, de sokkal nagyobb, mint amennyi idő az információ megszerzéséhez rendelkezésre áll. Az elliptikus görbéken megvalósított titkosításnak (ECC) is egy ilyen probléma adja a biztonságát. A problémát a szakirodalom ECDLP (Elliptic Curve Discrete Logarithm Problem) jelöléssel használja, jelentése „diszkrét logaritmus elliptikus görbék feletti” kiszámolásának problémája.

1991-ben néhány kutató elkészítette az RSA algoritmus elliptikus görbén alapuló változatát is, de néhány évvel később többen is megmutatták, hogy az elliptikus RSA-nak (ECC-like RSA) nincs számottevő előnye a hagyományos RSA-val szemben. Az ECRSA problémája egyébként továbbra is a faktorizálás maradt.

Eddig lényegében két műveletet definiáltunk a görbén, a pontok összeadását és egy pont duplázását. Ha elképzeljük az általunk könnyen elkészíthető sorozatot , rájövünk, hogy tulajdonképpen már szorozni is tudunk. Az így képzett pontot a pont skalár szorzatának nevezzük. Belátható, hogy az természetes szám meghatározása a szorzat alapján nem egyszerű feladat főként, ha a görbét egy test felett értelmezzük.

10.5. Definíció. Legyen egy test feletti elliptikus görbe és egy pont a görbén. Ekkor az -n értelmezett diszkrét logaritmusos problémáról beszélünk (az alapra vonatkozóan), ha adott egy pont és keressük azt az természetes számot, melyre egyenlőség teljesül (ha ilyen létezik). Ebben az esetben diszkrét logaritmusa -nak a bázis felett.

A diszkrét logaritmus előbb definiált szorzása és az elliptikus görbén értelmezett összeadás, lényegileg ugyanaz.

Megjegyezzük, hogy az ECDLP-n alapuló rendszerek többsége aláíró vagy kulcscserélő rendszer, mert gyors titkosításra ez a módszer is alkalmatlan. A következőkben néhány működő rendszert tekintünk át.

ECDH - Elliptic Curve Diffie - Hellman kulcscsere

Az eredeti Diffie-Hellman algoritmus a szimmetrikus titkosító rendszerek kulcsmegosztási problémáját oldotta meg. A két résztvevő ugyanazokat a műveleteket végezte el egyező nyilvános és különböző titkos paraméterekkel, de azonos eredményt kaptak, melyet kulcsként használhattak. Az ECDH is ugyan így működik, csak nem moduláris hatványozást használ, hanem a fejezet eddigi részében megismert elliptikus görbe műveleteket.

10.6. Példa. Szemléltessük egy példán keresztül:

Alice és Bob megegyeznek egy görbében és egy pontban, utóbbit bázispontnak hívjuk. A továbbiakban eme paramétereket nyilvános rendszerparamétereknek tekintjük. Alice választ egy véletlen számot, (amely kisebb, mint a pont rendje) és ugyan így tesz Bob is: Alice száma legyen , Bobé legyen . Mindketten titokban tartják választásukat. A kulcscsere következő lépésében Alice kiszámolja pontot, melyet elküld Bobnak, aki Alice műveletéhez hasonlóan kiszámolja pontot és elküldi Alicenek. Végül Alice a Bobtól kapott -t megszorozza -val, így megkapja pontot, valamint Bob az Alicetől kapott pontot szorozza meg titkos számával és eredményül ő is az pontot kapja. A közös pont valamely tulajdonsága (például vagy koordinátája vagy éppen , XOR , stb.) használható kulcsként. A kíváncsi Eve-nek az pontot kellene kiszámolnia, de csak , és pontokat ismeri, magukat a titkos és számokat nem. Az elliptikus Diffie-Hellman működését és lépéseit az alábbi egyszerű számpélda alapján követhetjük:

ECElGamal-Elliptic Curve ElGamal titkosítás

Ahogy az eredeti ElGamal titkosítás a Diffie-Hellman algoritmus problémáján alapul, úgy építhető fel az elliptikus ElGamal is az ECDH-ra:

  1. Alice és Bob választ egy görbét és egy bázispontot.

  2. Mindketten választanak egy-egy véletlen és számot, mint titkos kulcsot.

  3. Alice elküldi az pontot, mint nyilvános kulcsot Bobnak.

  4. Bob elküldi a pontot, mint nyilvános kulcsot Alicenek.

  5. Ha Alice üzenni akar Bobnak, az üzenetet leképzi a görbe egy (vagy több) pontjára, és generál egy véletlen számot, mint viszonykulcsot. Elküldi Bobnak a üzenet párost.

  6. Bob a következőképpen olvassa el az üzenetet: a kapott küldemény első felét megszorozza saját titkos számával, így -t kap, amit egyszerűen kivon a küldemény második feléből.

Elliptikus görbén alapuló digitális aláírás, ECDSA-Elliptic Curve Digital Signature Algorithm

Ahhoz, hogy Alice egy üzenetet aláírva el tudjon küldeni, következő paraméterek és eszközök szükségesek:

  1. egy elliptikus görbe felett (nyilvános paraméter),

  2. egy bázispont, melynek rendje (nyilvános paraméter, bit),

  3. egy véletlen szám és egy pont. Alice kulcspárja , ahol a titkos és a nyilvános kulcs.