
Az elliptikus görbés kriptográfia egy olyan PKI kriptográfia, ami az elliptikus görbéken alapul véges mezőkön. Ez első olvasásra bonyolultnak tűnik, de a valóságban nem feltétlenül az. Ahhoz, hogy könnyebben megérthető legyen, elkészült ez a leírás.
Az elliptikus görbe egy olyan egyenlettel leírható görbe, amely felírható a következő alakban:
y2=x3+ax+b
Attól függően, hogy az a és b milyen értéket vesz fel, a görbe alakja más és más lesz; az alábbi képeken található görbék mind elliptikus görbék.
Az elliptikus görbés kriptográfia esetén nevesített görbéket használunk. Ez azt jelenti, hogy a görbékhez és az azzal végzett számításokhoz vannak hozzátartozó a és b értékek, illetve további (a számításokhoz használandó) paraméterek. Ezeket az értékeket közzéteszik: a digitális aláírások esetében például NIST által elfogadott görbéket használunk. A görbéket a Standards for Efficient Cryptography definiálja.
Ezek például a Bitcoin kulcsok által használt SEC256K1 görbe esetén az a = 0; b = 7 értékeket veszik fel, így a képlet az alábbira módosul.
y2=x3+7
Ez a görbe így néz ki:
A digitális aláíráshoz használt SEC256R1 (vagy más néven NIST P256) görbe a és b értékei ennél sokkal nagyobbak, így az érthetőség kedvéért most a Bitcoin által is használt görbén keresztül mutatjuk be az EC kriptográfiát.
Ahhoz, hogy a görbéket kriptográfiához használhassuk, szükségünk van még pár paraméterre, amely az adott nevesített görbéhez tartozik.
Ezek a következők:
Ahhoz, hogy megérthessük, hogyan működik az elliptikus görbés kriptográfia, ismernünk kell az elliptikus görbén végezhető alapvető matematikai műveleteket.
Végezhető alapvető műveletek:
Az elliptikus görbék fontos tulajdonsága, hogy nincs a műveletek között osztás.
4.1 Pont negációja
Egy pont negációja (előjelének megfordítása) nem más, mint a vízszintes tengelyre tükrözése.
4.2 Két pont összeadása
A definíció szerint két pont összekötése egy egyenessel kiadja a harmadik pontot negatív előjellel.
P+Q= -R
(Az elliptikus görbés összeadás definíciója más mint a hagyományos összeadásé.)
Ez így néz ki:
Ahhoz, hogy megkapjuk a +R-t, a negáció során meghatározott tükrözést a vízszintes tengelyre el kell végezni.
Ennek eredménye az R pont.
4.3 Pont duplikálása
A pont összeadás speciális esete az, amikor a pontot saját magával adjuk össze.
Ilyenkor a két pont tulajdonképpen egybe esik, így az érintő egyenest kell megrajzolni, ami a -2P pontot metszi, és azt tükrözve megkapjuk a pont dupláját, 2P-t, az elliptikus görbén.
4.4 Pont szorzása számértékkel
Mivel két pontot össze tudunk adni, illetve a pontot tudjuk duplikálni (saját magával összeadni), így tetszőleges számban kombinálva ezt, skalár értékkel meg is tudjuk szorozni a tetszőleges pontunkat a görbén.
Az alábbi példában a P pontot 3-mal szorozzuk meg, ennek lépései a következők:
1. a P pontba érintőt húzunk és a kapott -2P metszéspontot tükrözzük, hogy megkapjuk a 2P-t.
2. A P és 2P pontokat összekötjük és a kapott -3P metszéspontot tükrözzük, hogy megkapjuk a 3P-t
A példában 3-mal szoroztunk, de nagyobb értékkel történő szorzás értelemszerűen azt jelenti, hogy az összeadás és duplikáció műveletét ismételgetni kell.
Ha például 6-tal szeretnénk szorozni, akkor a most kapott 3P-t felhasználva a duplikációnak megfelelően érintő egyenest rajzolva, majd tükrözve kapnánk meg a 6P-t.
Az elliptikus görbés kriptográfia során 256 bites (2255 nagyságrendű) az a szám, amivel szorzunk, azaz a privát kulcsunk.
A privát kulcs (privkey) egy véletlen egész szám 0 és n-1 között, ezt generáljuk.
A publikus kulcs a generátor (G) pont szorozva ezzel a generált véletlen számmal az elliptikus görbén.
pubkey = privkey * G
Ez azt jelenti, hogy az előző fejezetben olvasható szorzást kell végrehajtanunk a G ponttal.
Az, hogy az elliptikus görbén nem értelmezett az osztás, lehetetlenné teszi, hogy a nyilvános kulcsból, ami egy pont a görbén, meghatározzuk a privát kulcsot jelentő véletlen számot.
Az ellenőrzés általános alapelve, hogy helyreállítjuk a véletlen pontot a publikus kulcs segítségével, és ha az megegyezik az aláíráskori ponttal, akkor az aláírás helyes. Az ellenőrzés lépései az elliptikus algoritmussal a következők:
7.1 A matematika az aláírás és ellenőrzése lépések mögött
Habár ránézésre az összefüggés az aláírás és ellenőrzés között nem feltűnő, az egyenletek rendezésével ellenőrizhető az összefüggés helyessége.
Alakítsuk át az R’ pont képletét úgy, hogy behelyettesítjük a pubKey helyére annak képletét (pubKey = privKey * G):
R'=(h*s1)*G+(r*s1)*pubKey= (h*s1)*G+(r*s1)*privKey * G= (h+r*privKey)*s1*G
Ha vesszük az aláíráskor használt s értékét, akkor a következőkép tudjuk kiszámítani az s1 értékét:
s=k-1*(h+r*privKey)(mod n)
s1=s-1 (mod n)= (k-1*(h+r*privKey))-1 (mod n)=k*(h+r*privKey)-1 (mod n)
Ezt követően be kell helyettesíteni az s1 értéket az R’ pont fent meghatározott képletébe:
R'=(h+r*privKey)*s1*G= (h+r*privKey)*k* (h+r*privKey)-1 (mod n)*G= k*G
A kapott képlet a következő:
R'=k*G
Ha ezt összevetjük az aláíráskor használt képlettel láthatjuk, hogy egyezik:
R=k*G
Ez azt jelenti, hogy ha az R és R’ pontok egyeznek (amit célszerűség kedvéért csak az x koordinátával hasonlítunk), az aláírás rendben van.
© 2023 Microsec zrt. | Cégjegyzékszám: 01-10-047218 | Adószám: 23584497-2-41