ECDLP

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. januar 2015; checks kræver 13 redigeringer .

ECDLP (Elliptic Curve Discrete Logaritm Problem) er et diskret logaritmeproblem i en gruppe af punkter i en elliptisk kurve .

Lad en elliptisk kurve E, et endeligt felt F p og punkterne P, Q ∈ E(F p ) være givet. ECDLP's opgave er at finde sådan k, hvis den findes, at Q = [k]P.

Definitioner

En elliptisk kurve E over et begrænset felt F p er en kurve med formen (Weierstrass-form):

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

, hvor a, b ∈ F p .

Sættet af punkter på en elliptisk kurve i feltet F p , inklusive punktet "uendelighed" (betegnet som Ο), danner en endelig abelian gruppe og betegnes som E(F p ) .

Et punkt Q ∈E (F p ) kaldes et omvendt punkt til P ∈ E(F p ), hvis P + Q = Ο og betegnes som Q = -P .

For et naturligt tal n og P ∈ E(F p ) antager vi:

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

Notationerne [n]P og nP er ækvivalente. Definitionen kan udvides til et hvilket som helst heltal n ved at bruge -P.

Rækkefølgen af en gruppe af punkter er tallet N lig med kardinalitet af mængden E(F p ) og betegnes som |E(F p )| =N . Normalt i elliptisk kryptografi tages kurver således, at N = h * l, hvor h = 1, 2 eller 4, og l er et stort primtal.

Rækkefølgen af et punkt P ∈ E(Fp) er det minimale tal s, således at [s]P = Ο. I dette tilfælde dannes en undergruppe, og punktet P kaldes en generator . $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ $\langle P\rangle$

Løsningsalgoritmer

Fuld opregning

Det er det enkleste angreb at implementere. Det er kun nødvendigt at kunne udføre operationen R = [k]P.

Algoritme

$k:=1$
$R:=[k]P$
hvis , så - beslutning $R=Q$ $k$
andet ; gå til [2]. $k:=k+1$

Algoritmekompleksitet: Ο(N).

Polig-Hellman algoritme

Beskrivelse

Lad G være en undergruppe af E(F p ), (det vil sige, det antages, at tallet N kan faktoriseres), og . $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ $P,Q\in G$ $\exists k:Q=[k]P$

Vi vil løse problemet med at finde k modulo , så vil vi ved hjælp af den kinesiske restsætning finde løsningen k modulo N. ${p_{i}}^{e_{i}}$

Det er kendt fra gruppeteorien, at der er en gruppeisomorfi:

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

hvor er en cyklisk undergruppe af G, $C_{{p_{i}}^{e_{i}}}$ $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$

Derefter projektionen på : $\phi$ $C_{p^{e))$

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

Derfor, i . ${\phi _{p}}(Q)=[k]{\phi _{p}}(P)$ $C_{p^{e))$

Lad os vise, hvordan man løser problemet i , reducere det til at løse ECDLP i . $C_{p^{e))$ $C_p$

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

Tallet er defineret modulo . Så kan k skrives på følgende måde: $k$ ${\displaystyle p^{e))$

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

Lad os finde værdierne ved induktion. Antag, at vi kender - værdien , det vil sige $k_{0},k_{1},...$ $k'$ ${\displaystyle k\ mod\ p^{t))$

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

Nu vil vi bestemme og dermed beregne : $k_t$ $k\ mod\ p^{t+1}$

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

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

Lad og så $Q'=Q-[k']P$ $P'=[p^{t}]P$ $Q'=[k'']P'$

Nu - ordenselementet , for at opnå ordenselementet og derfor for at reducere problemet til det er det nødvendigt at gange det foregående udtryk med . At. $P'$ ${\displaystyle p^{et))$ $s$ $C_p$ ${\displaystyle s=p^{et-1))$

Q''=[s]Q'

P''=[s]P'

Modtog ECDLP i feltet som . $C_p$ $Q''=[k_{t}]P''$

Forudsat at dette problem kan løses i , finder vi løsningen i . Ved at bruge den kinesiske restsætning får vi ECDLP-løsningen i . $C_p$ $k$ $C_{p^{e))$ $E(F_p)$

Som nævnt ovenfor tages elliptiske kurver i praksis sådan, at , hvor er et meget stort primtal, hvilket gør denne metode ineffektiv. $N=hl$ $l$

Eksempel

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

Trin 1. Find $k\ mod\ 2$

Vi finder fremskrivningerne af punkter på : $C_{2}$

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

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

Vi bestemmer ${\displaystyle Q_{2}=[k]P_{2))$

k\equiv 1\ (mod\ 2)

Trin 2. Find $k\ mod\ 5$

Vi finder fremskrivningerne af punkter på : $C_{5}$

P_{5}=106P=(639.160)

Q_{5}=106Q=(639.849)

Vi bestemmer $Q_{5}=[k]P_{5}$

Bemærk det da

Q_{5}=-P_{5}

k\equiv 4\ (mod\ 5)

Trin 3. Find $k\ mod\ 53$

Vi finder fremskrivningerne af punkter på : $C_{53}$

P_{53}=10P=(32.737)

Q_{53}=10Q=(592.97)

Vi bestemmer $Q_{53}=[k]P_{53}$

k\equiv 48\ (mod\ 53)

Trin 4. Find $k\ mod\ 530$

Fra den kinesiske restsætning for værdierne opnået i de foregående trin 1-3, har vi det

k\equiv 419\ (mod\ 530)

Shanks' algoritme (Baby-Step/Giant-Step-metoden)

Beskrivelse

Lade være en cyklisk undergruppe af . $G=\langle P\rangle$ $E(F_{p});|\langle P\rangle |=l;Q\in G$

Lad os sætte det i formen: $k$

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

Siden da . $k\leq l$ $0\leq k_{0},k_{1}<\lceil {\sqrt {l))\rceil$

Vi beregner listen over "små skridt" og gemmer parrene . $P_{i}=[i]P$ $0\leq i<\lceil {\sqrt {l))\rceil$ $(P_{i},i)$

Beregningernes kompleksitet: . $O(\lceil {\sqrt {l))\rceil )$

Nu beregner vi de "store skridt". Lad os finde . $P'=[\lceil {\sqrt {l}}\rceil ]P$ $Q_{j}=Q-[j]P'$ $0\leq j<\lceil {\sqrt {l))\rceil$

Under søgningen forsøger vi at finde blandt de gemte par sådan, at . Hvis det var muligt at finde sådan et par, så . $Q_{j}$ $(P_{i},i)$ ${\displaystyle P_{i}=Q_{j))$ $k_{0}=i,k_{1}=j$

Eller, som er det samme:

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

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

Kompleksiteten af beregninger af "store trin": . $O(\lceil {\sqrt {l))\rceil )$

I dette tilfælde er den overordnede kompleksitet af metoden , men kræver også hukommelse til lagring, hvilket er en væsentlig ulempe ved algoritmen. $O({\sqrt {l)))$ $S({\sqrt {l)))$

Algoritme

$m:=\lceil {\sqrt {l))\rceil$
$\mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do}$ $R:=[i]P$ Gemme $(R,i)$
$\mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {do}$ $T:=Q-[j\lceil {\sqrt {l))\rceil ]P$ check- in liste [2] $T$
$\mathbf {if} \ T=R\ \mathbf {then}$ $k:=i+j\lceil {\sqrt {l))\rceil \ (mod\ l)$ $\mathbf {retur} \k$

Pollards ρ-metode

Beskrivelse

Lade være en cyklisk undergruppe af . $G=\langle P\rangle$ $E(F_{p});|G|=r;Q\in G$

Hovedideen med metoden er at finde forskellige par og modulo sådan, at . $(c',d')$ $(c'',d'')$ $r$ $[c']P+[d']Q=[c'']P+[d'']Q$

Så eller . Derfor ,. $[c'-c'']P=[d''-d']Q$ $Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$

For at implementere denne idé vælger vi en tilfældig funktion for iterationer og et tilfældigt punkt for at starte gennemgangen. Det næste punkt beregnes som . $f:G\rightarrow G$ $P_0$ $P_{i+1}=f(P_{i})$

Da er endeligt, er der indekser sådan, at . $G$ $i<j$ ${\displaystyle P_{i}=P_{j))$

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

Faktisk for . ${\displaystyle P_{i+l}=P_{j+l))$ $\forall l\geq 0$

Derefter er rækkefølgen periodisk med en periode (se figur). $\{P_{i}\}$ $ji$

Da f er en tilfældig funktion, vil sammenfaldet ifølge fødselsdagsparadokset ske efter ca. iterationer. For at fremskynde søgningen efter kollisioner bruges en metode opfundet af Floyd til at finde cykluslængden: et par værdier beregnes på én gang, indtil en match er fundet. ${\displaystyle {\sqrt {\frac {\pi r}{2))))$ $(P_{i},P_{2i})$ $i=1,2,...$

Algoritme

Initialisering. Vælg antallet af grene L (normalt tages 16) Vælg funktion $H:\langle P\rangle \rightarrow {1,2,...,L}$
Beregning . $[a_{i}]P+[b_{i}]Q$ $\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$ Tag tilfældigt $a_{i},b_{i}\in [0,r-1]$ $R_{i}:=[a_{i}]P+[b_{i}]Q$
Beregning . $[c']P+[d']Q$ Tag tilfældigt $c',d'\in [0,r-1]$ $X':=[c']P+[d']Q$
Forberedelse til en cyklus. $X'':=X',c'':=c',d'':=d'$
Cyklus. $\mathbf {gentag}$ $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 {do}$ $j:=H(X'')$ ${\displaystyle X'':=X''+R_{j))$ $c'':=c''+a_{j}\ (mod\ r)$ $d'':=d''+b_{j}\ (mod\ r)$ $\mathbf {indtil} \ X'=X''$
Afslut. $\mathbf {if} d'\neq d''\ \mathbf {then}$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ $\mathbf {else}$ FEJL eller kør algoritmen igen.

Algoritmens kompleksitet: . $O({\sqrt {r)))$

Eksempel

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

Trin 1. Definer funktionen.

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

Trin 2. Gentagelser.

${\begin{array}{c|ccc|ccc}Iteration&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)\\2&113&167&(130,181)&52)\7(03)&52)\7(03)&52)\7(03)&52) (36,97) & 46 & 40 & (223,153) \\ 5 & 20 & 29 & (119,180) & 232 & 127 & (167,57) \\ 6 & 0 & 97 & (108,89) & 192 & 24 & (57,105) \ \ 79 & 21 & (81,168) & 139 & 111 (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) & 144 )} \\\end{array}}$

Trin 3 Kollisionsdetektion

kl .: $i=12$ $[192]P+[24]Q=[213]P+[104]Q=(57.105)$
Det forstår vi $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$

Litteratur

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. En elementær introduktion til elliptisk kryptografi: algebraiske og algoritmiske grundlag. - M .: KomKniga, 2006. - S. 328. - ISBN 5-484-00443-8 .

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. En elementær introduktion til elliptisk kryptografi: elliptisk kurvekryptografiprotokoller. - M .: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP EVALUERINGSRAPPORT FOR CRYPTREC: SIKKERHEDSNIVEAU FOR KRYPTOGRAFI - ECDLP MATEMATISK PROBLEM.

Sangen Y. Yan Kvanteangreb på ECDLP-baserede kryptosystemer. - Springer USA, 2013 - ISBN 978-1-4419-7721-2