ECDLP

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. ledna 2015; kontroly vyžadují 13 úprav .

ECDLP (Elliptic Curve Discrete Logarithm Problem) je problém diskrétního logaritmu ve skupině bodů eliptické křivky .

Nechť je dána eliptická křivka E, konečné pole F p a body P, Q ∈ E(F p ). Úkolem ECDLP je najít takové k, pokud existuje, že Q = [k]P.

Definice

Eliptická křivka E nad konečným polem F p je křivka tvaru (Weierstrassova forma):

E:Y^{2}=X^{3}+aX+b

, kde a, b ∈ F p .

Množina bodů na eliptické křivce v poli F p , včetně bodu "nekonečno" (označeno Ο), tvoří konečnou abelovskou grupu a označíme ji E(F p ) .

Bod Q ∈E (F p ) se nazývá inverzní bod k P ∈ E(F p ), pokud P + Q = Ο a je označen jako Q = -P .

Pro přirozené číslo n a P ∈ E(F p ) předpokládáme:

{\displaystyle [n]P=\underbrace {P+P+...+P} _{n))

Označení [n]P a nP jsou ekvivalentní. Definici lze rozšířit na libovolné celé číslo n pomocí -P.

Řád skupiny bodů je číslo N rovné kardinalitě množiny E(F p ) a značí se |E(F p )| =N . Obvykle v eliptické kryptografii se křivky berou tak, že N = h * l, kde h = 1, 2 nebo 4 a l je velké prvočíslo.

Řád bodu P ∈ E(Fp) je minimální číslo s takové, že [s]P = Ο. V tomto případě se vytvoří podskupina a bod P se nazývá generátor . $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ $\langle P\rangle$

Algoritmy řešení

Úplný výčet

Je to nejjednodušší útok na implementaci. Je pouze nutné umět provést operaci R = [k]P.

Algoritmus

$k:=1$
$R:=[k]P$
pokud , tak - rozhodnutí $R=Q$ $k$
jinak ; přejděte na [2]. $k:=k+1$

Složitost algoritmu: Ο(N).

Polig-Hellmanův algoritmus

Popis

Nechť G je podgrupa E(F p ), (to znamená, že se předpokládá, že číslo N lze faktorizovat) a . $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ $P,Q\in G$ $\exists k:Q=[k]P$

Vyřešíme problém nalezení k modulo , pak pomocí čínské věty o zbytku najdeme řešení k modulo N. ${p_{i}}^{e_{i}}$

Z teorie grup je známo, že existuje skupinový izomorfismus:

\phi :G\rightarrow C_{{p_{1}}^{e_{1}}}\otimes ...\otimes C_{{p_{t}}^{e_{t}}}

kde je cyklická podgrupa G, $C_{{p_{i}}^{e_{i}}}$ $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$

Poté projekce na : $\phi$ $C_{p^{e))$

\phi _{p}={\begin{cases}G\arrowarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\ end{cases}}

Proto v . ${\phi _{p}}(Q)=[k]{\phi _{p}}(P)$ $C_{p^{e))$

Ukážeme si, jak problém vyřešit v , redukujeme jej na řešení ECDLP v . $C_{p^{e))$ $C_p$

Nechte a . $P,Q\in C_{p^{e}}$ $\exists k:Q=[k]P$

Číslo je definováno modulo . Potom k lze napsat v následujícím tvaru: $k$ ${\displaystyle p^{e))$

k=k_{0}+{k_{1}}p+...+{k_{e-1}}p^{e-1}

Pojďme najít hodnoty indukcí. Předpokládejme, že víme - hodnotu , tzn $k_{0},k_{1},...$ $k'$ ${\displaystyle k\ mod\ p^{t))$

{\displaystyle k'=k_{0}+...+k_{t-1}p^{t-1))

Nyní chceme určit a tedy vypočítat : $k_t$ $k\ mod\ p^{t+1}$

k=k'+p^{t}k''

Pak . $Q=[k']P+[k'']([p^{t}]P)$

Nechte a pak $Q'=Q-[k']P$ $P'=[p^{t}]P$ $Q'=[k'']P'$

Nyní - prvek řádu , k získání prvku řádu a tedy k redukci problému na je nutné vynásobit předchozí výraz číslem . Že. $P'$ ${\displaystyle p^{et))$ $p$ $C_p$ ${\displaystyle s=p^{et-1))$

Q''=[s]Q'

P''=[s]P'

Přijato ECDLP v terénu jako . $C_p$ $Q''=[k_{t}]P''$

Za předpokladu, že tento problém lze vyřešit v , najdeme řešení v . Pomocí čínské věty o zbytku získáme řešení ECDLP v . $C_p$ $k$ $C_{p^{e))$ $E(F_p)$

Jak bylo uvedeno výše, v praxi se eliptické křivky berou tak, že , kde je velmi velké prvočíslo, což činí tuto metodu neúčinnou. $N=hl$ $l$

Příklad

$Q=[k]P\ (mod\ 1009)$

$E:y^{2}\equiv x^{3}+71x+602\ (mod\ 1009)$

$P=(1,237),Q=(190,271)$

$N=1060=2^{2}*5*53$

$|\langle P\rangle |=530=2*5*53$

Krok 1. Najděte $k\ mod\ 2$

Najdeme projekce bodů na : $C_{2}$

P_{2}=265P=(50,0)

Q_{2}=265Q=(50,0)

rozhodujeme se ${\displaystyle Q_{2}=[k]P_{2))$

k\equiv 1\ (mod\ 2)

Krok 2. Najděte $k\ mod\ 5$

Najdeme projekce bodů na : $C_{5}$

P_{5}=106P=(639,160)

Q_{5}=106Q=(639,849)

rozhodujeme se $Q_{5}=[k]P_{5}$

Všimněte si toho

Q_{5}=-P_{5}

k\equiv 4\ (mod\ 5)

Krok 3. Najděte $k\ mod\ 53$

Najdeme projekce bodů na : $C_{53}$

P_{53}=10P=(32,737)

Q_{53}=10Q=(592,97)

rozhodujeme se $Q_{53}=[k]P_{53}$

k\equiv 48\ (mod\ 53)

Krok 4. Najděte $k\ mod\ 530$

Z čínské věty o zbytku pro hodnoty získané v předchozích krocích 1-3 to máme

k\equiv 419\ (mod\ 530)

Shanksův algoritmus (metoda Baby-Step/Giant-Step)

Popis

Dovolit být cyklická podskupina . $G=\langle P\rangle$ $E(F_{p});|\langle P\rangle |=l;Q\in G$

Uveďme to ve tvaru: $k$

k=k_{0}+k_{1}\lceil {\sqrt {l))\rceil

Od té doby . $k\leq l$ $0\leq k_{0},k_{1}<\lceil {\sqrt {l))\rceil$

Vypočítáme seznam "malých kroků" a uložíme dvojice . $P_{i}=[i]P$ $0\leq i<\lceil {\sqrt {l))\rceil$ $(P_{i},i)$

Složitost výpočtů: . $O(\lceil {\sqrt {l))\rceil )$

Nyní vypočítáme „velké kroky“. Pojďme najít . _ $P'=[\lceil {\sqrt {l}}\rceil ]P$ $Q_{j}=Q-[j]P'$ $0\leq j<\lceil {\sqrt {l))\rceil$

Během hledání se snažíme najít mezi uloženými dvojicemi takové, že . Pokud by bylo možné takový pár najít, pak . $Q_{j}$ $(P_{i},i)$ ${\displaystyle P_{i}=Q_{j))$ $k_{0}=i,k_{1}=j$

Nebo, což je totéž:

[i]P=Q-[j\lceil {\sqrt {l))\rceil ]P,

[i+j\lceil {\sqrt {l}}\rceil ]P=Q

Složitost výpočtů "velkých kroků": . $O(\lceil {\sqrt {l))\rceil )$

V tomto případě je celková složitost metody , ale také vyžaduje paměť pro ukládání, což je značná nevýhoda algoritmu. $O({\sqrt {l)))$ $S({\sqrt {l)))$

Algoritmus

$m:=\lceil {\sqrt {l))\rceil$
$\mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {dělat}$ $R:=[i]P$ Uložit $(R,i)$
$\mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {dělat}$ $T:=Q-[j\lceil {\sqrt {l))\rceil ]P$ check -in seznam [2] $T$
$\mathbf {if} \ T=R\ \mathbf {pak}$ $k:=i+j\lceil {\sqrt {l))\rceil \ (mod\ l)$ $\mathbf {return} \k$

Pollardova ρ-metoda

Popis

Dovolit být cyklická podskupina . $G=\langle P\rangle$ $E(F_{p});|G|=r;Q\in G$

Hlavní myšlenkou metody je najít odlišné páry a modulo tak, aby . $(c',d')$ $(c'',d'')$ $r$ $[c']P+[d']Q=[c'']P+[d'']Q$

Potom nebo . Proto, . $[c'-c'']P=[d''-d']Q$ $Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$

K realizaci této myšlenky zvolíme náhodnou funkci pro iterace a náhodný bod pro zahájení procházení. Další bod se vypočítá jako . $f:G\rightarrow G$ $P_0$ $P_{i+1}=f(P_{i})$

Protože je konečný, existují takové indexy , že . $G$ $i<j$ ${\displaystyle P_{i}=P_{j))$

Pak . $P_{i+1}=f(P_{i})=f(P_{j})=P_{j+1}$

Vlastně pro . ${\displaystyle P_{i+l}=P_{j+l))$ $\forall l\geq 0$

Potom je sekvence periodická s tečkou (viz obrázek). $\{P_{i}\}$ $ji$

Vzhledem k tomu, že f je náhodná funkce, podle narozeninového paradoxu se náhoda stane přibližně po iteracích. Pro urychlení hledání kolizí se používá metoda vynalezená společností Floyd k nalezení délky cyklu: dvojice hodnot se vypočítá najednou, dokud není nalezena shoda. ${\displaystyle {\sqrt {\frac {\pi r}{2))))$ $(P_{i},P_{2i})$ $i=1,2,...$

Algoritmus

Inicializace. Vyberte počet poboček L (obvykle se bere 16) Vyberte funkci $H:\langle P\rangle \rightarrow {1,2,...,L}$
Výpočet . $[a_{i}]P+[b_{i}]Q$ $\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {dělat}$ Vezměte náhodně $a_{i},b_{i}\in [0,r-1]$ $R_{i}:=[a_{i}]P+[b_{i}]Q$
Výpočet . $[c']P+[d']Q$ Vezměte náhodně $c',d'\in [0,r-1]$ $X':=[c']P+[d']Q$
Příprava na cyklus. $X'':=X',c'':=c',d'':=d'$
Cyklus. $\mathbf {repeat}$ $j:=H(X')$ ${\displaystyle X':=X'+R_{j))$ $c':=c'+a_{j}\ (mod\ r)$ $d':=d'+b_{j}\ (mod\ r)$ $\mathbf {for} \ i:=1\ \mathbf {to} \ 2\ \mathbf {dělat}$ $j:=H(X'')$ ${\displaystyle X'':=X''+R_{j))$ $c'':=c''+a_{j}\ (mod\ r)$ $d'':=d''+b_{j}\ (mod\ r)$ $\mathbf {dokud} \ X'=X''$
Výstup. $\mathbf {if} d'\neq d''\ \mathbf {pak}$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ $\mathbf {else}$ CHYBA nebo spusťte algoritmus znovu.

Složitost algoritmu: . $O({\sqrt {r)))$

Příklad

$Q=[k]P\ (mod\ 229)$

$E:y^{2}\equiv x^{3}+x+44\ (mod\ 229)$

$P=(5,116),Q=(155,166)$

$|\langle P\rangle |=239$

Krok 1. Definujte funkci.

$H:\langle P\rangle \rightarrow {1,2,3,4}$
$H(x,y)=(x\ mod\ 4)+1$
$(a_{1},b_{1},R_{1})=(79,163,(135,117))$
$(a_{2},b_{2},R_{2})=(206,19,(96,97))$
$(a_{3},b_{3},R_{3})=(87.109,(84.62))$
$(a_{4},b_{4},R_{4})=(219,68,(72,134))$

Krok 2. Iterace.

${\begin{array}{c|ccc|ccc}Iterace&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\ \\hline 0&54&175&(39,159)&54&175&(39,159)\\1&34&4&(160,9)&113&167&(130,182)\\0,182)\\0,182)\\0,182)\\0,182)\\0,182)\\0,182)\\0,182)\\0,182)\\2&113&167&(130,182,3&07)\&\81,3&27(0)\&\81,3&270\&\\07&270 (36,97) & 46 & 40 & (223,153) \\ 5 & 20 & 29 & (119,180) a 232 & 127 & (167,57) \\ 6 & 0 & 97 & (108,89) & 192 & 24 & (57,16 & & (1816 & (2217 & (185,227 & (57 a (18117 a (57,117 & (57,1117 & (57,1117 & (57,1117 &. (197.92) \\ 9 a 26 & 108 & (9.18) a 140 & 87 & (194,145) \\ 10 & 232 & 127 & (167,57) & 67 & 120 & (223,153) \\ 11 & 212 & 195 & 215 & (161.57) \ 57 & \ \ \ 575 & \ \ \ \ Mathb)} a (1615)} a (1615) & (161.57) \ Math (161.57 & (161.57) &. )} \\\end{array}}$

Krok 3 Detekce kolize

v : $i=12$ $[192]P+[24]Q=[213]P+[104]Q=(57,105)$
Chápeme to $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$

Literatura

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Základní úvod do eliptické kryptografie: Algebraické a algoritmické základy. - M .: KomKniga, 2006. - S. 328. - ISBN 5-484-00443-8 .

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Elementary Introduction to eliptic cryptography: Elliptic curve cryptography protocols. - M .: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP HODNOCENÍ ZPRÁVA PRO CRYPTREC: BEZPEČNOSTNÍ ÚROVEŇ KRYPTOGRAFIE - MATEMATICKÝ PROBLÉM ECDLP.

Song Y. Yan Quantum Attacks on ECDLP-based Cryptosystems. – Springer USA, 2013 – ISBN 978-1-4419-7721-2