A kriptovaluták matematikája – ECDSA kulcspár

A kriptovaluták kriptográfiai eljárásokat használnak. Ezzel biztosítják, hogy csak az férhessen hozzá a pénzhez akinek a tulajdonában van, hogy egy-egy tranzakció esetén meg tudjunk győződni arról, hogy ez hiteles, és bizonyos kriptovaluták még adatokat is titkosítanak ezen eljárásokkal. Nagyon bonyolultnak tűnhet ez a terület, azonban az egész szinte csak egyszerű matematika.

Amikor kriptovalutát utalunk meg kell adnunk pár fontos adatot, hogy honnan, hová és mennyi pénzt szeretnénk átküldeni. Ez eddig hasonló, mint amikor banki utalás végzünk, ezek az adatok ott is szükségesek. Banki utalás esetén megfogjuk a papírt, ráírjuk ezeket az adatokat, aláírjuk, majd odaadjuk az ügyintéző kisasszonynak. A bank ellenőrzni az adatok, megbizonyosodik róla, hogy van elég pénzünk, hogy a cél számla létezik és arról is, hogy valóban a mi aláírásunk szerepel-e a papíron. Emellé még esetleg személyi igazolványt, vagy egyéb hitelesítő iratot kér tőlünk.

A kriptovaluták esetén nincs papír, sem bank. Valahogyan mégis meg kell bizonyosodni arról, hogy az a pénz amit el szeretnénk küldeni a miénk és jogunk van használni. Éppen ezért ezeket az utalásokat is alá kell írnunk, de nem a tollal, hanem digitális. Amikor utalást indítunk készítünk egy digitális aláírást és azt is csatoljuk az utalási kéréshez. A hálózat többi tagja pedig le tudja ellenőrízni, hogy valóban mi írtuk-e alá a tranzakciót. Ehhez egy ECDSA (Elliptic Curve Digital Signature Algorithm) nevű algoritumust fogunk használni. A legtöbb kriptovaluta ezzel működik.

Az ECDSA magyarul egy elliptikus görbéken alapuló digitális aláírási algoritmus. Elliptikus görbének azokat sík algebrai göbéket nevezzük, amelyeket az

y² = x³ + ax + b

formájú egyenlet ír le. Egy elliptikus görbe így néz ki koordináta rendszerben ábrázolva.

Érdemes megfigyelni, hogy szimmetrikus az x tengelyre. Előfordulhatnak olyan esetek amikor szingularitás keletkezik. A szingularitás egy olyan pont, ahol a görbe saját magát metszi, “csúcsosodik”, vagy a görbétől külön álló pont jelenik meg. Példákat itt lehet megtekinteni. Ezek nekünk nem nagyon kellenek, ezért ki is zárjuk őket egy kitétellel:

4a³ + 27b² ≠ 0

Tehát a képletünk most így néz ki:

y² = x³ + ax + b
és
4a³ + 27b² ≠ 0

Most, hogy tudjuk mi az az elliptikus görbe nézzük meg hogy jön itt szóba a kriptográfia! Válasszunk egy tetszőleg P pontot a görbén, legyen ez P(x,y). Válasszunk egy másik pontot is amely a görbénken van, ez legyen q(x,y). Kössük össze a két pontot egy egyenessel és nézzük meg, hogy hol metszi az egyenes a görbénket! A metszéspontból húzzunk egy, az x tengelyre merőleges vonalat és nézzük meg, hogy ez a vonal hol metszi a görbét. A másik oldalon lévő metszéspont legyen R(x,y). Ez pontosan az előző metszéspontunk tükrözése és egybe P és Q pont összege is. (A rajz minőségéért elnézést 😀 )

Mi történik, ha P ponthoz saját magát adjuk hozzá? Ebben az esetben végtelen mennyiségű egyenest tudunk húzni, hiszen a P ponton rajta lesz a másik P. Aztán a 2•P pontunkhoz hozzá adhatjuk még egyszer a P-t, ekkor megkapjuk a P+P+P-t, azaz a 3•P-t. Ezt az összeadási műveletet akárhányszor meg tudjuk csinálni.

Az abrán 3•P-t számoljuk ki. Ehhez először hozzádjuk a P ponthoz önmagát és húzunk egy eneset amely P-n átmegy (zöld). A metszéspontot tükrözzük és így megkapjuk P+P-t, azaz 2•P-t. Mi P+P+P-t szeretnénk kiszámolni, így most P+P-hez hozzáadjuk P-t. Húzunk egy egyenest amely átmegy a P ponton és a 2•P ponton is. A metszéspontot tükrözzük és így meg is kapjuk 3•P-t. (Piros pont). (Az ábra jelen esetben is csak szemléltető eszköz, nem pontos, nem szép és nem arányos)

Mit kellene tenni, ha 4•P-t, azaz P+P+P+P-t szeretnénk kiszámítani? Ebben az esetben P-ből húznánk egy egyenest 3P-be, a metszéspontot tükröznénk és meg is kapnánk 4•P-t. De most maradjunk a 3•P pontunknál és nevezzük el ezt a pontot Q-nak. Tehát legyen Q = 3•P. Általános formában Q = D•P, ahol a D egy szabadon választott szám. A mi esetünkben D=3.
A Q pontnak van egy x és egy y koordinátája amik leolvashatóak az ábráról. Ha ismerjük ezt a Q pontot, akkor meg tudjuk mondani, hogy hányszor adtuk össze P-t, azaz, hogy mennyi volt a D? Nem, ennek a kiszámítását nem tudjuk elvégezni egykönnyen. Tehát, a Q(x,y) pont koordinátáit elmondjuk bárkinek. ő nem fogja tudni, hogy hány alkalommal adtuk önmagához a P pontunkat. Ha ismeri P-t, akkor is csak úgy tudhatja meg, hogy mi a 3-as számot választottuk, ha addig végez összeadásokat, amíg el nem éri Q-t, vagy Q-ból elkezdi kivonogatni a P-t amíg a kivonások eredménye nem lesz egyenlő P-vel.

Most adjunk meg pár szabályt a játékunkhoz!

1. Először is mondjuk azt, hogy az elliptukus görbénk egyenlete mindig ez legyen:

y² = x³ + 0x + 7

Egyszerűbben:

y² = x³ + 7

Az első formát azért írtam le, hogy jobban látszódon, hogy ez megfelel az eredeti egyenletnek, csak itt a=0 b pedig 7.

2. Hozzunk még olyan szabályt, hogy a P pont legyen fix, ne lehessen szabadon választani. P pont koordinátái legyenek a következő szép nagy számok:

x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

3. A harmadik szabályunk legyen az, hogy annyiszor adjuk P-t önmagához amennyiszer csak akarjuk, viszont amikor P+P-t számoljuk, akkor csak olyan egyenest húzhatunk P-ből, amely a görbe érintője.

Bárki játszat, de a három szabályt be kell tartania. Most ezzel elértük, hogy mindenki ugyanazt a görbét fogja használni, az első P pontja mindenkinek ugyanott van és P-ből csak egy egyenest tudunk húzni amikor önmagához hozzáadjuk. A fenti egyenlet írja le a használt elliptikus görbét, míg a P(x,y) pont, amit ezek a szép nagy koordináták határoznak meg a bázispont (base point).

Azt is említettük, hogy, ha megmondjok valakinek a Q pont koordinátáit, ő nem fogja tudni megmondani, hogy hányszor adtuk önmagához P-t. Ő tudja Q értékét, mert megadtuk, ismerti P-t mert azt az előbb meghatároztuk a szabályokban, és azt, hogy Q = D•P. Ahogy fentebb már megállapítottuk, D-t nem lehet kiszámolni, csak hosszadalmas próbálgatással. Képzeljük el, hogy hogy a D nagyon nagy szám is lehet. Egészen pontosan 0 és 2²⁵⁶-1 között bármilyen egész számot választhatunk. Ekkor, ha valaki a Q és a P ismeretében meg szeretné mondani, hogy mennyi volt a D, el kell kezdenie egyenként összeadni. Akár 2¹²⁸ próbálkozás is kellhet, mire eltalálja a számot. Ilyen sok összeadást, vagy kivonást nagyon sok idő elvégezni. Amikor viszont mi készítjük el a saját Q pontunkat, akkor nekünk nem kell ennyit számolni. Vegyünk egy példát, legyen az D=10, tehát Q = 10•P. Ez egyenlő a P+P+P+P+P+P+P+P+P+P-el, azaz tíszer adjuk össze P-t. De, nézzük a következőt:

2•P = P+P
4•P = 2P+2P
8•P = 4P+4P
10•P = 8•P+2•P

Így, először kiszámoljuk 2•P-t. 2•P-hez hozzáadunk még 2•P-t akkor már tudjuk 4•P-t. 4•P-hez hozzáadjuk a 4•P-t így meglesz a 8•P. A végén pedig 8•P-hez adjuk hozzá 2•P-t és megvan a 10•P. Ez 4 darab összeadás. De ez csak azért működik, mert ismerjük D-t. Természetesen a való életben a D sokkal nagyobb szokott lenni. Olyan sokkal amit elképzelni is nehéz.

Tehát a D egy olyan szám amit csak mi ismerünk és nem lehet kiszámolni Q-ból. A Q pedig könnyen számítható D-ből. Adjunk nekik nevet. Legyen D a privát kulcsunk, Q pedig a publikus kulcsunk. Lehet, mivel teljesíti azt a feltételt, hogy a privát kulcs ne legyen meghatározható a publikus kulcsból. Már csak egy probléma van, akár nagyon hosszú tizedes törtek is lehetnek a koordinátáink, azt pedig nem lehet kicsi helyen tárolni. Módosítsunk az egyenletünkön, hogy csak egész számok lehessenek

y² mod p = (x³ + 7) mod p

A p pedig legyen egy prím szám, mondjuk p = 2²⁵⁶-2³²-977
(A mod pedig a maradékos osztást jelenti, 13 mod 3 = 1, mert 13 ben a 3 megvan négyszer és marad az 1)

Most nézzük meg újra, egyben a három szabályunkat:

x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424 

Ezzel most pont leírtuk az ECDSA algoritmus secp256k1 görbéjének a működését. 🙂 Így már tudunk készíteni magunknak valódi ECDSA secp256k1 kulcspárt, pont olyat, amit a bitcoin és a MicroCoin is használ. Minden szabályt ismerünk hozzá.

A lépések:

A  kulcspárunkat pedig a következő adatok írják le:

Algoritmus: ECDSA
Görbe (curve): secp256k1
Privát kulcs: A D értéke
Publikus kulcs: Q x és y koordinátája

Hogyan néz ez ki programkódban? Így:

ECCurve curve = ECCurve.CreateFromFriendlyName("secp256k1");
var ecdsa = ECDsa.Create(curve);
EECParameters parameters = ecdsa.ExportParameters(true);
// parameters.D -> privát kulcs
// parameters.Q.X -> publikus kulcs x koordinátája
// parameters.Q.Y -> publikus kulcs y koordinátája

Szerencsére nekünk nem kell pontokat összeadni és ezekkel játszani, megcsinálja helyettünk az .NET framework, vagy pl. az OpenSSL.

A publikus kulcs esetében nem feltétlen van szükségünk az x és az y koordinátára is. Elég az x és az, hogy az előjele negatív, vagy pozitív. Ugyanis, ha egy adott x koordinátára húzunk egy az x tengelyre merőleges egyenest, akkor két ponton fogja metszeni a görbénket amelyek az y koordináta előjelében fognak különbözni. Így a publikus kulcsot nem kell 2×256 biten tárolnunk, hanem így, tömörített formában is lehetséges. Ezt a tömörített formátumot használja a bitcoin.

Mivel ez a bejegyzés már nagyon hosszú, és lassan fáj a kezem, ezért, hogy hogyan lesz ebből aláírás és hogyan fogjuk ellenőrízni, egy későbbi bejegyzésben leírom. 🙂