ECDLP

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. tammikuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 13 muokkausta .

ECDLP (Elliptic Curve Discrete Logathm Problem) on diskreetti logaritmiongelma elliptisen käyrän pisteryhmässä .

Olkoon elliptinen käyrä E, äärellinen kenttä F p ja pisteet P, Q ∈ E(F p ). ECDLP:n tehtävänä on löytää sellainen k, jos se on olemassa, että Q = [k]P.

Määritelmät

Elliptinen käyrä E äärellisen kentän F p päällä on muotoa (Weierstrassin muoto):

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

, missä a, b ∈ F p .

Pistejoukko elliptisellä käyrällä kentässä F p , mukaan lukien piste "ääretön" (merkitty Ο), muodostaa äärellisen Abelin ryhmän ja sitä merkitään E(F p ) .

Pistettä Q ∈E (F p ) kutsutaan käänteispisteeksi pisteelle P ∈ E(F p ), jos P + Q = Ο ja sitä merkitään Q = -P .

Luonnolliselle luvulle n ja P ∈ E(F p ) oletetaan:

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

Merkinnät [n]P ja nP ovat samanarvoisia. Määritelmä voidaan laajentaa mihin tahansa kokonaislukuun n käyttämällä -P:tä.

Pisteryhmän järjestys on luku N, joka on yhtä suuri kuin joukon E(F p ) kardinaliteetti, ja sitä merkitään |E(F p )| =N . Yleensä elliptisessä kryptografiassa käyrät otetaan siten, että N = h * l, missä h = 1, 2 tai 4, ja l on suuri alkuluku.

Pisteen P ∈ E(Fp) kertaluku on minimiluku s siten, että [s]P = Ο. Tässä tapauksessa muodostetaan aliryhmä ja pistettä P kutsutaan generaattoriksi . $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ $\langle P\rangle$

Ratkaisualgoritmit

Täysi luettelo

Se on yksinkertaisin toteuttaa hyökkäys. On tarpeen vain pystyä suorittamaan operaatio R = [k]P.

Algoritmi

$k:=1$
$R:=[k]P$
jos , niin - ratkaisu $R=Q$ $k$
muu ; mene kohtaan [2]. $k:=k+1$

Algoritmin monimutkaisuus: Ο(N).

Polig-Hellman-algoritmi

Kuvaus

Olkoon G aliryhmä E(F p ), (eli oletetaan, että luku N voidaan kertoa) ja . $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ $P,Q\in G$ $\exists k:Q=[k]P$

Ratkaisemme ongelman löytää k modulo , sitten kiinalaisen jäännöslauseen avulla löydämme ratkaisun k modulo N. ${p_{i}}^{e_{i}}$

Ryhmäteoriasta tiedetään, että on olemassa ryhmäisomorfismi:

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

missä on G:n syklinen alaryhmä, $C_{{p_{i}}^{e_{i}}}$ $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$

Sitten projektio : $\phi$ $C_{p^{e))$

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

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

Näytämme, kuinka ongelma ratkaistaan luvussa , pelkistämällä se ECDLP:n ratkaisemiseen kohdassa . $C_{p^{e))$ $C_p$

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

Numero on määritelty modulo . Sitten k voidaan kirjoittaa seuraavassa muodossa: $k$ ${\displaystyle p^{e))$

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

Etsitään arvot induktiolla. Oletetaan, että tiedämme - arvon , eli $k_{0},k_{1},...$ $k'$ ${\displaystyle k\ mod\ p^{t))$

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

Nyt haluamme määrittää ja siten laskea : $k_t$ $k\ mod\ p^{t+1}$

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

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

Anna ja sitten $Q'=Q-[k']P$ $P'=[p^{t}]P$ $Q'=[k'']P'$

Nyt - järjestyselementti , järjestyksen elementin saamiseksi ja siten ongelman vähentämiseksi on tarpeen kertoa edellinen lauseke luvulla . Että. $P'$ ${\displaystyle p^{et))$ $s$ $C_p$ ${\displaystyle s=p^{et-1))$

Q''=[s]Q'

P''=[s]P'

Vastaanotettu ECDLP kentällä nimellä . $C_p$ $Q''=[k_{t}]P''$

Olettaen, että tämä ongelma voidaan ratkaista kohdassa , löydämme ratkaisun kohdassa . Kiinan jäännöslauseen avulla saadaan ECDLP-ratkaisu . $C_p$ $k$ $C_{p^{e))$ $E(F_p)$

Kuten edellä mainittiin, käytännössä elliptiset käyrät otetaan siten, että , missä on erittäin suuri alkuluku, mikä tekee tästä menetelmästä tehottoman. $N=hl$ $l$

Esimerkki

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

Vaihe 1. Etsi $k\ mod\ 2$

Löydämme pisteiden projektiot : $C_{2}$

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

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

Me päätämme ${\displaystyle Q_{2}=[k]P_{2))$

k\equiv 1\ (mod\ 2)

Vaihe 2. Etsi $k\ mod\ 5$

Löydämme pisteiden projektiot : $C_{5}$

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

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

Me päätämme $Q_{5}=[k]P_{5}$

Huomaa se sitten

Q_{5}=-P_{5}

k\equiv 4\ (mod\ 5)

Vaihe 3. Etsi $k\ mod\ 53$

Löydämme pisteiden projektiot : $C_{53}$

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

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

Me päätämme $Q_{53}=[k]P_{53}$

k\equiv 48\ (mod\ 53)

Vaihe 4. Etsi $k\ mod\ 530$

Kiinalaisesta jäännöslauseesta edellisissä vaiheissa 1-3 saaduille arvoille saamme sen

k\equiv 419\ (mod\ 530)

Shanksin algoritmi (Baby-Step/Giant-Step-menetelmä)

Kuvaus

Antaa olla syklinen alaryhmä . $G=\langle P\rangle$ $E(F_{p});|\langle P\rangle |=l;Q\in G$

Laitetaan se muotoon: $k$

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

Siitä lähtien . $k\leq l$ $0\leq k_{0},k_{1}<\lceil {\sqrt {l))\rceil$

Laskemme luettelon "pienistä askeleista" ja tallennamme parit . $P_{i}=[i]P$ $0\leq i<\lceil {\sqrt {l))\rceil$ ${\näyttötyyli (P_{i},i)}$

Laskelmien monimutkaisuus: . $O(\lceil {\sqrt {l))\rceil )$

Nyt laskemme "isot askeleet". Etsitään . _ _ $P'=[\lceil {\sqrt {l}}\rceil ]P$ $Q_{j}=Q-[j]P'$ $0\leq j<\lceil {\sqrt {l))\rceil$

Haun aikana yritämme löytää tallennettujen parien joukosta sellaisia, että . Jos sellainen pari olisi mahdollista löytää, niin . $Q_{j}$ ${\näyttötyyli (P_{i},i)}$ ${\displaystyle P_{i}=Q_{j))$ $k_{0}=i,k_{1}=j$

Tai mikä on sama:

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

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

"Suurten vaiheiden" laskelmien monimutkaisuus: . $O(\lceil {\sqrt {l))\rceil )$

Tässä tapauksessa menetelmän yleinen monimutkaisuus , mutta vaatii myös muistia tallennusta varten, mikä on algoritmin merkittävä haitta. $O({\sqrt {l)))$ $S({\sqrt {l)))$

Algoritmi

$m:=\lceil {\sqrt {l))\rceil$
$\mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do}$ $R:=[i]P$ Tallentaa ${\näyttötyyli (R,i)}$
$\mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {do}$ $T:=Q-[j\lceil {\sqrt {l))\rceil ]P$ sisäänkirjautumislista [2] $T$
$\mathbf {if} \ T=R\ \mathbf {sitten}$ $k:=i+j\lceil {\sqrt {l))\rceil \ (mod\ l)$ $\mathbf {return} \k$

Pollardin ρ-menetelmä

Kuvaus

Antaa olla syklinen alaryhmä . $G=\langle P\rangle$ $E(F_{p});|G|=r;Q\in G$

Menetelmän pääideana on löytää erilliset parit ja modulo siten, että . ${\näyttötyyli (c',d')}$ ${\näyttötyyli (c'',d'')}$ $r$ $[c']P+[d']Q=[c'']P+[d'']Q$

Sitten tai . Siksi ,. $[c'-c'']P=[d''-d']Q$ $Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$

Tämän idean toteuttamiseksi valitsemme iteraatioille satunnaisfunktion ja satunnaisen pisteen läpikäynnin aloittamiseksi. Seuraava piste lasketaan . $f:G\rightarrow G$ $P_0$ $P_{i+1}=f(P_{i})$

Koska on rajallinen, on olemassa indeksejä niin, että . $G$ $i<j$ ${\displaystyle P_{i}=P_{j))$

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

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

Tällöin sekvenssi on jaksollinen jakson kanssa (katso kuva). $\{P_{i}\}$ $ji$

Koska f on satunnaisfunktio, syntymäpäiväparadoksin mukaan sattuma tapahtuu noin iteraatioiden jälkeen. Törmäysten etsinnän nopeuttamiseksi käytetään Floydin keksimää menetelmää syklin pituuden löytämiseksi: arvopari lasketaan kerralla, kunnes osuma löytyy. ${\displaystyle {\sqrt {\frac {\pi r}{2))))$ ${\näyttötyyli (P_{i}, P_{2i})}$ $i=1,2,...$

Algoritmi

Alustus. Valitse oksien lukumäärä L (yleensä 16 otetaan) Valitse toiminto $H:\langle P\rangle \rightarrow {1,2,...,L}$
Laskenta . $[a_{i}]P+[b_{i}]Q$ $\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$ Ota satunnainen $a_{i},b_{i}\in [0,r-1]$ $R_{i}:=[a_{i}]P+[b_{i}]Q$
Laskenta . $[c']P+[d']Q$ Ota satunnainen $c',d'\in [0,r-1]$ $X':=[c']P+[d']Q$
Valmistautuminen kiertoon. $X'':=X',c'':=c',d'':=d'$
Kierrä. $\mathbf {toista}$ ${\näyttötyyli 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}$ ${\näyttötyyli j:=H(X'')}$ ${\displaystyle X'':=X''+R_{j))$ $c'':=c''+a_{j}\ (mod\ r)$ $d'':=d''+b_{j}\ (mod\ r)$ $\mathbf {until} \ X'=X''$
Poistu. $\mathbf {if} d'\neq d''\ \mathbf {then}$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ $\mathbf {else}$ VIRHE tai suorita algoritmi uudelleen.

Algoritmin monimutkaisuus: . $O({\sqrt {r)))$

Esimerkki

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

Vaihe 1. Määritä toiminto.

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

Vaihe 2. Iteraatiot.

${\begin{array}{c|ccc|ccc}Iteraatio&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\ ? (36,97) & 46 & 40 & (223 153) \\ 5 & 20 & 29 & 29 & (119,180) & 232 & 127 & (167 57) \\ 6 & 0 & 97 & (108,89) & 192 & 24 & (57,105) \\ 79 & 79 & 21 & (81,168) ja (57,105) & (181 ja 0,13) ja (81 40) ja (87) ja (57) ja (57) ja (57) ja (57) ja (57) ja (57) ja (57). (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) \ Mathbf (167.57) \ 57,105). )} \\\end{array}}$

Vaihe 3 Törmäyksen havaitseminen

osoitteessa : $i=12$ $[192]P+[24]Q=[213]P+[104]Q=(57 105)$
Me ymmärrämme sen $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$

Kirjallisuus

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Perusjohdanto elliptiseen kryptografiaan: Algebralliset ja algoritmiset perusteet. - M .: KomKniga, 2006. - S. 328. - ISBN 5-484-00443-8 .

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Perusjohdanto elliptiseen kryptografiaan: Elliptisen käyrän salausprotokollat. - M .: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP CRYPTREC:N ARVIOINTIRAPORTTI: KRYPTOGRAFIAN TURVALLISUUSTASO - ECDLP:N MATEMAATTINEN ONGELMA.

Kappale Y. Yan Quantum Attacks on ECDLP-pohjainen kryptosysteemi. - Springer USA, 2013 - ISBN 978-1-4419-7721-2