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ď q_i 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.
F2^m kde q = 2^m 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 F2^m.

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 F2^m 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 4a³ +27b² ≠ 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:

                                                                     y²  = x³ + ax + b (mod p)

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

Pre daný bod P = (x_p, y_p):

x_p je x-ová súradnica P.
y_p je y-ová súradnica P.

Eliptické krivky nad F2^m

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

                                                                  y² + xy = x³ + ax² + b in F2^m

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 F_p

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: y² = x³ + ax + b (mod p)
G - cyklická podskupina definovaná ako základný bod na krivke G = (x_G, y_G)
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 F2^m

Doménové parametre eliptickej krivky nad poľom F2^m:

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

m - celého číslo určené z konečného poľa F2^m.
f(x) – irreducible binárny polynom stupňa m určujúci reprezentáciu poľa F2^m
a,b є F2^m - špecifikujú eliptickú krivku E(F2^m):
- E: y² + xy = x³ + ax² + b in F2m
G - cyklická podskupina definovaná ako základný bod na krivke G = (x_G, y_G)
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í F2^m pre 2¹⁶³, 2²³³, 2²⁸³, 2⁴⁰⁹ a 2⁵⁷¹.

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