Kryptografia na báze eliptických kriviek

Kryptografia na báze eliptických kriviek (iné názvy: kryptografia pomocou eliptických kriviek, kryptografia eliptických kriviek, angl. elliptic curve cryptography, skr. ECC) je systém asymetrickej kryptografie (kryptografie s verejným kľúčom), ktorý je založený na algebrickej štruktúre eliptických kriviek nad konečnými poľami. Použitie eliptických kriviek v kryptografii navrhli nezávisle Neal Koblitz a Victor S. Miller v roku 1985.

Systém je založený na veľmi ťažkej riešiteľnosti niektorých matematických problémov. Pre protokoly založené na eliptických krivkách sa predpokladá, že nájdenie diskrétneho logaritmu prvku eliptickej krivky je nemožné. Veľkosť eliptických kriviek určuje obťažnosť problému. Predpokladá sa, že na získanie rovnakej úrovne zabezpečenia ako pri RSA systémoch možno použiť menšiu grupu. Použitie malých grúp redukuje požiadavky na ukladanie a prenos. 

 Základná matematická definícia 
 Konečné polia 
Abstraktne, konečné pole sa skladá z konečnej množiny objektov tzv. prvkov poľa, spolu s opisom dvoch operácií, sčítanie a násobenie, to možno vykonať v pároch z jednotlivých prvkov poľa. Tieto operácie musia mať určité vlastnosti. Prvky poľa charakterizuje q, ktoré predstavuje veľkosť poľa.

Ukazuje sa, že toto je konečné pole obsahujúce q prvky vtedy a len vtedy, keď qi su prvočísla. Konečné pole s q prvkami je označované ako Fq.

U eliptyckych kriviek sú použité dva druhy konečných polí Fq :
 Fp kde q = p, čo sú nepárne prvočísla, taktiež nazývané hlavné konečné polia, p je charakteristika poľa.
 F2m kde q = 2m pre m ≥ 1, taktiež nazývané charakteristické binárne konečné polia.

Je potrebné veľmi presne opísať konkrétne túto oblasť, aby sa presne špecifikovali šifrovacie systémy na základe ECC na úplnom začiatku tvorby krivky a samotných kľúcov.

 Eliptické krivky 
Eliptická krivka nad konečným poľom Fq je definovaná z hľadiska riešenia rovnice v Fq. Forma rovnice definujúca eliptickú krivku nad Fq sa líši v závislosti na tom, či konečné pole je hlavné konečné pole Fp alebo charakteristické binárne konečné pole F2m.

Formálna definícia eliptických kriviek je veľmi technicky zložitá a vyžaduje určité zázemie vysokoškolskej algebrickej geometrie.

Eliptické krivky nad F2m aj Fp sú non-supersingularne eliptické krivky:
 Geometricky to znamená, že graf nemá vrcholy alebo križovania.
 Krivka je non-singulárna vtedy a len vtedy, ak jej diskriminant je pozitívny, nerovný nule a jedna zo súčastí krivky je záporná.

 Eliptické krivky nad Fp 
Nech Fp je hlavné konečné pole tak, že p je nepárne prvočíslo a nech koeficienty a,bєFp a vyhovujú pre 4a3 +27b2 ≠ 0 (mod p). Potom eliptická krivka E(Fp) cez Fp definovaná parametrami a, b є Fp zložená zo súboru riešení alebo bodov P = (x, y) pre x, y є Fp má rovnicu:

                                                                      y2  = x3 + ax + b (mod p)

spolu s extra bodom Ό nazývaným bod v nekonečne v projektivní rovine.
Rovnica y2 = x3 + ax + b (mod p) je vymedzenie rovnice E(Fp).

Pre daný bod P = (xp, yp):
 xp je x-ová súradnica P.
 yp je y-ová súradnica P.

 Eliptické krivky nad F2m 
Nech F2m je charakteristické binárne konečné pole, a nech koeficienty a, b є F2m a vyhovujú b≠0 v F2m . Potom eliptická krivka E(F2m) cez F2m definovaná parametrami a, b є F2m zložená zo súboru riešení alebo bodov P=(x, y) pre x, y є F2m má rovnicu:

                                                                   y2 + xy = x3 + ax2 + b in F2m

spolu s extra bodom Ό nazývaným bod v nekonečne v projektívnej rovine.

 Doménové parametre eliptických kriviek 
Táto sekcia sa zaoberá adresovaním parametrov eliptickej krivky. Opisuje parametre potrebné pre eliptické krivky, ako by mali byť generované, a ako by mali byť schvaľované.

Doménové parametre Eliptických kriviek môžu byť generované náhodne, čo znamená, že parametre sú získané z časti ako výstup z bezpečnej hašovacej funkcie. Preukázateľne použité náhodné parametre eliptický kriviek sa iba odporúčajú, pretože môžu byť používané pre rôzne dôvody.

 Doménové parametre Eliptických kriviek nad Fp 
Doménové parametre eliptickej krivky nad poľom Fp:

                                                                        T = (p, a, b, G, n, h)

 p – celé prvočíslo určené z konečného poľa Fp.
 a, b є Fp - sú použité pri definovaní rovnice krivky E(Fp):
 E: y2 = x3 + ax + b (mod p)
 G - cyklická podskupina definovaná ako základný bod na krivke G = (xG, yG)
 n - určuje poradie bodu G, n musí byť prvočíslo
 h - kofaktor, vyplýva z Langrangeovej vety h = E(Fp)/n , h je celočíselná hodnota (h ≤ 4), pokiaľ možno (h = 1)

 Doménové parametre Eliptických kriviek nad F2m 
Doménové parametre eliptickej krivky nad poľom F2m:

                                                                       T = (m, f(x), a, b, G, n, h)

 m - celého číslo určené z konečného poľa F2m.
 f(x) – irreducible binárny polynom stupňa m určujúci reprezentáciu poľa F2m
 a,b є F2m - špecifikujú eliptickú krivku E(F2m):
 E: y2 + xy = x3 + ax2 + b in F2m
 G - cyklická podskupina definovaná ako základný bod na krivke G = (xG, yG)
 n - určuje poradie bodu G, n musí byť prvočíslo
 h - kofaktor, vyplýva z Langrangeovej vety h = E(Fp)/n , h je celočíselná hodnota (h ≤ 4), pokialmožno (h = 1) 

 Všeobecne 
Generovanie doménových parametrov si zvyčajne vykonáva každý účastník sám, pretože ide o počítanie počtu bodov na krivke, čo je časovo náročné a problematické realizovať. 

Špecifikácia FIPS 186-3 má desať odporúčaných dĺžok konečných polí, na základe ktorých sa potom generujú aj rôzne dĺžky kľúčov:
 Päť hlavných konečných polí Fp p192, p224, p256, p384 a p521
 Päť binárních konečných polí F2m pre 2163, 2233, 2283, 2409 a 2571.

Tieto hodnoty pre Krivky boli vybrané pre optimálnu bezpečnosť a účinnosť vykonávania.

 Kľúčový pár eliptických kriviek 
Všetky kryptografické systémy verejným kľúčom opísané v tomto dokumente používajú kľúčovú dvojicu známu ako kľúčové páry eliptickej krivky.

Kľúčové páry eliptickej krivky by mali byť tvorené nasledujúcim spôsobom:
 Input: Doménové parametre eliptickej krivky T=(p, a, b, G, n, h) alebo (m, f(x), a, b,G, n, h).
 Output: Kľúčový pár eliptickej krivky (d, Q) asociovaný s T, sa skladá z dvoch častí:
1. d - tajný zabezpečený kľúč, ktorý má celočíselnú hodnotu v intervale [1, n-1]
2. Q – verejný kľúč Q=(xQ, yQ), čo je bod Q = dG, kde G je náš základný pevný bod definovaný na krivke.

 Kryptografické systémy 
Momentálne používané kryptografické systémy s využitím eliptických kriviek:
 ECDH (Eliptic Curve Diffie-Hellman) založený na Diffieho-Hellmanovom systéme
 ECDSA (Elliptic Curve Digital Signature Algorithm) založený na štandarde DSA (Digital Signature Algorithm)
 ECMQV (Elliptic curve Menezes-Qu-Vanstone) založený na systéme MQV (Menezes-Qu-Vanstone), čo je vlastne overovací protokol pre kľúčovú dohodu založenú na Diffieho-Hellmanovom systéme.

 Referencie 
 [1] Brown, D.: Eliptic Curve Cryptography, 2009.
 [2] Don, J., Menezes, A.: The Elliptic Curve Digital Signature Algorithm, Canada, 2000.
 [3] Locke, G., Gallagher, P., Digital Signature Standard, FIPS PUB 186-3, NIST,USA, 2009

Kategória:Kryptografia