![]() |
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.
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.
Az alábbi egyenlet definiál egy F test feletti elliptikus görbét:
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ó:
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 P és Q pontjainak összeadása. P ⊕ Q = R
A görbe P(x1,y1) és Q(x2,y2) pontjainak összeadása algebrailag is definiálható a következő módon:
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)
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 Qk 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.
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:
Megjegyzés: Amikor ECC esetében bitekben kifejezett kulcshosszról beszélünk, akkor a kA 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.
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.
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
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.
Az elliptikus görbék feletti ElGamal protokoll
Megjegyzés:
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:
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:
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.
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.