Ecdlp

ECDLP (Elliptic Curve Discrete Logarithm Problem) is a discrete logarithm problem in a group of points of an elliptic curve .

Let an elliptic curve E, a finite field F _p and points P, Q ∈ E (F _p ) be given. The task of ECDLP is to find k if it exists such that Q = [k] P.

Definitions

An elliptic curve E over a finite field F _p is called a curve of the form (Weierstrass form):

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

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

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

, where a, b ∈ F _p .

The set of points on the elliptic curve in the field F _p , including the point "infinity" (denoted by Ο), forms a finite Abelian group and is denoted by E (F _p ) .

A point Q ∈E (F _p ) is called a return point to P ∈ E (F _p ) if P + Q = Ο and is denoted as Q = -P .

For a natural number n and P ∈ E (F _p ) we will assume:

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

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

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

The entries are [n] P and nP equivalents. The definition can be extended to any integer n if you use -P.

The order of a group of points is the number N equal to the cardinality of the set E (F _p ) and is denoted by | E (F _p ) | = N. Usually, elliptic cryptography takes curves such that N = h * l, where h = 1, 2 or 4, and l is a large prime number.

The order of a point P ∈ E (Fp) is the minimum number s such that [s] P = Ο. This forms a subgroup $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ ${\ displaystyle \ langle P \ rangle = \ {[k] P: k = {\ overline {1, s}} \}}$ $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ and point P is called a generator $\langle P\rangle$ ${\ displaystyle \ langle P \ rangle}$ $\langle P\rangle$ .

Decision Algorithms

Full search

It is the simplest attack in the implementation. It is only necessary to be able to do the operation R = [k] P.

Algorithm

$k:=1$ ${\ displaystyle k: = 1}$
$R:=[k]P$ ${\ displaystyle R: = [k] P}$
if $R=Q$ ${\ displaystyle R = Q}$ , then $k$ ${\ displaystyle k}$ - decision
else $k:=k+1$ ${\ displaystyle k: = k + 1}$ ; go to [2].

Algorithm complexity: Ο (N).

Polyg - Hellman Algorithm

Description

Let G be a subgroup of E (F _p ), $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ ${\ displaystyle N = | G | = \ prod _ {i = 1} ^ {t} {p_ {i}} ^ {e ^ {i}}}$ (i.e. it is assumed that the number N can be factorized) $P,Q\in G$ ${\ displaystyle P, Q \ in G}$ and $\exists k:Q=[k]P$ ${\ displaystyle \ exists k: Q = [k] P}$ .

We will solve the problem of finding k modulo ${p_{i}}^{e_{i}}$ ${\ displaystyle {p_ {i}} ^ {e_ {i}}}$ , then, using the Chinese remainder theorem , we find a solution k modulo N.

From group theory it is known that there is an isomorphism of groups:

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

{\ displaystyle \ phi: G \ rightarrow C _ {{p_ {1}} ^ {e_ {1}}} \ otimes ... \ otimes C _ {{p_ {t}} ^ {e_ {t}}}}

Where $C_{{p_{i}}^{e_{i}}}$ ${\ displaystyle C _ {{p_ {i}} ^ {e_ {i}}}}$ Is a cyclic subgroup G, $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$ ${\ displaystyle | C _ {{p_ {i}} ^ {e_ {i}}} | = {p_ {i}} ^ {e_ {i}}}$

Then projection $\phi$ ${\ displaystyle \ phi}$ on $C_{p^{e}}$ ${\ displaystyle C_ {p ^ {e}}}$ :

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

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

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

We show how to solve the problem in $C_{p^{e}}$ ${\ displaystyle C_ {p ^ {e}}}$ reducing it to an ECDLP solution in $C_{p}$ ${\ displaystyle C_ {p}}$ .

Let be $P,Q\in C_{p^{e}}$ ${\ displaystyle P, Q \ in C_ {p ^ {e}}}$ and $\exists k:Q=[k]P$ ${\ displaystyle \ exists k: Q = [k] P}$ .

Number $k$ ${\ displaystyle k}$ defined modulo $p^{e}$ ${\ displaystyle p ^ {e}}$ . Then we can write k in the following form:

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

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

Find the values $k_{0},k_{1},...$ ${\ displaystyle k_ {0}, k_ {1}, ...}$ by induction. Suppose known $k^{'}$ ${\ displaystyle k '}$ - value $k\ mod\ p^{t}$ ${\ displaystyle k \ mod \ p ^ {t}}$ , i.e

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

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

Now we want to define $k_{t}$ ${\ displaystyle k_ {t}}$ and thus calculate $k\ mod\ p^{t+1}$ ${\ displaystyle k \ mod \ p ^ {t + 1}}$ :

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

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

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

Let be $Q'=Q-[k']P$ ${\ displaystyle Q '= Q- [k'] P}$ and $P'=[p^{t}]P$ ${\ displaystyle P '= [p ^ {t}] P}$ then $Q'=[k'']P'$ ${\ displaystyle Q '= [k' '] P'}$

Now $P^{'}$ ${\ displaystyle P '}$ - element of order $p^{e-t}$ ${\ displaystyle p ^ {et}}$ to get an order element $p$ ${\ displaystyle p}$ and therefore reduce the problem to $C_{p}$ ${\ displaystyle C_ {p}}$ you must multiply the previous expression by $s=p^{e-t-1}$ ${\ displaystyle s = p ^ {et-1}}$ . T.O.

Q''=[s]Q'

{\ displaystyle Q '' = [s] Q '}

and

P''=[s]P'

{\ displaystyle P '' = [s] P '}

Got ECDLP in the box $C_{p}$ ${\ displaystyle C_ {p}}$ as $Q''=[k_{t}]P''$ ${\ displaystyle Q '' = [k_ {t}] P ''}$ .

Assuming that this problem can be solved in $C_{p}$ ${\ displaystyle C_ {p}}$ find a solution $k$ ${\ displaystyle k}$ at $C_{p^{e}}$ ${\ displaystyle C_ {p ^ {e}}}$ . Using the Chinese remainder theorem, we obtain an ECDLP solution in $E(F_{p})$ ${\ displaystyle E (F_ {p})}$ .

As mentioned above, in practice, elliptic curves are taken such that $N=hl$ ${\ displaystyle N = hl}$ where $l$ ${\ displaystyle l}$ - a very large prime number, which makes this method ineffective.

Example

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

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

$P=(1,237),Q=(190,271)$ ${\ displaystyle P = (1,237), Q = (190,271)}$

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

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

Step 1. Find $k\ mod\ 2$ ${\ displaystyle k \ mod \ 2}$

Find the projections of points on $C_{2}$ ${\ displaystyle C_ {2}}$ :

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

{\ displaystyle P_ {2} = 265P = (50.0)}

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

{\ displaystyle Q_ {2} = 265Q = (50.0)}

Decide $Q_{2}=[k]P_{2}$ ${\ displaystyle Q_ {2} = [k] P_ {2}}$

k\equiv 1\ (mod\ 2)

{\ displaystyle k \ equiv 1 \ (mod \ 2)}

Step 2. Find $k\ mod\ 5$ ${\ displaystyle k \ mod \ 5}$

Find the projections of points on $C_{5}$ ${\ displaystyle C_ {5}}$ :

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

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

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

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

Decide $Q_{5}=[k]P_{5}$ ${\ displaystyle Q_ {5} = [k] P_ {5}}$

notice, that

Q_{5}=-P_{5}

{\ displaystyle Q_ {5} = - P_ {5}} then

k\equiv 4\ (mod\ 5)

{\ displaystyle k \ equiv 4 \ (mod \ 5)}

Step 3. Find $k\ mod\ 53$ ${\ displaystyle k \ mod \ 53}$

Find the projections of points on $C_{53}$ ${\ displaystyle C_ {53}}$ :

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

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

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

{\ displaystyle Q_ {53} = 10Q = (592.97)}

Decide $Q_{53}=[k]P_{53}$ ${\ displaystyle Q_ {53} = [k] P_ {53}}$

k\equiv 48\ (mod\ 53)

{\ displaystyle k \ equiv 48 \ (mod \ 53)}

Step 4. Find $k\ mod\ 530$ ${\ displaystyle k \ mod \ 530}$

From the Chinese remainder theorem for the values obtained in the previous steps 1-3, we have that

k\equiv 419\ (mod\ 530)

{\ displaystyle k \ equiv 419 \ (mod \ 530)}

Shanks Algorithm (Baby-Step / Giant-Step method)

Description

Let be $G=\langle P\rangle$ ${\ displaystyle G = \ langle P \ rangle}$ - cyclic subgroup $E(F_{p});|\langle P\rangle |=l;Q\in G$ ${\ displaystyle E (F_ {p}); | \ langle P \ rangle | = l; Q \ in G}$ .

Imagine $k$ ${\ displaystyle k}$ as:

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

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

Because $k\leq l$ ${\ displaystyle k \ leq l}$ then $0\leq k_{0},k_{1}<\lceil {\sqrt {l}}\rceil$ ${\ displaystyle 0 \ leq k_ {0}, k_ {1} <\ lceil {\ sqrt {l}} \ rceil}$ .

We calculate the list of "small steps" $P_{i}=[i]P$ ${\ displaystyle P_ {i} = [i] P}$ , $0\leq i<\lceil {\sqrt {l}}\rceil$ ${\ displaystyle 0 \ leq i <\ lceil {\ sqrt {l}} \ rceil}$ and save the pairs $(P_{i},i)$ ${\ displaystyle (P_ {i}, i)}$ .

Computational complexity: $O(\lceil {\sqrt {l}}\rceil )$ ${\ displaystyle O (\ lceil {\ sqrt {l}} \ rceil)}$ .

Now we calculate the "big steps". Let be $P'=[\lceil {\sqrt {l}}\rceil ]P$ ${\ displaystyle P '= [\ lceil {\ sqrt {l}} \ rceil] P}$ we find $Q_{j}=Q-[j]P'$ {\ displaystyle Q_ {j} = Q- [j] P '} , $0\leq j<\lceil {\sqrt {l}}\rceil$ ${\ displaystyle 0 \ leq j <\ lceil {\ sqrt {l}} \ rceil}$ .

During search $Q_{j}$ ${\ displaystyle Q_ {j}}$ try to find find among saved pairs $(P_{i},i)$ ${\ displaystyle (P_ {i}, i)}$ such that $P_{i}=Q_{j}$ ${\ displaystyle P_ {i} = Q_ {j}}$ . If you managed to find such a pair, then $k_{0}=i,k_{1}=j$ ${\ displaystyle k_ {0} = i, k_ {1} = j}$ .

Or, the same thing:

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

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

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

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

.

The complexity of computing "big steps": $O(\lceil {\sqrt {l}}\rceil )$ ${\ displaystyle O (\ lceil {\ sqrt {l}} \ rceil)}$ .

In this case, the overall complexity of the method $O({\sqrt {l}})$ ${\ displaystyle O ({\ sqrt {l}})}$ but also required $S({\sqrt {l}})$ ${\ displaystyle S ({\ sqrt {l}})}$ memory for storage, which is a significant minus of the algorithm.

Algorithm

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

Pollard ρ-method

Description

Let be $G=\langle P\rangle$ ${\ displaystyle G = \ langle P \ rangle}$ - cyclic subgroup $E(F_{p});|G|=r;Q\in G$ ${\ displaystyle E (F_ {p}); | G | = r; Q \ in G}$ .

The main idea of the method is to find different pairs $(c',d')$ ${\ displaystyle (c ', d')}$ and $(c'',d'')$ {\ displaystyle (c``, d '')} modulo $r$ ${\ displaystyle r}$ such that $[c']P+[d']Q=[c'']P+[d'']Q$ ${\ displaystyle [c '] P + [d'] Q = [c ''] P + [d ''] Q}$ .

Then $[c'-c'']P=[d''-d']Q$ ${\ displaystyle [c'-c ''] P = [d '' - d '] Q}$ or $Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ ${\ displaystyle Q = {\ frac {c'-c ''} {d '' - d '}} P \ (mod \ r)}$ . Consequently, $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ ${\ displaystyle k \ equiv {\ frac {c'-c ''} {d '' - d '}} \ (mod \ r)}$ .

To implement this idea, we choose a random function for iterations $f:G\rightarrow G$ ${\ displaystyle f: G \ rightarrow G}$ , and a random point $P_{0}$ ${\ displaystyle P_ {0}}$ to start the crawl. The next point is calculated as $P_{i+1}=f(P_{i})$ ${\ displaystyle P_ {i + 1} = f (P_ {i})}$ .

Because $G$ ${\ displaystyle G}$ - finite, then there are such indices $i<j$ ${\ displaystyle i <j}$ , what $P_{i}=P_{j}$ ${\ displaystyle P_ {i} = P_ {j}}$ .

Then $P_{i+1}=f(P_{i})=f(P_{j})=P_{j+1}$ ${\ displaystyle P_ {i + 1} = f (P_ {i}) = f (P_ {j}) = P_ {j + 1}}$ .

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

Then the sequence $\{P_{i}\}$ ${\ displaystyle \ {P_ {i} \}}$ - periodic with a period $j-i$ ${\ displaystyle ji}$ (see pic).

Since f is a random function, according to the birthday paradox , coincidence will happen in about ${\sqrt {\frac {\pi r}{2}}}$ ${\ displaystyle {\ sqrt {\ frac {\ pi r} {2}}}}$ iterations. To speed up the search for collisions, the method invented by Floyd to search for the cycle length is used: a pair of values is calculated immediately $(P_{i},P_{2i})$ ${\ displaystyle (P_ {i}, P_ {2i})}$ for $i=1,2,...$ ${\ displaystyle i = 1,2, ...}$ until there is a match.

Algorithm

Initialization.
Choose the number of branches L (usually 16)
Select function $H:\langle P\rangle \rightarrow {1,2,...,L}$ ${\ displaystyle H: \ langle P \ rangle \ rightarrow {1,2, ..., L}}$
Calculation $[a_{i}]P+[b_{i}]Q$ ${\ displaystyle [a_ {i}] P + [b_ {i}] Q}$ .
$\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$ ${\ displaystyle \ mathbf {for} \ i: = 1 \ \ mathbf {to} \ L \ \ mathbf {do}}$
Take random $a_{i},b_{i}\in [0,r-1]$ ${\ displaystyle a_ {i}, b_ {i} \ in [0, r-1]}$
$R_{i}:=[a_{i}]P+[b_{i}]Q$ ${\ displaystyle R_ {i}: = [a_ {i}] P + [b_ {i}] Q}$
Calculation $[c']P+[d']Q$ ${\ displaystyle [c '] P + [d'] Q}$ .
Take random $c',d'\in [0,r-1]$ ${\ displaystyle c ', d' \ in [0, r-1]}$
$X':=[c']P+[d']Q$ ${\ displaystyle X ': = [c'] P + [d '] Q}$
Preparing for the cycle.
$X'':=X',c'':=c',d'':=d'$ ${\ displaystyle X '': = X ', c' ': = c', d '': = d '}$
Cycle.
$\mathbf {repeat}$ ${\ displaystyle \ mathbf {repeat}}$
$j:=H(X')$ ${\ displaystyle j: = H (X ')}$
$X':=X'+R_{j}$ ${\ displaystyle X ': = X' + R_ {j}}$
$c':=c'+a_{j}\ (mod\ r)$ ${\ displaystyle c ': = c' + a_ {j} \ (mod \ r)}$
$d':=d'+b_{j}\ (mod\ r)$ ${\ displaystyle d ': = d' + b_ {j} \ (mod \ r)}$
$\mathbf {for} \ i:=1\ \mathbf {to} \ 2\ \mathbf {do}$ ${\ displaystyle \ mathbf {for} \ i: = 1 \ \ mathbf {to} \ 2 \ \ mathbf {do}}$
$j:=H(X'')$ ${\ displaystyle j: = H (X '')}$
$X'':=X''+R_{j}$ ${\ displaystyle X '': = X '' + R_ {j}}$
$c'':=c''+a_{j}\ (mod\ r)$ ${\ displaystyle c '': = c '' + a_ {j} \ (mod \ r)}$
$d'':=d''+b_{j}\ (mod\ r)$ ${\ displaystyle d``: = d '' + b_ {j} \ (mod \ r)}$
$\mathbf {until} \ X'=X''$ ${\ displaystyle \ mathbf {until} \ X '= X' '}$
Output.
$\mathbf {if} d'\neq d''\ \mathbf {then}$ ${\ displaystyle \ mathbf {if} d '\ neq d' '\ \ mathbf {then}}$
$k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ ${\ displaystyle k \ equiv {\ frac {c'-c ''} {d '' - d '}} \ (mod \ r)}$
$\mathbf {else}$ ${\ displaystyle \ mathbf {else}}$ ERROR or run the algorithm again.

Algorithm Complexity: $O({\sqrt {r}})$ {\ displaystyle O ({\ sqrt {r}})} .

Example

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

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

$P=(5,116),Q=(155,166)$ ${\ displaystyle P = (5,116), Q = (155,166)}$

$|\langle P\rangle |=239$ ${\ displaystyle | \ langle P \ rangle | = 239}$

Step 1. Define the function.

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

Step 2. Iterations.

${\begin{array}{c|c c c|c c c}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,182)&180&105&(36,97)\\3&200&37&(27,17)&0&97&(108,89)\\4&180&105&(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)&14&207&(167,57)\\12&192&24&\mathbf {(57,105)} &213&104&\mathbf {(57,105)} \\\end{array}}$ ${\ displaystyle {\ 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,182) & 180 & 105 & (36,97) \\ 3 & 200 & 37 & (27,17) & 0 & 97 & (108,89) \ \ 4 & 180 & 105 & (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 ) & 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) & 14 & 207 & (167,57) \\ 12 & 192 & 24 & \ m 57,105)} & 213 & 104 & \ mathbf {(57,105)} \\\ end {array}}}$

Step 3. Collision Detection.

At $i=12$ ${\ displaystyle i = 12}$ : $[192]P+[24]Q=[213]P+[104]Q=(57,105)$ ${\ displaystyle [192] P + [24] Q = [213] P + [104] Q = (57,105)}$
We get that $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$ ${\ displaystyle k \ equiv {\ frac {192-213} {104-24}} \ equiv 176 \ (mod \ 229)}$

Literature

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Elementary introduction to elliptic cryptography: Algebraic and algorithmic foundations. - 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 elliptic cryptography: Protocols of cryptography on elliptic curves. - M.: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP EVALUATION REPORT FOR CRYPTREC: SECURITY LEVEL OF CRYPTOGRAPHY - ECDLP MATHEMATICAL PROBLEM.

Song Y. Yan Quantum Attacks on ECDLP-Based Cryptosystems. - Springer US, 2013 - ISBN 978-1-4419-7721-2

Ecdlp

Definitions

Decision Algorithms

Full search

Algorithm

Polyg - Hellman Algorithm

Description

Example

Shanks Algorithm (Baby-Step / Giant-Step method)

Description

Algorithm

Pollard ρ-method

Description

Algorithm

Example

Literature

More articles: