Az elliptikus görbékre épülő kriptográfia
Az elliptikus görbék elméletére épülő kriptográfia (elliptic curve cryptography, ECC) az ún. ECDLP (elliptic curve discrete logarithm problem) nevű matematikai problémára épülő kriptográfiai megoldások együttes elnevezése. ECC alatt több algoritmust is értünk, köztük aláírásra (pl. ECDSA), titkosításra (pl. EC ElGamal) és autentikációra (pl. ECDH) szolgáló algoritmusokat is.

  A kriptográfiai alapfogalmakról szeretne olvasni?

 

Az ECDLP-re épülő algoritmusokra általánosságban igaz, hogy kisebb kulcsmérettel nyújtanak hasonló biztonságot, mint az RSA. Például, egy 160 bites ECC kulcs egy 1024 bites RSA kulccsal, egy 224 bites ECC kulcs egy 2048 bites RSA kulccsal ekvivalens biztonságot nyújt az NIST 2007-es ajánlása szerint. Ugyanakkor, az ECDLP-re épülő algoritmusok bonyolultabb műveleteket végeznek a kulcsokkal, így az ECC nem feltétlenül tekinthető gyorsabbnak, mint az RSA.

Az elliptikus görbék fogalmának bevezetése előtt áttekintjük a csoport és a test algebrai fogalmakat, majd ezek alapján bemutatunk egy "nehéz" matematikai problémát, az ECDLP-t. Végül leírjuk, hogy az ECDLP-re hogyan lehet kriptográfiai algoritmusokat, például elektronikus aláírást építeni.

Csoportok és testek

Egy halmaz elemei A={a1,a2,a3,...}, és egy köztük értelmezett művelet ("+") csoportot (G) alkotnak, ha a következők teljesülnek rájuk:

 

Csoportot alkotnak például az egész számok az összeadás művelettel.

Egy halmaz elemei A={a1,a2,a3,...}, és két köztük értelmezett művelet ("+" és "*") testet (F) alkotnak, ha:

 

Testet alkotnak például a valós számok az összeadás és a szorzás művelettel.

Elliptikus görbék

Az alábbi egyenlet definiál egy F test feletti elliptikus görbét:

y2 + axy + by = x3 + cx2 + dx + e

A fenti egyenletben mind az a, b, c, d, e együtthatók, mind az x és y változók az F test elemei. A görbét azon (x,y) ∈ F2 pontok alkotják, amelyek kielégítik a fenti egyenletet. További követelmény, hogy a görbe "sima" legyen, azaz ha a fenti egyenletet f(x,y) = 0 alakra hozzuk, akkor az f függvény akárhányszor differenciálható legyen.

Attól függően, hogy a görbét (illetve a fenti egyenletet) milyen F test felett értelmezzük, az egyenlet egyszerűbb alakban is felírható. Ha a görbét a valós számok felett értelmezzük, a fenti általános egyenlet az alábbi alakra hozható:

y2 = x3 + ax + b

A valós számok feletti görbe grafikusan is ábrázolható.

 


Egy elliptikus görbe a valós számok teste felett

 

Tekintsünk a görbe részének egy különleges O pontot. Az O egy absztrakt, végtelen távoli pont, amely rajta van minden függőleges egyenesen, és az x tengelyre vonatkozó tükörképe önmaga (azaz O = -O).

Az alábbi műveleteket definiáljuk a görbe pontjain:

A görbe pontjai (beleértve az O pontot is) csoportot alkotnak az ⊕ műveletre.

A valós számok teste feletti elliptikus görbék grafikusan szemléletesen ábrázolhatóak, de kriptográfiai szempontból nem bírnak jelentőséggel. A kriptográfiai területén ún. véges testek, azaz véges elemszámú testek feletti görbéket szokás használni.

A gyakorlatban a következő testek feletti görbék jelennek meg:

 

A GF(p) és GF(2m) testek feletti görbék nem ábrázolhatóak olyan szemléletesen, mint a valós számok teste feletti görbék, az ⊕ művelet esetén is elsősorban az algebrai definíciónak van értelme. Ugyanakkor egyes GF(p) és GF(2m) testek feletti görbék pontjai alkotta csoportokban a diszkrét logaritmus probléma (DLP) különösen "nehéz", így a DLP-re épülő kriptográfiai protokollok e csoportokban hatékonyan alkalmazhatóak, rövidebb kulcsokkal is biztonságot nyújtanak.

 


Az y2 = x3 + x görbe a GF(23) felett. A "görbe" pontjai azon (x,y) párosok, amelyek kielégítik a görbe egyenletét. (Forrás: certicom.com)

 

ECDLP (elliptic curve discrete logarithm problem)

 

Az elliptikus görbék kriptográfiai jelentőségét az adja, hogy egyes véges testek felett értelmezett elliptikus görbék pontjain a diszkrét logaritmus probléma (DLP), azaz az ECDLP, "nehéz" feladat, nem ismert rá hatékony algoritmus.

Ha Q egy elliptikus görbe egy pontja, és k egy egész szám, akkor a Q és k*Q pontok ismeretében k meghatározása "nehéz" feladat.

 

Megjegyzés: A görbe pontjai között értelmezett ⊕ műveletre az "összeadás" elnevezést használtuk, mert a szakirodalom általában így hívja e műveletet. Ezen elnevezés önkényes, az ⊕ műveletet akár a pontok közti "szorzás" műveletnek is nevezhettük volna. Ebben az esetben a másik művelet, a többször egymás után elvégzett szorzás a "hatványozás" nevet kapta volna. Ekkor az ECDLP alatt azt értettük volna, hogy a és a Qpontok ismeretében meghatározása, azaz a logaritmusképzés "nehéz" feladat.

 

Miller és Koblitz 1985-ben egymástól függetlenül javasolták, hogy az elliptikus görbék pontjain értelmezett diszkrét logaritmus probléma (ECDLP) kriptográfiai alkalmazását.

 

A következőkben bemutatott protokollok az ECDLP nehézségét használják ki.

Kulcsgenerálás

 

Nem könnyű megfelelő, azaz kellően biztonságos és kellően hatékony, görbét választani, ezért "nevezetes", nemzetközi szervezetek által ajánlott görbéket szokás használni. Az USA-ban az NIST (FIPS 186-3), az EU-ban a "Brainpool" munkacsoport javasolt görbéket. Általában egy ECC-re épülő rendszer minden felhasználója egyazon G görbét és annak egyazon Q pontját használja, tehát G és Q közös, nyilvános információk.

Amikor az Alajos nevű felhasználó ECC kulcspárt generál, a következő műveleteket végzi el:

  1. Generál egy kA véletlen számot. Ez lesz az ő magánkulcsa.
  2. Megszorozza a Q pontot a kA számmal, a kA * Q pont lesz az ő nyilvános kulcsa.

 

Megjegyzés: Amikor ECC esetében bitekben kifejezett kulcshosszról beszélünk, akkor a kmagánkulcs méretét értjük alatta.

ECC esetén a kódolási műveletek nem olyan szimmetrikusak, mint pl. RSA esetén. Itt az aláírás és a titkosítás nem inverz műveletei egymásnak, hanem egészen más módon történnek.

ECDH - elliptikus görbék feletti Diffie-Hellman protokoll

 

Az ECDH protokoll segítségével két fél - Alajos és Bendegúz - nyilvános csatornán keresztül állapodhatnak meg közös titokban.

 

  1. Alajos és Bendegúz átküldik egymásnak a nyilvános kulcsaikat: Alajos elküldi Bendegúznak a kA * Q nyilvános kulcsot. Bendegúz elküldi Alajosnak a kB * Q nyilvános kulcsot. Ha a csatornán hallgatózó támadó nem tudja megoldani az ECDLP-t, akkor a kapott adatokból nem ismeri meg sem kA-t, sem kB-t.
  2. Mindkét fél megszorozza a kapott nyilvános kulcsot a saját magánkulcsával:
    Alajos kiszámítja a (kB * Q) * kA = kA * kB * Q értéket.
    Bendegúz kiszámítja a (kA * Q ) * kB = kA * kB * Q értéket.

 

Az eredményül kapott, kA * kB * Q értéket csak ők ketten tudják kiszámítani, csak ők ismerik. Ez az érték lesz a közös titkuk, ebből képezhetnek közös szimmetrikus kulcsot.

 


Az elliptikus görbék feletti Diffie-Hellman protokoll

 

EC ElGamal - elliptikus görbék feletti ElGamal protokoll

 

Az EC ElGamal protokoll segítségével titkos üzenetet lehet küldeni valakinek. Tegyük fel, hogy Bendegúz titkos üzenetet szeretne küldeni Alajosnak. Üzenetének a görbe M pontját felelteti meg, az M pont koordinátáit szeretné átküldeni.

 

  1. Bendegúz kiválaszt egy r friss véletlen számot.
  2. Bendegúz kiszámítja a titkosított üzenetet, az
    r*Q és az M r*(kA * Q)
    értékeket, azaz a görbe két pontját. E két pont koordinátáit küldi át Alajosnak. Bendegúz csak a (kA*Q) értéket (azaz Alajos nyilvános kulcsát) ismeri, a kAmagánkulcsot nem.

     

     

  3. Alajos a kapott r*Q pontot megszorozza a saját kA magánkulcsával, így megkapja az r * kA * Q pontot. E pontot kivonja a kapott M r*(kA * Q) pontból, és eredményül megkapja a görbe M pontját, vagyis azt az üzenetet, amelyet Bendegúz küldött. A protokoll biztonsága arra épül, hogy Alajoson és Bendegúzon kívül más nem tudja kiszámítani az r * kA * Q pontot a csatornán megjelenő és a nyilvános információk alapján.

 

 


Az elliptikus görbék feletti ElGamal protokoll

 

 

Megjegyzés: RSA

 

ECDSA - elliptikus görbék feletti DSA (digital signature algorithm)

 

Tegyük fel, hogy az Alajos nevű felhasználó alá szeretné írni az m dokumentumot. Ehhez a következő lépéseket végzi el:

  1. Kiszámítja az e = h(m) (modulo n) értéket, ahol h() egy hash függvény.
  2. Generál egy t véletlen egész számot, ahol t ∈ [1, n-1].
  3. Kiszámítja az r = (t*Q)[x] (modulo n) értéket, ahol (t*Q)[x] a görbe t*Q pontjának x koordinátáját jelenti.
  4. Kiszámítja az s = t-1*(e + r*kA) (modulo n) értéket. (E művelethez van szükség a kA magánkulcsra.)

 

Az így kapott (r, s) páros az Alajos nevű felhasználó aláírása az m dokumentumon.

Az aláírás ellenőrzéséhez szükség van az m dokumentumra, az (r, s) aláírásra, az aláíró kA*Q nyilvános kulcsára, valamint a közös G görbére és annak Q pontjára. Az ellenőrző fél a következő lépéseket végzi el:

  1. Elvégzi a lenyomatképzést, azaz kiszámítja az e = h(m) (modulo n) értéket.
  2. Kiszámítja a w = s-1 (modulo n) értéket.
  3. Kiszámítja az u1 = (e*w) értéket.
  4. Kiszámítja az u2 = r*w (modulo n) értéket.
  5. Kiszámítja a görbe (x1, y1) = u1*Q + u2* kA *Qpontját.

     

    Ebből a Q pont kiemelésével:
    (x1, y1) = u1*Q + u2* kA *Q = Q*(u1 + u2* kA)

    Az aláírás készítésének 4. lépése szerint s = t-1*(e + r*kA) (modulo n), ezt átrendezve:
    t = s-1*(e + r*kA) = w*e + w*r*kA = u1 + u2*kA

    Ezt az előző egyenletbe behelyettesítve:
    (x1, y1) = Q*(u1 + u2* kA) = Q*t

    Ahol x1 az aláírás készítésének 3. lépése miatt meg kell, hogy egyezzen az aláírás r komponensével.

  6. Az ellenőrző fél akkor fogadja el az aláírást, ha x1 = r.

 

 

Hol használnak ECC-t?

 

A legtöbb nyilvános kulcsú alkalmazás jelenleg RSA-ra épül, bár sok alkalmazás támogatja az ECC-t, és vannak ECC-alapú nemzetközi hitelesítés szolgáltatók.

Az NSA 2009. végén kibocsátott, kriptográfiai algoritmusokra vonatkozó ajánlása szerint át kell térni az ECC-re, és csakis az áttérés lezártáig lehet még RSA-t használni, 2048 bites kulcshosszal.

A biometriai azonosítókat (ujjlenyomatot) tartalmazó EU-s útleveleken lévő chipekből csak arra jogosult készülékek olvashatják ki az útlevél birtokosának biometriai azonosítóit. Az útlevélchip titkosított és hitelesített csatornát épít ki az olvasókészülékkel, e csatorna felépítése során mind az útlevélchip, mind az olvasókészülék tanúsítvánnyal azonosítja magát (egy, az SSL-hez hasonló protokollon keresztül). Mind az olvasókészülékek, mind az útlevélchipek tanúsítványai egy dedikált, ECC-re épülő PKI hierarchiából származnak, és e berendezések ECC alapon egyeztetik a kapcsolat titkosításához és hitelesítéséhez használt kriptográfiai kulcsokat.