Eliptická křivka

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Eliptické křivky, [-3;3] není nesingulární, má ostrý bod

Eliptická křivka je hladká spojitá křivka, na které definujeme bod O, což je bod v nekonečnu.

Její rovnice je y^2 + 2xy = ax^3 + bx^2 + cx + d, což lze upravit na tzv. Weierstrassův tvar y^2 = x^3 + ax + b.

Pokud platí, že 4a^3 + 27b^2 = 0, kde a, b jsou koeficienty z Weierstrassova tvaru, pak není křivka nesingulární (má ostrý bod) a nejedná se tedy o eliptickou křivku.

Eliptická křivka nad reálnými čísly[editovat | editovat zdroj]

Sčítání bodů P, Q
Sčítání bodů P, -P
Zdvojnásobení bodu P

Eliptickou křivku nad reálnými čísly můžeme definovat jako skupinu souřadnic [x;y], které vyhovují rovnici y^2=x^3+ax+b, kde a, b, x, y ∈ \mathbb{R}.

Pokud je daná eliptická křivka nesingulární, může zformovat grupu.

Sčítání bodů na eliptické křivce[editovat | editovat zdroj]

Graficky[editovat | editovat zdroj]

Grupy eliptických křivek jsou aditivní grupy, to znamená, že základní operace je zde sčítání. Sčítání dvou bodů na eliptické křivce je definováno geometricky.

Opačný bod k bodu P[x;y] je bod −P[x;−y], je tedy zobrazen osovou souměrností podle osy x. Ke každému bodu P existuje bod −P.

Předpokládejme, že body P a Q jsou dva různé body na eliptické křivce a že −P ≠ Q. Abychom tyto dva body sečetli graficky, musíme jimi proložit přímku, která eliptickou křivku protne ještě v právě jednom bodě. Tento bod můžeme nazvat −R. Obraz tohoto bodu je hledaný bod R, kde platí R=P+Q.

Pokud by platilo, že -P=Q, pak můžeme říct, že bod Q je opačný k bodu P, tedy že mají stejnou souřadnici x. Sečteme-li tyto dva body (proložíme-li jimi přímku), nezískáme další průsečík s eliptickou křivkou. Tato přímka však eliptickou křivku protne v nekonečnu v pomyslném bodu O, můžeme tedy říct, že P+(-P)=O.

Pokud by nastala situace, že P=Q, pak bychom mohli říct, že chceme bod P zdvojnásobit. Tuto operaci učiníme tak, že uděláme tečnu k eliptické křivce s bodem dotyku P. Tato tečna protne eliptickou křivku v právě jednom bodě, který můžeme nazvat −R, jeho obraz R je bod, který hledáme.

Pokud by nastala situace, kdy P=Q a y=0, jeho zdvojením tečna protne eliptickou křivku v nekonečnu v pomyslném bodě O, řekneme tedy, že 2P=O. Pokud bychom chtěli bod P ztrojnásobit, získáme opět bod P, neboť platí 3P=2P+P=O+P=P.

Algebraicky[editovat | editovat zdroj]

Další možností, jak sčítat body na eliptické křivce, je použití algebraických výpočtů. Tento způsob je nutný například u kryptografie na bázi eliptických křivek.

V první řadě musíme určit směrnici přímky, na které leží body P a Q. Tuto směrnici s vypočítáme jako \textrm{tg}\, \alpha, s=\frac{y_{p}-y_{q}}{x_{p}-x_{q}}.

Díky Viète-Newtonovým vztahům můžeme říct, že pokud Q ≠ −P, pak:
x_{R} = s^2 - x_{P} - x_{Q}
y_{R} = s(x _{P}-x_{R}) - y_{P}


Pro zdvojnásobení bodu P, kde y_{P} \ne 0, platí, že:
s=\frac{3x_{P}^2+a}{2y_{P}}
x_{R}=s^2-2x_{P}
y_{R}=s(x_{P}-x_{R})-y_{P}

Eliptická křivka nad tělesem F_{p}[editovat | editovat zdroj]

Počítání nad reálnými čísly je pomalé a nepřesné z důvodu zaokrouhlování. Kryptografické aplikace potřebují přesné a rychlé výpočty, proto se v praxi používají eliptické křivky nad tělesem F_{p}.

Poznamenejme, že s tělesem F_{p} pracujeme jako s množinou zbytkových tříd modulo p, počítáme tedy s čísly 0 až p-1 a že končíme výpočet tehdy, když máme zbytek po dělení prvočíslem p v tomto rozmezí. Pro těleso F_{23} tedy počítáme s přirozenými čísly 0 až 22 a výsledkem matematických operací bude opět číslo v rozmezí 0 až 22.

Eliptická křivka nad tělesem F_{p} může být vytvořena z libovolných čísel a, b, která jsou však v tělese F_{p}. Eliptická křivka obsahuje všechny body o souřadnicích [x;y], které vyhovují rovnici y^2 \equiv x^3 + ax + b \mod p.

Pokud 4a^3 + 27b^2 \mod p \ne 0, pak eliptická křivka může zformovat grupu.

Sčítání bodů na eliptické křivce nad tělesem F_{p}[editovat | editovat zdroj]

Sčítání bodů na eliptické křivce nad tělesem F_{p} již nelze provádět efektivně graficky, používá se pouze algebraický postup.

Algebraický postup se od sčítání na eliptické křivce nad reálnými čísly příliš neliší, veškeré rovnice pouze budeme uvažovat nad tělesem F_{p}, tedy modulo p.

Pro -P \ne Q:
s \equiv \frac {y_{P}-y_{Q}}{x_{P}-x_{Q}}\mod p
x_{R} \equiv s^2 - x_{P} - x_{Q} \mod p
y_{R} \equiv s(x_{P}-x_{R})-y_{P} \mod p


Pro 2P:
s \equiv \frac {3x_{P}^2+a}{2y_{P}}\mod p
x_{R} \equiv s^2 - 2x_{P} \mod p
y_{R} \equiv s(x_{P}-x_{R})-y_{P} \mod p


Také opačné body se počítají modulo p, tedy pro P[x;y] máme −P[x;−y modulo p].

Eliptické křivky nad m-bitovými řetězci[editovat | editovat zdroj]

Prvky eliptických křivek nad F_{2^m} jsou m-bitové řetězce, tedy m je počet číslic, které můžeme použít, a 2 udává binární soustavu. Na této křivce je vždy konečný počet bodů.

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

Kategorie Elliptic curves ve Wikimedia Commons