ECDLP

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 26 ianuarie 2015; verificările necesită 13 modificări .

ECDLP (Elliptic Curve Discrete Logarithm Problem) este o problemă de logaritm discret într-un grup de puncte ale unei curbe eliptice .

Să fie date o curbă eliptică E, un câmp finit F p , și punctele P, Q ∈ E(F p ). Sarcina ECDLP este să găsească un astfel de k, dacă există, încât Q = [k]P.

Definiții

O curbă eliptică E peste un câmp finit F p este o curbă de forma (forma Weierstrass):

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

, unde a, b ∈ F p .

Mulțimea punctelor de pe o curbă eliptică din câmpul F p , inclusiv punctul „infinit” (notat cu Ο), formează un grup abelian finit și este notat cu E(F p ) .

Un punct Q ∈E (F p ) se numește punct invers față de P ∈ E(F p ) dacă P + Q = Ο și se notează Q = -P .

Pentru un număr natural n și P ∈ E(F p ) presupunem:

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

Notațiile [n]P și nP sunt echivalente. Definiția poate fi extinsă la orice număr întreg n folosind -P.

Ordinea unui grup de puncte este numărul N egal cu cardinalitatea mulțimii E(F p ) și se notează |E(F p )| =N . De obicei, în criptografia eliptică, curbele sunt luate astfel încât N = h * l, unde h = 1, 2 sau 4 și l este un număr prim mare.

Ordinea unui punct P ∈ E(Fp) este numărul minim s astfel încât [s]P = Ο. În acest caz, se formează un subgrup și punctul P se numește generator . $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ $\langle P\rangle$

Algoritmi de soluție

Enumerarea completă

Este cel mai simplu atac de implementat. Este necesar doar să se poată efectua operația R = [k]P.

Algoritm

$k:=1$
$R:=[k]P$
dacă , atunci - soluție $R=Q$ $k$
altceva ; mergeți la [2]. $k:=k+1$

Complexitatea algoritmului: Ο(N).

Algoritmul Polig-Hellman

Descriere

Fie G un subgrup al lui E(F p ), (adică se presupune că numărul N poate fi factorizat) și . $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ $P,Q\in G$ $\exists k:Q=[k]P$

Vom rezolva problema găsirii k modulo , apoi, folosind teorema chineză a restului , vom găsi soluția k modulo N. ${p_{i}}^{e_{i}}$

Din teoria grupurilor se știe că există un izomorfism de grup:

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

unde este un subgrup ciclic al lui G, $C_{{p_{i}}^{e_{i}}}$ $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$

Apoi proiecția pe : $\phi$ $C_{p^{e)}$

\phi _{p}={\begin{cases}G\rightarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\ sfârșit{cazuri}}

Prin urmare, în . ${\phi _{p}}(Q)=[k]{\phi _{p}}(P)$ $C_{p^{e)}$

Să arătăm cum să rezolvăm problema în , reducând-o la rezolvarea ECDLP în . $C_{p^{e)}$ $C_p$

Lasă și . $P,Q\in C_{p^{e}}$ $\exists k:Q=[k]P$

Numărul este definit modulo . Atunci k poate fi scris sub următoarea formă: $k$ $p^{e)$

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

Să găsim valorile prin inducție. Să presupunem că știm - valoarea , adică $k_{0},k_{1},...$ $k'$ $k\mod\p^{t)$

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

Acum vrem să determinăm și astfel să calculăm : $k_t$ $k\mod\p^{t+1}$

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

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

Lasă și apoi $Q'=Q-[k']P$ $P'=[p^{t}]P$ $Q'=[k'']P'$

Acum - elementul de ordine , pentru a obține elementul de ordine și, prin urmare, pentru a reduce problema la este necesar să se înmulțească expresia anterioară cu . Acea. $P'$ $p^{et)$ $p$ $C_p$ $s=p^{et-1)$

Q''=[s]Q'

și

P''=[s]P'

A primit ECDLP pe teren ca . $C_p$ $Q''=[k_{t}]P''$

Presupunând că această problemă poate fi rezolvată în , găsim soluția în . Folosind teorema chineză a restului, obținem soluția ECDLP în . $C_p$ $k$ $C_{p^{e)}$ $E(F_p)$

După cum sa menționat mai sus, în practică, curbele eliptice sunt luate astfel încât , unde este un număr prim foarte mare, ceea ce face ca această metodă să fie ineficientă. $N=hl$ $l$

Exemplu

$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$

Pasul 1. Găsiți $k\mod\2$

Găsim proiecțiile punctelor pe : $C_{2}$

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

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

Noi decidem $Q_{2}=[k]P_{2)$

k\equiv 1\(mod\2)

Pasul 2. Găsiți $k\mod\5$

Găsim proiecțiile punctelor pe : $C_{5}$

P_{5}=106P=(639.160)

Q_{5}=106Q=(639.849)

Noi decidem $Q_{5}=[k]P_{5}$

Rețineți că atunci

Q_{5}=-P_{5}

k\equiv 4\(mod\5)

Pasul 3. Găsiți $k\mod\53$

Găsim proiecțiile punctelor pe : $C_{53}$

P_{53}=10P=(32.737)

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

Noi decidem $Q_{53}=[k]P_{53}$

k\equiv 48\ (mod\ 53)

Pasul 4. Găsiți $k\mod\530$

Din teorema chineză a restului pentru valorile obținute în pașii anteriori 1-3, avem că

k\equiv 419\ (mod\ 530)

Algoritmul lui Shanks (metoda Baby-Step/Giant-Step)

Descriere

Fie un subgrup ciclic al . $G=\langle P\rangle$ $E(F_{p});|\langle P\rangle |=l;Q\in G$

Să o punem sub forma: $k$

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

De când , atunci . $k\leq l$ $0\leq k_{0},k_{1}<\lceil {\sqrt {l)}\rceil$

Calculăm lista de „pași mici” și salvăm perechile . $P_{i}=[i]P$ $0\leq i<\lceil {\sqrt {l)}\rceil$ $(P_{i},i)$

Complexitatea calculelor: . $O(\lceil {\sqrt {l)}\rceil )$

Acum calculăm „pașii mari”. Să găsim . _ $P'=[\lceil {\sqrt {l}}\rceil ]P$ $Q_{j}=Q-[j]P'$ $0\leq j<\lceil {\sqrt {l)}\rceil$

În timpul căutării, încercăm să găsim printre perechile salvate astfel încât . Dacă a fost posibil să găsești o astfel de pereche, atunci . $Q_{j}$ $(P_{i},i)$ $P_{i}=Q_{j)$ $k_{0}=i,k_{1}=j$

Sau, care este la fel:

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

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

Complexitatea calculelor „pașilor mari”: . $O(\lceil {\sqrt {l)}\rceil )$

În acest caz, complexitatea generală a metodei , dar necesită și memorie pentru stocare, ceea ce este un dezavantaj semnificativ al algoritmului. $O({\sqrt {l))}$ $S({\sqrt {l))}$

Algoritm

$m:=\lceil {\sqrt {l)}\rceil$
$\mathbf {pentru} \ i:=1\ \mathbf {la} \ m\ \mathbf {a face}$ $R:=[i]P$ Salvați $(R,i)$
$\mathbf {pentru} \ j:=1\ \mathbf {la} \ m\ \mathbf {a face}$ $T:=Q-[j\lceil {\sqrt {l)}\rceil ]P$ lista de înregistrare [2] $T$
$\mathbf {dacă} \ T=R\ \mathbf {atunci}$ $k:=i+j\lceil {\sqrt {l))\rceil \ (mod\l)$ $\mathbf {întoarcere} \k$

Metoda ρ a lui Pollard

Descriere

Fie un subgrup ciclic al . $G=\langle P\rangle$ $E(F_{p});|G|=r;Q\in G$

Ideea principală a metodei este de a găsi perechi distincte și modulo astfel încât . $(c',d')$ $(c'',d'')$ $r$ $[c']P+[d']Q=[c'']P+[d'']Q$

Apoi sau . Prin urmare, . $[c'-c'']P=[d''-d']Q$ $Q={\frac {c'-c''}{d''-d'}}P\ (mod\r)$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\r)$

Pentru a implementa această idee, alegem o funcție aleatoare pentru iterații și un punct aleatoriu pentru a începe traversarea. Următorul punct este calculat ca . $f:G\rightarrow G$ $P_0$ $P_{i+1}=f(P_{i})$

Deoarece este finit, există indici astfel încât . $G$ $i<j$ $P_{i}=P_{j)$

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

De fapt , pentru . $P_{i+l}=P_{j+l)$ $\forall l\geq 0$

Apoi succesiunea este periodică cu o perioadă (vezi figura). $\{P_{i}\}$ $ji$

Deoarece f este o funcție aleatorie, conform paradoxului zilei de naștere , coincidența se va întâmpla după aproximativ iterații. Pentru a accelera căutarea coliziunilor, se utilizează o metodă inventată de Floyd pentru a găsi lungimea ciclului: o pereche de valori pentru este calculată dintr-o dată până când este găsită o potrivire. ${\sqrt {\frac {\pi r}{2}}}$ $(P_{i}, P_{2i})$ $i=1,2,...$

Algoritm

Inițializare. Alegeți numărul de ramuri L (de obicei se ia 16) Selectați funcția $H:\langle P\rangle \rightarrow {1,2,...,L}$
Calculul . $[a_{i}]P+[b_{i}]Q$ $\mathbf {pentru} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$ Luați la întâmplare $a_{i},b_{i}\in [0,r-1]$ $R_{i}:=[a_{i}]P+[b_{i}]Q$
Calculul . $[c']P+[d']Q$ Luați la întâmplare $c',d'\in [0,r-1]$ $X':=[c']P+[d']Q$
Pregătirea pentru un ciclu. $X'':=X',c'':=c',d'':=d'$
Ciclu. $\mathbf {repetare}$ $j:=H(X')$ $X':=X'+R_{j)$ $c':=c'+a_{j}\ (mod\r)$ $d':=d'+b_{j}\ (mod\r)$ $\mathbf {pentru} \ i:=1\ \mathbf {la} \ 2\ \mathbf {a face}$ $j:=H(X'')$ $X'':=X''+R_{j)$ $c'':=c''+a_{j}\ (mod\r)$ $d'':=d''+b_{j}\ (mod\r)$ $\mathbf {până la} \ X'=X''$
Ieșire. $\mathbf {dacă} d'\neq d''\ \mathbf {atunci}$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\r)$ $\mathbf {altfel}$ EROARE sau rulați algoritmul din nou.

Complexitatea algoritmului: . $O({\sqrt {r))}$

Exemplu

$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$

Pasul 1. Definiți funcția.

$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))$

Pasul 2. Iterații.

${\begin{array}{c|ccc|ccc}Iterație&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\ \\hlinia 0&54&175&(39.159)&54&175&(39.159)\\1&34&4&(160,9)&113&167&(130.182)\\2&113&167&(130.182)&34&4&(160,9)&113&167&(130.182)\\2&113&167&(130.182)&34&4&(160,9)&113&167&(130.182)\\2&113&167&(130.182)&34&4&(160,9)&113&167&(130.182)\\2&113&167&(130.182)&34&4&(160,9)&113&167&(130.182) (36,97) & 46 & 40 & (223.153) \\ 5 & 20 & 29 & (119,180) & 232 & 127 & (167,57) \\ 6 & 0 & 97 & (108,89) & 192 & 24 & (57,105) \\ 7 & 79 & 21 & (81.168) & 139 & 111 & (185 și 21 și (81.168) & 139 & 111 și (185 și 22 și (81.168) & 139 & 223 & 111 și (185 și 2 (197.92) \\ 9 & 26 & 108 & (9.18) & 140 & 87 & (194.145) \\ 10 & 232 & 127 & (167.57) & 67 & 120 & (223.153) \\ 11 & 212 & 195 & (75.136) & 14 & 204 & (161.b2) \ math (167.57) \ 57,10)} & 213 & math (167.57) \ 57,10 și (161.b2) \ matemat )} \\\end{matrice}}$

Pasul 3 Detectarea coliziunilor

La : $i=12$ $[192]P+[24]Q=[213]P+[104]Q=(57,105)$
Înțelegem asta $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$

Literatură

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. O introducere elementară în criptografia eliptică: fundamente algebrice și algoritmice. - M .: KomKniga, 2006. - S. 328. - ISBN 5-484-00443-8 .

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. O introducere elementară în criptografia eliptică: protocoale de criptare cu curbă eliptică. - M .: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP RAPORT DE EVALUARE PENTRU CRYPTREC: NIVEL DE SECURITATE AL CRIPTOGRAFII - PROBLEMA MATEMATICĂ ECDLP.

Song Y. Yan Atacuri cuantice asupra criptosistemelor bazate pe ECDLP. - Springer US, 2013 - ISBN 978-1-4419-7721-2