Eliptická křivka

Eliptická křivka je hladká spojitá křivka, která je definována rovnicí ${\displaystyle y^{2}+2xy=ax^{3}+bx^{2}+cx+d}$, což lze upravit na tzv. Weierstrassův tvar ${\displaystyle y^{2}=x^{3}+ax+b}$.

Pokud platí, že ${\displaystyle 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. Na eliptické křivce můžeme definovat bod v nekonečnu, který se obvykle označuje jako bod O.

Eliptická křivka nad reálnými čísly

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

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

Sčítání bodů na eliptické křivce

Graficky

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í ${\displaystyle R=P+Q}$.

Pokud by platilo, že ${\displaystyle -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 ${\displaystyle P+(-P)=O}$.

Pokud by nastala situace, že ${\displaystyle 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 ${\displaystyle P=Q}$ a ${\displaystyle y=0}$, jeho zdvojením tečna protne eliptickou křivku v nekonečnu v pomyslném bodě O, řekneme tedy, že ${\displaystyle 2P=O}$. Pokud bychom chtěli bod P ztrojnásobit, získáme opět bod P, neboť platí ${\displaystyle 3P=2P+P=O+P=P}$.

Algebraicky

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 ${\displaystyle {\textrm {tg}}\,\alpha }$, ${\displaystyle 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:
${\displaystyle x_{R}=s^{2}-x_{P}-x_{Q}}$
${\displaystyle y_{R}=s(x_{P}-x_{R})-y_{P}}$

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

Eliptická křivka nad tělesem ${\displaystyle F_{p}}$

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 ${\displaystyle F_{p}}$.

Poznamenejme, že s tělesem ${\displaystyle F_{p}}$ pracujeme jako s množinou zbytkových tříd modulo p, počítáme tedy s čísly 0 až ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle F_{p}}$ může být vytvořena z libovolných čísel a, b, která jsou však v tělese ${\displaystyle F_{p}}$. Eliptická křivka obsahuje všechny body o souřadnicích [x;y], které vyhovují rovnici ${\displaystyle y^{2}\equiv x^{3}+ax+b\mod p}$.

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

Sčítání bodů na eliptické křivce nad tělesem ${\displaystyle F_{p}}$

Sčítání bodů na eliptické křivce nad tělesem ${\displaystyle 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 ${\displaystyle F_{p}}$, tedy modulo p.

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

Pro 2P:
${\displaystyle s\equiv {\frac {3x_{P}^{2}+a}{2y_{P}}}\mod p}$
${\displaystyle x_{R}\equiv s^{2}-2x_{P}\mod p}$
${\displaystyle 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

Prvky eliptických křivek nad ${\displaystyle 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ů.

Literatura

• Silverman, J. H..: Rational Points on Elliptic Curves, 1992, ISBN 978-0-387-97825-3

Související články

• Diffie-Hellman protokol s využitím eliptických křivek
• Kryptografie nad eliptickými křivkami
• Protokol digitálního podpisu s využitím eliptických křivek

Externí odkazy

• http://brkos.math.muni.cz/files/download/elipticke-krivky.pdf
• http://www.certicom.com/
• Obrázky, zvuky či videa k tématu eliptická křivka na Wikimedia Commons