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<sub>i</sub>** 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<sup>m</sup>** kde *q = 2<sup>m</sup>* 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<sup>m</sup>**.

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<sup>m</sup>** 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<sup>3</sup> +27b<sup>2</sup> ≠ 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<sup>2</sup>  = x<sup>3</sup> + ax + b (mod p)**

spolu s extra bodom *Ό* nazývaným bod v nekonečne v projektivní rovine.
Rovnica **y<sup>2</sup> = x<sup>3</sup> + ax + b (mod p)** je vymedzenie rovnice **E(Fp)**.

Pre daný bod **P = (x<sub>p</sub>, y<sub>p</sub>)**:
* *x<sub>p</sub>* je x-ová súradnica *P*.
* *y<sub>p</sub>* je y-ová súradnica *P*.

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

                                                                   **y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b** in **F2<sup>m</sup>**

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<sub>p</sub>
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<sup>2</sup> = x<sup>3</sup> + ax + b (mod p)*
* **G** - cyklická podskupina definovaná ako základný bod na krivke *G = (x<sub>G</sub>, y<sub>G</sub>)*
* **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<sup>m</sup>
Doménové parametre eliptickej krivky nad poľom *F2<sup>m</sup>*:

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

* **m** - celého číslo určené z konečného poľa *F2<sup>m</sup>*.
* **f(x)** – irreducible binárny polynom stupňa *m* určujúci reprezentáciu poľa F*2<sup>m</sup>*
* **a,b є F2<sup>m</sup>** - špecifikujú eliptickú krivku *E(F2<sup>m</sup>)*:
** *E: y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b in F2m*
* **G** - cyklická podskupina definovaná ako základný bod na krivke *G = (x<sub>G</sub>, y<sub>G</sub>)*
* **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<sup>m</sup>* pre **2<sup>163</sup>**, **2<sup>233</sup>**, **2<sup>283</sup>**, **2<sup>409</sup>** a **2<sup>571</sup>**.

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