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={a₁,a₂,a₃,...}, és egy köztük értelmezett művelet ("+") csoportot (G) alkotnak, ha a következők teljesülnek rájuk:

• zártság:
  ha a_i, a_j ∈ A, akkor a_i+a_j ∈ A     ∀ i, j;
• asszociativitás:
  (a_i + a_j) + a_k = a_i + (a_j + a_k)     ∀ i, j, k;
• létezik egységelem:
  ∃ a_e, amelyre a_e + a_i = a_i + a_e = a_i     ∀ i;
• minden elemnek létezik egyértelmű inverze:
  ∀ a_i ∃ a_j, amelyre a_i + a_j = a_e     ∀ i, j;

 

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

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

• F zárt a "+" és "*" műveletekre;
• F csoport a "+" műveletre, és "+" e csoportban kommutatív művelet;
• F \ {0} a "*" műveletre csoport, és "*" e csoportban kommutatív művelet, és a 0 elem az előző pontban szereplő csoport egységeleme;
• teljesül a disztributivitás, azaz:
  a_i * (a_j + a_k) = a_i * a_j + a_i * a_k     ∀ i, j, k;

 

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:

y² + axy + by = x³ + cx² + 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) ∈ F² 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ó:

y² = x³ + 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 két pontjának összeadása. Legyen a P és Q pontokon átmenő egyenes és a görbe harmadik metszéspontja -R; ennek az x tengelyre való tükörképe R, amely szintén pontja a görbének. Ekkor P ⊕ Q = R. Ha P = Q, akkor a rajtuk átmenő egyenes alatt a görbe P pontbeli érintőjét kell érteni. Ha R megegyezik a P és Q pontok valamelyikével, akkor úgy kell tekinteni, hogy az egyenes az R pontban érinti a görbét. Ezen kívül P + (-P) = O, és O + O = O.

   

  
  A görbe P és Q pontjainak összeadása. P ⊕ Q = R

  A görbe P(x₁,y₁) és Q(x₂,y₂) pontjainak összeadása algebrailag is definiálható a következő módon:

  x₃ = s² - x₁ - x₂ y₃ = s(x₁-x₃) - y₁ahol s (a görbe "meredeksége"). Ha P ≠ Q, akkor s = (y₂-y₁)/(x₂-x₁); ha P = Q, akkor s = (3x₁²+a)/2y₁.
• Pont szorzása egész számmal. A görbe Q pontjának a k egész számmal való megszorzása alatt azt érjük, hogy a Q pontot k-szor összeadjuk önmagával. (Például: 5*Q = Q ⊕ Q ⊕ Q ⊕ Q ⊕ Q.)

   

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), azaz a modulo p egész számok alkotta test, ahol p prímszám. Ekkor a görbe egyenletében mind az a és b együtthatók, mind az x és y változók GF(p)-beli egész számok. A GF(7) testben például: 2 + 2 = 4, és 4 + 4 = 1, és 4 * 4 = 2, valamint 2^-1 = 4 (mert 2 * 4 = 1), és 3 / 2 = 3 * 2-1 = 5. A GF(p) feletti görbék esetén az ⊕ művelet algebrai definíciója megegyezik a valós számok teste feletti görbék esetén használt definícióval.
• A GF(2^m) test. E test elemei m hosszú bitsorozatokként vagy m-edfokú bináris polinomokként ábrázolhatóak. A GF(2^m) ún. "2-karakterisztiájú" test, így a GF(2^m) feletti görbék esetén a görbe általános egyenlete nem alakítható y² = x³ + ax + b alakra, így a valós számok teste feletti görbék esetén használt definíció egy az egyben nem alkalmazható. (A GF(2^m) esetre alkalmazható képletek a görbe általános egyenletéből vezethetőek le.)

 

A GF(p) és GF(2^m) 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(2^m) 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 y² = x³ + 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 Q és a Q^k pontok ismeretében k 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 k_A véletlen számot. Ez lesz az ő magánkulcsa.
2. Megszorozza a Q pontot a k_A számmal, a k_A * Q pont lesz az ő nyilvános kulcsa.

 

Megjegyzés: Amikor ECC esetében bitekben kifejezett kulcshosszról beszélünk, akkor a k_A magá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 k_A * Q nyilvános kulcsot. Bendegúz elküldi Alajosnak a k_B * 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 k_A-t, sem k_B-t.
2. Mindkét fél megszorozza a kapott nyilvános kulcsot a saját magánkulcsával:
   Alajos kiszámítja a (k_B * Q) * k_A = k_A * k_B * Q értéket.
   Bendegúz kiszámítja a (k_A * Q ) * k_B = k_A * k_B * Q értéket.

 

Az eredményül kapott, k_A * k_B * 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*(k_A * 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 (k_A*Q) értéket (azaz Alajos nyilvános kulcsát) ismeri, a k_Amagánkulcsot nem.

    

    

3. Alajos a kapott r*Q pontot megszorozza a saját k_A magánkulcsával, így megkapja az r * k_A * Q pontot. E pontot kivonja a kapott M ⊕ r*(k_A * 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 * k_A * 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:

Az EC ElGamal titkosításhoz friss véletlen szám generálására van szükség, míg az

RSA

titkosítás önmagában determinisztikus művelet, nem igényel véletlen számot. Általában is igaz, hogy jó minőségű titkosításhoz randomizálásra van szükség, mert ha teljesen determinisztrikus titkosítást alkalmazunk, akkor a támadó észleli, ha kétszer ugyanazt az üzenetet küldjük el. RSA esetében is szokás randomizálni, véletlen padding alkalmazásával.

 

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*k_A) (modulo n) értéket. (E művelethez van szükség a k_A 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ó k_A*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 u₁ = (e*w) értéket.
4. Kiszámítja az u₂ = r*w (modulo n) értéket.
5. Kiszámítja a görbe (x₁, y₁) = u₁*Q + u₂* k_A *Qpontját.

    

   Ebből a Q pont kiemelésével:
   (x₁, y₁) = u₁*Q + u₂* k_A *Q = Q*(u1 + u2* k_A)

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

   Ezt az előző egyenletbe behelyettesítve:
   (x₁, y₁) = Q*(u1 + u2* k_A) = Q*t

   Ahol x₁ 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 x₁ = 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.