ECDLP

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2015. január 26-án felülvizsgált verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

Az ECDLP (Elliptikus görbe diszkrét logaritmus probléma) egy diszkrét logaritmus feladat egy elliptikus görbe pontjainak csoportjában .

Legyen adott egy E elliptikus görbe, egy véges F p mező és a P, Q ∈ E(F p ) pontok. Az ECDLP feladata, hogy olyan k-t találjon, ha létezik, amely Q = [k]P.

Definíciók

Az E elliptikus görbe egy véges F p mező felett a következő alakú görbe (Weierstrass forma):

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

, ahol a, b ∈ F p .

Az F p mezőben lévő elliptikus görbén lévő pontok halmaza , beleértve a "végtelen" pontot (jelöljük Ο-ként), véges Abel-csoportot alkot, és E(F p ) -ként jelöljük .

Egy Q ∈E (F p ) pontot P ∈ E(F p ) inverz pontjának nevezzük , ha P + Q = Ο, és Q = -P -ként jelöljük .

Egy n természetes számra és P ∈ E(F p ) feltételezzük:

{\displaystyle [n]P=\zárójel {P+P+...+P} _{n))

Az [n]P és nP jelölések egyenértékűek. A definíció bármely n egész számra kiterjeszthető a -P használatával.

Egy pontcsoport sorrendje az N szám, amely megegyezik az E(F p ) halmaz számosságával, és |E(F p )| =N . Az elliptikus kriptográfiában általában úgy veszik fel a görbéket, hogy N = h * l, ahol h = 1, 2 vagy 4, és l egy nagy prímszám.

Egy P ∈ E(Fp) pont sorrendje az a minimális s szám, amelyre [s]P = Ο. Ebben az esetben egy alcsoport jön létre , és a P pontot generátornak nevezzük . $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ $\langle P\rangle$

Megoldási algoritmusok

Teljes felsorolás

Ez a legegyszerűbb végrehajtható támadás. Csak az R = [k]P művelet végrehajtására van szükség.

Algoritmus

$k:=1$
$R:=[k]P$
ha , akkor - megoldás $R=Q$ $k$
más ; lépjen a [2]-re. $k:=k+1$

Algoritmus bonyolultsága: Ο(N).

Polig-Hellman algoritmus

Leírás

Legyen G az E(F p ) részcsoportja, (vagyis feltételezzük, hogy az N szám faktorizálható), és . $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ $P,Q\in G$ $\exists k:Q=[k]P$

Megoldjuk a k modulo megtalálásának feladatát , majd a kínai maradéktétel segítségével megtaláljuk a k modulo N megoldást. ${p_{i}}^{e_{i}}$

A csoportelméletből ismert, hogy létezik csoportizomorfizmus:

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

ahol G ciklikus alcsoportja, $C_{{p_{i}}^{e_{i}}}$ $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$

Ezután a kivetítés erre : $\phi$ $C_{p^{e))$

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

Ezért ben . ${\phi _{p}}(Q)=[k]{\phi _{p}}(P)$ $C_{p^{e))$

Mutassuk meg, hogyan lehet megoldani a feladatot -ben, redukálva azt ECDLP megoldására -ben . $C_{p^{e))$ $C_p$

Hagyjuk és . $P,Q\in C_{p^{e}}$ $\exists k:Q=[k]P$

A szám modulo definiálva van . Ekkor k a következő formában írható fel: $k$ $p^{e}$

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

Keressük meg az értékeket indukcióval. Tegyük fel, hogy tudjuk - az értéket , azaz $k_{0},k_{1},...$ $k'$ ${\displaystyle k\ mod\ p^{t))$

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

Most meg akarjuk határozni és így kiszámítani : $k_t$ $k\ mod\ p^{t+1}$

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

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

Hadd és akkor $Q'=Q-[k']P$ $P'=[p^{t}]P$ $Q'=[k'']P'$

Most - a sorrend eleme, a sorrend elem megszerzéséhez, és ezért a probléma redukálásához meg kell szorozni az előző kifejezést -val . Hogy. $P'$ ${\displaystyle p^{et))$ $p$ $C_p$ ${\displaystyle s=p^{et-1))$

Q''=[s]Q'

és

P''=[s]P'

ECDLP-t kapott a terepen , mint . $C_p$ $Q''=[k_{t}]P''$

Feltételezve, hogy ez a probléma megoldható -ban , a megoldást -ben találjuk . A kínai maradéktételt felhasználva megkapjuk az ECDLP megoldást -ben . $C_p$ $k$ $C_{p^{e))$ $E(F_p)$

Ahogy fentebb említettük, a gyakorlatban az elliptikus görbéket úgy vesszük fel, hogy , ahol egy nagyon nagy prímszám, ami hatástalanná teszi ezt a módszert. $N=hl$ $l$

Példa

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

1. lépés: Keresse meg $k\ mod\ 2$

Megtaláljuk a pontok vetületeit : $C_{2}$

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

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

Mi döntünk ${\displaystyle Q_{2}=[k]P_{2))$

k\equiv 1\ (mod\ 2)

2. lépés: Keresse meg $k\ mod\ 5$

Megtaláljuk a pontok vetületeit : $C_{5}$

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

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

Mi döntünk $Q_{5}=[k]P_{5}$

Jegyezd meg akkor

Q_{5}=-P_{5}

k\equiv 4\ (mod\ 5)

3. lépés: Keresse meg $k\ mod\ 53$

Megtaláljuk a pontok vetületeit : $C_{53}$

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

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

Mi döntünk $Q_{53}=[k]P_{53}$

k\equiv 48\ (mod\ 53)

4. lépés: Keresse meg $k\ mod\ 530$

A kínai maradék tételből az előző 1-3. lépésben kapott értékekre azt kapjuk

k\equiv 419\ (mod\ 530)

Shanks algoritmusa (Baby-Step/Giant-Step módszer)

Leírás

Legyen egy ciklikus alcsoportja . $G=\langle P\rangle$ $E(F_{p});|\langle P\rangle |=l;Q\in G$

Tegyük formába: $k$

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

Azóta . _ $k\leq l$ $0\leq k_{0},k_{1}<\lceil {\sqrt {l))\rceil$

Kiszámoljuk a "kis lépések" listáját , és elmentjük a párokat . $P_{i}=[i]P$ $0\leq i<\lceil {\sqrt {l))\rceil$ ${\megjelenítési stílus (P_{i},i)}$

A számítások összetettsége: . $O(\lceil {\sqrt {l))\rceil )$

Most kiszámoljuk a "nagy lépéseket". Találjuk meg . _ $P'=[\lceil {\sqrt {l}}\rceil ]P$ $Q_{j}=Q-[j]P'$ $0\leq j<\lceil {\sqrt {l))\rceil$

A keresés során igyekszünk az elmentett párok között olyanokat találni, hogy . Ha sikerült találni egy ilyen párt, akkor . $Q_{j}$ ${\megjelenítési stílus (P_{i},i)}$ ${\displaystyle P_{i}=Q_{j))$ $k_{0}=i,k_{1}=j$

Vagy ami ugyanaz:

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

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

A „nagy lépések” számításának összetettsége: . $O(\lceil {\sqrt {l))\rceil )$

Ebben az esetben a módszer általános összetettsége , hanem memóriát is igényel a tároláshoz, ami az algoritmus jelentős hátránya. $O({\sqrt {l)))$ $S({\sqrt {l)))$

Algoritmus

$m:=\lceil {\sqrt {l))\rceil$
$\mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do}$ $R:=[i]P$ megment ${\megjelenítési stílus (R,i)}$
$\mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {do}$ $T:=Q-[j\lceil {\sqrt {l))\rceil ]P$ bejelentkezési lista [2] $T$
$\mathbf {if} \ T=R\ \mathbf {akkor}$ $k:=i+j\lceil {\sqrt {l))\rceil \ (mod\ l)$ $\mathbf {return} \k$

Pollard ρ-módszere

Leírás

Legyen egy ciklikus alcsoportja . $G=\langle P\rangle$ $E(F_{p});|G|=r;Q\in G$

A módszer fő ötlete az, hogy különálló párokat és modulokat találjunk úgy, hogy . $(c',d')$ ${\megjelenítési stílus (c'',d'')}$ $r$ $[c']P+[d']Q=[c'']P+[d'']Q$

Akkor vagy . Ezért ,. $[c'-c'']P=[d''-d']Q$ $Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$

Ennek az ötletnek a megvalósításához kiválasztunk egy véletlenszerű függvényt az iterációkhoz , és egy véletlen pontot a bejárás elindításához. A következő pontot a következőképpen számítjuk ki . $f:G\rightarrow G$ $P_0$ $P_{i+1}=f(P_{i})$

Mivel véges, vannak olyan indexek , hogy . $G$ $i<j$ ${\displaystyle P_{i}=P_{j))$

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

Valójában azért . ${\displaystyle P_{i+l}=P_{j+l))$ $\forall l\geq 0$

Ekkor a sorozat periodikus egy ponttal (lásd az ábrát). $\{P_{i}\}$ $ji$

Mivel f egy véletlen függvény, a születésnapi paradoxon szerint az egybeesés körülbelül iteráció után következik be. Az ütközések keresésének felgyorsítása érdekében a Floyd által feltalált módszert használják a ciklus hosszának meghatározására: egy értékpárt egyszerre számítanak ki, amíg egyezést nem találnak. ${\displaystyle {\sqrt {\frac {\pi r}{2))))$ $(P_{i},P_{2i})$ $i=1,2,...$

Algoritmus

Inicializálás. Válassza ki az ágak számát L (általában 16-ot vesznek fel) Funkció kiválasztása $H:\langle P\rangle \rightarrow {1,2,...,L}$
Számítás . $[a_{i}]P+[b_{i}]Q$ $\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$ Vegyél véletlenszerűen $a_{i},b_{i}\in [0,r-1]$ $R_{i}:=[a_{i}]P+[b_{i}]Q$
Számítás . $[c']P+[d']Q$ Vegyél véletlenszerűen $c',d'\in [0,r-1]$ $X':=[c']P+[d']Q$
Felkészülés a ciklusra. $X'':=X',c'':=c',d'':=d'$
Ciklus. $\mathbf {ismétlés}$ $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 {amig} \ X'=X''$
Kijárat. $\mathbf {if} d'\neq d''\ \mathbf {akkor}$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ $\mathbf {else}$ HIBA, vagy futtassa újra az algoritmust.

Az algoritmus összetettsége: . $O({\sqrt {r)))$

Példa

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

1. lépés: Határozza meg a függvényt.

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

2. lépés. Iterációk.

${\begin{array}{c|ccc|ccc}Iteráció&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\ ? (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,227)\\8&46&40&(223,153 )&193&0& (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) & 204 & (161.B2) \ 67.5. )} \\\end{tömb}}$

3. lépés Ütközésészlelés

itt : $i=12$ $[192]P+[24]Q=[213]P+[104]Q=(57,105)$
Ezt értjük $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$

Irodalom

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Elemi bevezetés az elliptikus kriptográfiába: Algebrai és algoritmikus alapok. - M .: KomKniga, 2006. - S. 328. - ISBN 5-484-00443-8 .

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Egy elemi bevezetés az elliptikus kriptográfiába: Elliptic curve cryptography protocols. - M .: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP A CRYPTREC ÉRTÉKELÉSI JELENTÉSE: A KRIPTOGRÁFIA BIZTONSÁGI SZINTJE – ECDLP MATEMATIKAI PROBLÉMA.

Y. Yan dal : kvantumtámadások ECDLP-alapú kriptorendszerek ellen. - Springer USA, 2013 - ISBN 978-1-4419-7721-2