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.

1. Mi az elliptikus görbe?

Az elliptikus görbe egy olyan egyenlettel leírható görbe, amely felírható a következő alakban:

y²=x³+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.

2. Milyen görbéket használunk a PKI-hez?

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.

y²=x³+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.

3. Milyen paraméter tartozik még a görbékhez?

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:

• Generátor pont (G)
  Ez egy olyan pont a görbén, amit mindenki használ az aláírás (vagy annak ellenőrzése) során

• a véges mező (Fp) végét meghatározó p paraméter
  A véges mező egy olyan számmező, amely egész számokat tartalmaz két végpont között. Az Fp véges mező 0 és p-1 közötti egész számokat tartalmazza, ennek matematikai leírása:
  
  F_p={0,…, p-1}
  
  Mivel a görbénket véges mezőn használjuk, ezért a görbénkhez tartozó képlet is módosul:
  
  y²=x³+ax+b (mod p)
  
  Ez a Bitcoin görbéje esetében így néz ki:
  
  y²=x³+7 (mod p)

• a maximális kulcs értékeket meghatározó n paraméter
  Ez határozza meg privát kulcs maximális értékét. A privát kulcs értékének 0 és n-1 közé kell esnie. Ez az n érték a G rendje.

• a társfaktor h
  Ez az érték aláíráskor és aláírás ellenőrzéskor használt, kicsinek kell lennie (h ≤ 4), lehetőleg h=1 -nek.

4. Műveletek az elliptikus görbén

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:

• pont negációja (előjel váltása)
• két pont összeadása
• pont duplikálása (pont önmagával összeadása)
• összeadás ismétlésével a számmal (skalár értékkel) történő szorzás is megvalósítható.

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 (2²⁵⁵ nagyságrendű) az a szám, amivel szorzunk, azaz a privát kulcsunk.

5. Hogyan jön létre a kulcspárom? Miért biztonságos?

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.

6. Hogyan írunk alá?

1. Az aláírás lépései az elliptikus algoritmussal a következők:

1. Számítsuk ki dokumentum hash (h) értékét.
2. Generáljunk egy k véletlen számot, ahol k értékének 0 és n-1 közé kell esnie.
3. Számoljuk ki a k számhoz tartozó R pontot a G pont szorzásával.
   R=k*G
4. Vegyük az R pont x koordinátájának értékét, ez legyen r:
   r=R.x
5. Számítsuk ki az aláírás-bizonyíték értékét, amit s-sel jelölünk.
   s=k^-1*(h+r*privKey)(mod n)
6. Az aláírásunk az r és az s értékek együttesen.

7. Hogyan ellenőrzünk?

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:

1. Számítsuk ki dokumentum hash (h) értékét.
2. Számítsuk ki az s1 értékét: s1=s^-1  (mod n)
3. Határozzuk meg az alíráskor használt véletlen pontot:
   R'=(h*s1)*G+(r*s1)*pubKey
4. Vegyük az R’ pont x koordinátájának értékét, ez legyen r’ = r'=R'.x
5. Ha az aláíráskori r és az ellenőrzéskori r’ megegyezik, akkor az aláírás sikeresen ellenőrzésre került.

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.