Kriptográfia

Bitcoin titkosítása – elliptikus görbékkel

A diszkrét logaritmus és az elliptikus görbék is idegen fogalmak, ráadásul teljes megértésükhöz felsőbb matematikai ismeretek szükségesek. Ennek ellenére tartogatnak olyan érdekességeket, amelyek már középiskolás tudással is megérthetők. Három lépésben mutatjuk be a titkosítás alapjait. Elsőször az elliptikus görbéket tekintjük át, és értelmezünk a pontjai között műveleteket. Második lépés, hogy megértsük, hogy miért használható ez a rendszer titkosításra, azaz, hogyan lehet nyílt és titkos kulcsokkal üzenni úgy, hogy lényegében feltörhetetlen kódolást készítünk. Végül megpróbálunk eljutni a valós kódolás alapjaihoz, amelyeket véges elemű halmazon értelmezett műveletekkel végzünk.

Elliptikus görbék

Elliptikus görbének nevezzük azt a síkgörbét, amelynek a pontjai kielégítik a következő egyenletet, kiegészítve egy “végtelenben felvett” ponttal, amelyet \(O\)-val jelölünk. \[ \begin{aligned} y^2=x^3+ax+b \end{aligned}\notag \] A fentiekben definiált elliptikus görbékből a kriptavaluták, így a Bitcoin-hoz használt blockchain titkosítását az alábbi elliptikus görbéből kiindulva végzik. \[ \begin{aligned} a=0,\,b=7\\ y^2=x^3+7 \end{aligned}\notag \] Most egy nehéz lépés jön. Műveleteket értelmezünk az elliptikus görbe pontjai között. Először két pont összegét, \(P+Q\)-t, majd egy pont skalárszorosát, \(nP\)-t definiáljuk. Két különböző pont összege legyen az ábrán jelölt \(P+Q\), azaz \(P,Q\)-n átmenő egyenes és a görbe metszéspontját tükrözzük az \(x\) tengelyre. Egy pont kétszeresét, \(2P\)-t úgy kapjuk, hogy \(P\)-ben érintőt húzunk az elliptikus görbéhez, és a görbével vett metszéspontját tükrözzük \(x\) tengelyre. A műveletek szokatlanok lehetnek, de talán ez adja az érdekességüket is. Ha meghatározzuk a \(2^kP\) pontokat, akkor ebből már tetszőleges \(nP\) pont számítható. Erre azért van szükség, mert kevesebb művelettel számítható ki egy pont tetszőleges skalárszorosa, \(nP\), ahhoz viszonyítva, mintha az \(n\) db összeadást elvégeznénk. Például \(9P=2^3P+P\), így a 9 összeadás helyett csak három duplikációt és egy összeadást kellett elvégezni. Ennek azért van jelentősége, mert nagyon nagy számokkal dolgozik a titkosító algoritmus, és az alacsonyabb műveletigény növeli a számítás sebességét.

Diszkrét logaritmus

Olyan titkosítás szeretnénk képezni, amely során a titkosítás könnyen megtörténhet, de feltörni nem lehet. Az elliptikus görbékkel definiált műveletek lehetővé teszik ezt. Ugyanis, ha nagy \(n\) számot keresünk, akkor ennek ellenére \(Q=nP\) könnyen számítható, azonban \(P,Q\) ismeretében lényegében reménytelen meghatározni \(n\) értékét. A műveletet, amellyel \(P\) és \(Q\) ismeretében \(n\) meghatározható, diszkrét logaritmusnak nevezzük és \(n=\log_P Q\)-val jelöljük.

Véges elemű elliptikus görbe

A folytonos elliptikus görbék esetén látható, hogy az egyik pontból, hogyan juthatunk el egy másikba, összeadással, vagy skalárral való szorzással. A kriptográfiában nem jók az ennyire kiszámítható elemek, ezért a valós számokon értelmezett elliptikus görbék helyett ezek véges sok pontját használják. Az elliptikus görbe azon értékeit tekintjük, amelyekre teljesül a görbét leíró egyenlőség modul p, azaz csak azokat a pontokat tekintjük, amelyek koordinátáira teljesül, hogy \[ \begin{aligned} y^2=x^3+7\mod p \end{aligned}\notag \] Az \(x,y\) értékeit is csak véges sok számból, \((0,\,1,\,\ldots,\,p-1)\)-ből választjuk ki. Az előzőek alapján a kriptográfiában használatos elliptikus görbe képe \(y^2=x^3+7,\,p=17\): Igen, ez se nem elliptikus, se nem görbe. A grafikonról leolvasható, hogy például az \((1,\,5)\) pont eleme a diszkrét elliptikus görbének, mert \[ \begin{aligned} x^3+7=1^3+7=7,\quad 7\equiv 7 \mod 17\\ y^2=5^2=25,\quad 25\equiv 7\mod 17 \end{aligned}\notag \] Azaz a diszkrét elliptikus görbe egyenletét kielégítik a megadott koordináták (\(17\)-tel vett maradékait tekintve). Valószínűleg nehéz feldolgozni a fentieket a sok újdonság miatt, ennek ellenére egy kis betekintést kaptunk abba, hogy milyen bonyolult világ vesz körül bennünket.