ECDLP

ECDLP (Elliptic Curve Discrete Logarithm Problem) — задача дискретного логарифмирования в группе точек эллиптической кривой.

Пусть даны эллиптическая кривая E, конечно поле F_p и точки P, Q ∈ E(F_p). Задача ECDLP: найти такое k, если оно существует, что Q = [k]P.

ОпределенияПравить

Эллиптической кривой E над конечным полем F_p называется кривая вида (форма Вейерштрасса):

$E:Y^2=X^3+aX+b$$E:Y^{2}=X^{3}+aX+b$ , где a, b ∈ F_p.

Набор точек на эллиптической кривой в поле F_p, включающий точку «бесконечность» (обозначается как Ο), образует конечную абелеву группу и обозначается как E(F_p).

Точка Q ∈E (F_p) называется обратной точкой к P ∈ E(F_p), если P + Q = Ο и обозначается как Q = -P.

Для натурального числа n и P ∈ E(F_p) будем считать:

$[n]P=\underset{n}{\underset{⏟<!--\; ⏟\; -->}{P+P+...+P}}$$[n]P=\underbrace {P+P+...+P} _{n}$ 

Записи [n]P и nP эквиваленты. Определение можно расширить для любого целого числа n, если использовать -P.

Порядком группы точек называется число N равное мощности множества E(F_p) и обозначается как |E(F_p)| = N. Обычно в эллиптической криптографии берутся кривые такие, что N = h * l, где h = 1, 2 или 4, а l — большое простое число.

Порядком точки P ∈ E(Fp) называется минимальное число s такое, что [s]P = Ο. При этом образуется подгруппа $⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->=\{[k]P:k=\stackrel{¯<!--\; ¯\; -->}{1,s}\}$$\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$  и точка P называется генератором $⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->$$\langle P\rangle$ .

Алгоритмы решенияПравить

Полный переборПравить

Является самой просто атакой в реализации. Необходимо только уметь делать операцию R = [k]P.

АлгоритмПравить

1. $k:=1$$k:=1$ 
2. $R:=[k]P$$R:=[k]P$ 
3. if $R=Q$$R=Q$ , then $k$$k$  — решение
4. else $k:=k+1$$k:=k+1$ ; перейти к [2].

Сложность алгоритма: Ο(N).

Алгоритм Полига — ХеллманаПравить

ОписаниеПравить

Пусть G — подгруппа E(F_p), $N=|G|=\underset{i=1}{\overset{t}{\prod <!--\; \prod \; -->}}{p_i}^{e^i}$$N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$  (то есть предполагается, что число N может быть факторизовано), $P,Q\in <!--\; \in \; -->G$$P,Q\in G$  и $\mathrm{\exists <!--\; \exists \; -->}k:Q=[k]P$$\exists k:Q=[k]P$ .

Будем решать задачу о поиске k по модулю ${p_i}^{e_i}$${p_{i}}^{e_{i}}$ , затем, используя китайскую теорему об остатках, найдем решение k по модулю N.

Из теории групп известно, что существует изоморфизм групп:

$\mathrm{\varphi <!--\; \varphi \; -->}:G\to <!--\; \to \; -->C_{{p_1}^{e_1}}\otimes <!--\; \otimes \; -->...\otimes <!--\; \otimes \; -->C_{{p_t}^{e_t}}$$\phi :G\rightarrow C_{{p_{1}}^{e_{1}}}\otimes ...\otimes C_{{p_{t}}^{e_{t}}}$ 

где $C_{{p_i}^{e_i}}$$C_{{p_{i}}^{e_{i}}}$  — циклическая подгруппа G, $|C_{{p_i}^{e_i}}|={p_i}^{e_i}$$|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$ 

Тогда проекция $\mathrm{\varphi <!--\; \varphi \; -->}$$\phi$  на $C_{p^e}$$C_{p^{e}}$ :

${\mathrm{\varphi <!--\; \varphi \; -->}}_p=\{\begin{array}{l}G\to <!--\; \to \; -->C_{p^e}\\ R⟼<!--\; ⟼\; -->[\frac{N}{p^e}]R\end{array}$$\phi _{p}={\begin{cases}G\rightarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\end{cases}}$ 

Следовательно, ${\mathrm{\varphi <!--\; \varphi \; -->}}_p(Q)=[k]{\mathrm{\varphi <!--\; \varphi \; -->}}_p(P)$${\phi _{p}}(Q)=[k]{\phi _{p}}(P)$  в $C_{p^e}$$C_{p^{e}}$ .

Покажем, как решить задачу в $C_{p^e}$$C_{p^{e}}$ , сведя её к решению ECDLP в $C_p$$C_p$ .

Пусть $P,Q\in <!--\; \in \; -->C_{p^e}$$P,Q\in C_{p^{e}}$  и $\mathrm{\exists <!--\; \exists \; -->}k:Q=[k]P$$\exists k:Q=[k]P$ .

Число $k$$k$  определено по модулю $p^e$$p^{e}$ . Тогда можно записать k в следующем виде:

$k=k_0+k_{1}p+...+k_{e-<!--\; -\; -->1}{p}^{e-<!--\; -\; -->1}$$k=k_{0}+{k_{1}}p+...+{k_{e-1}}p^{e-1}$ 

Найдем значения $k_0,k_1,...$$k_{0},k_{1},...$  по индукции. Предположим, известно $k^{\prime }$$k'$  — значение $kmod{p}^t$$k\ mod\ p^{t}$ , то есть

$k^{\prime }=k_0+...+k_{t-<!--\; -\; -->1}{p}^{t-<!--\; -\; -->1}$$k'=k_{0}+...+k_{t-1}p^{t-1}$ 

Теперь хотим определить $k_t$$k_t$  и таким образом вычислить $kmod{p}^{t+1}$$k\ mod\ p^{t+1}$ :

$k=k^{\prime }+p^t{k}^{″}$$k=k'+p^{t}k''$ 

Тогда $Q=[k^{\prime }]P+[k^{″}]([p^t]P)$$Q=[k']P+[k'']([p^{t}]P)$ .

Пусть $Q^{\prime }=Q-<!--\; -\; -->[k^{\prime }]P$$Q'=Q-[k']P$  и $P^{\prime }=[p^t]P$$P'=[p^{t}]P$ , тогда $Q^{\prime }=[k^{″}]P^{\prime }$$Q'=[k'']P'$ 

Теперь $P^{\prime }$$P'$  — элемент порядка $p^{e-<!--\; -\; -->t}$$p^{e-t}$ , чтобы получить элемент порядка $p$$p$  и, следовательно, свести задачу в $C_p$$C_p$  необходимо умножить предыдущее выражение на $s=p^{e-<!--\; -\; -->t-<!--\; -\; -->1}$$s=p^{e-t-1}$ . Т.о.

$Q^{″}=[s]Q^{\prime }$$Q''=[s]Q'$  и $P^{″}=[s]P^{\prime }$$P''=[s]P'$ 

Получили ECDLP в поле $C_p$$C_p$  в виде $Q^{″}=[k_t]P^{″}$$Q''=[k_{t}]P''$ .

Предполагая, что можно решить эту задачу в $C_p$$C_p$ , находим решение $k$$k$  в $C_{p^e}$$C_{p^{e}}$ . Используя китайскую теорему об остатках, получаем решение ECDLP в $E(F_p)$$E(F_p)$ .

Как говорилось выше, на практике берутся эллиптические кривые такие, что $N=hl$$N=hl$ , где $l$$l$  — очень большое простое число, что делает данный метод малоэффективным.

ПримерПравить

$Q=[k]P(mod1009)$$Q=[k]P\ (mod\ 1009)$ 

$E:y^2\equiv <!--\; \equiv \; -->x^3+71x+602(mod1009)$$E:y^{2}\equiv x^{3}+71x+602\ (mod\ 1009)$ 

$P=(1,237),Q=(190,271)$$P=(1,237),Q=(190,271)$ 

$N=1060=2^2\ast <!--\; \ast \; -->5\ast <!--\; \ast \; -->53$$N=1060=2^{2}*5*53$ 

$|⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->|=530=2\ast <!--\; \ast \; -->5\ast <!--\; \ast \; -->53$$|\langle P\rangle |=530=2*5*53$ 

Шаг 1. Найти $kmod2$$k\ mod\ 2$ 

• Находим проекции точек на $C_2$$C_{2}$ :

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

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

• Решаем $Q_2=[k]P_2$$Q_{2}=[k]P_{2}$ 

$k\equiv <!--\; \equiv \; -->1(mod2)$$k\equiv 1\ (mod\ 2)$ 

Шаг 2. Найти $kmod5$$k\ mod\ 5$ 

• Находим проекции точек на $C_5$$C_{5}$ :

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

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

• Решаем $Q_5=[k]P_5$$Q_{5}=[k]P_{5}$ 

Заметим, что $Q_5=-<!--\; -\; -->P_5$$Q_{5}=-P_{5}$ , тогда $k\equiv <!--\; \equiv \; -->4(mod5)$$k\equiv 4\ (mod\ 5)$ 

Шаг 3. Найти $kmod53$$k\ mod\ 53$ 

• Находим проекции точек на $C_{53}$$C_{53}$ :

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

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

• Решаем $Q_{53}=[k]P_{53}$$Q_{53}=[k]P_{53}$ 

$k\equiv <!--\; \equiv \; -->48(mod53)$$k\equiv 48\ (mod\ 53)$ 

Шаг 4. Найти $kmod530$$k\ mod\ 530$ 

• Из китайской теоремы об остатках для значений, полученных на предыдущих шагах 1-3, имеем, что

$k\equiv <!--\; \equiv \; -->419(mod530)$$k\equiv 419\ (mod\ 530)$ 

Алгоритм Шенкса (Baby-Step/Giant-Step method)Править

ОписаниеПравить

Пусть $G=⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->$$G=\langle P\rangle$  — циклическая подгруппа $E(F_p);|⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->|=l;Q\in <!--\; \in \; -->G$$E(F_{p});|\langle P\rangle |=l;Q\in G$ .

Представим $k$$k$  в виде:

$k=k_0+k_1\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->$$k=k_{0}+k_{1}\lceil {\sqrt {l}}\rceil$ 

Так как $k\le <!--\; \le \; -->l$$k\leq l$ , то $0\leq k_{0},k_{1}<\lceil {\sqrt {l}}\rceil$ .

Вычисляем список «маленьких шагов» $P_i=[i]P$$P_{i}=[i]P$ , $0\leq i<\lceil {\sqrt {l}}\rceil$  и сохраняем пары $(P_i,i)$$(P_{i},i)$ .

Сложность вычислений: $O(\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->)$$O(\lceil {\sqrt {l}}\rceil )$ .

Теперь вычисляем «большие шаги». Пусть $P^{\prime }=[\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->]P$$P'=[\lceil {\sqrt {l}}\rceil ]P$ , найдём $Q_j=Q-<!--\; -\; -->[j]P^{\prime }$$Q_{j}=Q-[j]P'$ , $0\leq j<\lceil {\sqrt {l}}\rceil$ .

Во время поиска $Q_j$$Q_{j}$  пробуем найти среди сохранённых пар $(P_i,i)$$(P_{i},i)$  такую, что $P_i=Q_j$$P_{i}=Q_{j}$ . Если удалось найти такую пару, то $k_0=i,k_1=j$$k_{0}=i,k_{1}=j$ .

Или, что то же самое:

$[i]P=Q-<!--\; -\; -->[j\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->]P,$$[i]P=Q-[j\lceil {\sqrt {l}}\rceil ]P,$ 

$[i+j\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->]P=Q$$[i+j\lceil {\sqrt {l}}\rceil ]P=Q$ .

Сложность вычислений «больших шагов»:$O(\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->)$$O(\lceil {\sqrt {l}}\rceil )$ .

В таком случае общая сложность метода $O(\sqrt{l})$$O({\sqrt {l}})$ , но также требуется $S(\sqrt{l})$$S({\sqrt {l}})$  памяти для хранения, что является существенным минусом алгоритма.

АлгоритмПравить

1. $m:=\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->$$m:=\lceil {\sqrt {l}}\rceil$ 
2. $\mathbf{f}\mathbf{o}\mathbf{r}i:=1\mathbf{t}\mathbf{o}m\mathbf{d}\mathbf{o}$$\mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do}$ 

   $R:=[i]P$$R:=[i]P$ 

   сохранить $(R,i)$$(R,i)$ 

3. $\mathbf{f}\mathbf{o}\mathbf{r}j:=1\mathbf{t}\mathbf{o}m\mathbf{d}\mathbf{o}$$\mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {do}$ 

   $T:=Q-<!--\; -\; -->[j\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->]P$$T:=Q-[j\lceil {\sqrt {l}}\rceil ]P$ 

   проверить $T$$T$  в списке [2]

4. $\mathbf{i}\mathbf{f}T=R\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}$$\mathbf {if} \ T=R\ \mathbf {then}$ 

   $k:=i+j\lceil <!--\; \lceil \; -->\sqrt{l}\rceil <!--\; \rceil \; -->(modl)$$k:=i+j\lceil {\sqrt {l}}\rceil \ (mod\ l)$ 

   $\mathbf{r}\mathbf{e}\mathbf{t}\mathbf{u}\mathbf{r}\mathbf{n}k$$\mathbf {return} \ k$ 

ρ-метод ПоллардаПравить

ОписаниеПравить

Пусть $G=⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->$$G=\langle P\rangle$  — циклическая подгруппа $E(F_p);|G|=r;Q\in <!--\; \in \; -->G$$E(F_{p});|G|=r;Q\in G$ .

Основная идея метода — найти различные пары $(c^{\prime },d^{\prime })$$(c',d')$  и $(c^{″},d^{″})$$(c'',d'')$  по модулю $r$$r$  такие, что $[c^{\prime }]P+[d^{\prime }]Q=[c^{″}]P+[d^{″}]Q$$[c']P+[d']Q=[c'']P+[d'']Q$ .

Тогда $[c^{\prime }-<!--\; -\; -->c^{″}]P=[d^{″}-<!--\; -\; -->d^{\prime }]Q$$[c'-c'']P=[d''-d']Q$  или $Q=\frac{c^{\prime }-<!--\; -\; -->c^{″}}{d^{″}-<!--\; -\; -->d^{\prime }}P(modr)$$Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ . Следовательно, $k\equiv <!--\; \equiv \; -->\frac{c^{\prime }-<!--\; -\; -->c^{″}}{d^{″}-<!--\; -\; -->d^{\prime }}(modr)$$k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ .

Чтобы реализовать эту идею, выберем случайную функцию для итераций $f:G\to <!--\; \to \; -->G$$f:G\rightarrow G$ , и случайную точку $P_0$$P_0$  для начала обхода. Следующая точка вычисляется как $P_{i+1}=f(P_i)$$P_{i+1}=f(P_{i})$ .

Так как $G$$G$  — конечная, то найдутся такие индексы $i<j$ , что $P_i=P_j$$P_{i}=P_{j}$ .

Тогда $P_{i+1}=f(P_i)=f(P_j)=P_{j+1}$$P_{i+1}=f(P_{i})=f(P_{j})=P_{j+1}$ .

На самом деле $P_{i+l}=P_{j+l}$$P_{i+l}=P_{j+l}$ , для $\mathrm{\forall <!--\; \forall \; -->}l\ge <!--\; \ge \; -->0$$\forall l\geq 0$ .

Тогда последовательность $\{P_i\}$$\{P_{i}\}$  — периодична с периодом $j-<!--\; -\; -->i$$j-i$  (см. рис).

Так как f случайная функция, то, согласно парадоксу дней рождения, совпадение случится примерно через $\sqrt{\frac{\mathrm{\pi <!--\; \pi \; -->}r}{2}}$${\sqrt {\frac {\pi r}{2}}}$  итераций. Для ускорения поиска коллизий используется метод, придуманный Флойдом для поиска длины цикла: вычисляется сразу пара значений $(P_i,P_{2i})$$(P_{i},P_{2i})$  для $i=1,2,...$$i=1,2,...$ , пока не найдется совпадение.

АлгоритмПравить

1. Инициализация.

   Выбрать число ветвей L (обычно берётся 16)

   Выбрать функцию $H:⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->\to <!--\; \to \; -->1,2,...,L$$H:\langle P\rangle \rightarrow {1,2,...,L}$ 

2. Вычисление $[a_i]P+[b_i]Q$$[a_{i}]P+[b_{i}]Q$ .

   $\mathbf{f}\mathbf{o}\mathbf{r}i:=1\mathbf{t}\mathbf{o}L\mathbf{d}\mathbf{o}$$\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$ 

   Взять случайные $a_i,b_i\in <!--\; \in \; -->[0,r-<!--\; -\; -->1]$$a_{i},b_{i}\in [0,r-1]$ 

   $R_i:=[a_i]P+[b_i]Q$$R_{i}:=[a_{i}]P+[b_{i}]Q$ 

3. Вычисление $[c^{\prime }]P+[d^{\prime }]Q$$[c']P+[d']Q$ .

   Взять случайные $c^{\prime },d^{\prime }\in <!--\; \in \; -->[0,r-<!--\; -\; -->1]$$c',d'\in [0,r-1]$ 

   $X^{\prime }:=[c^{\prime }]P+[d^{\prime }]Q$$X':=[c']P+[d']Q$ 

4. Подготовка к циклу.

   $X^{″}:=X^{\prime },c^{″}:=c^{\prime },d^{″}:=d^{\prime }$$X'':=X',c'':=c',d'':=d'$ 

5. Цикл.

   $\mathbf{r}\mathbf{e}\mathbf{p}\mathbf{e}\mathbf{a}\mathbf{t}$$\mathbf {repeat}$ 

   $j:=H(X^{\prime })$$j:=H(X')$ 

   $X^{\prime }:=X^{\prime }+R_j$$X':=X'+R_{j}$ 

   $c^{\prime }:=c^{\prime }+a_j(modr)$$c':=c'+a_{j}\ (mod\ r)$ 

   $d^{\prime }:=d^{\prime }+b_j(modr)$$d':=d'+b_{j}\ (mod\ r)$ 

   $\mathbf{f}\mathbf{o}\mathbf{r}i:=1\mathbf{t}\mathbf{o}2\mathbf{d}\mathbf{o}$$\mathbf {for} \ i:=1\ \mathbf {to} \ 2\ \mathbf {do}$ 

   $j:=H(X^{″})$$j:=H(X'')$ 

   $X^{″}:=X^{″}+R_j$$X'':=X''+R_{j}$ 

   $c^{″}:=c^{″}+a_j(modr)$$c'':=c''+a_{j}\ (mod\ r)$ 

   $d^{″}:=d^{″}+b_j(modr)$$d'':=d''+b_{j}\ (mod\ r)$ 

   $\mathbf{u}\mathbf{n}\mathbf{t}\mathbf{i}\mathbf{l}{X}^{\prime }=X^{″}$$\mathbf {until} \ X'=X''$ 

6. Выход.

   $\mathbf{i}\mathbf{f}{d}^{\prime }\ne <!--\; \ne \; -->d^{″}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}$$\mathbf {if} d'\neq d''\ \mathbf {then}$ 

   $k\equiv <!--\; \equiv \; -->\frac{c^{\prime }-<!--\; -\; -->c^{″}}{d^{″}-<!--\; -\; -->d^{\prime }}(modr)$$k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ 

   $\mathbf{e}\mathbf{l}\mathbf{s}\mathbf{e}$$\mathbf {else}$  ОШИБКА или запустить алгоритм ещё раз.

Сложность алгоритма: $O(\sqrt{r})$$O({\sqrt {r}})$ .

ПримерПравить

$Q=[k]P(mod229)$$Q=[k]P\ (mod\ 229)$ 

$E:y^2\equiv <!--\; \equiv \; -->x^3+x+44(mod229)$$E:y^{2}\equiv x^{3}+x+44\ (mod\ 229)$ 

$P=(5,116),Q=(155,166)$$P=(5,116),Q=(155,166)$ 

$|⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->|=239$$|\langle P\rangle |=239$ 

Шаг 1.Определить функцию.

• $H:⟨<!--\; ⟨\; -->P⟩<!--\; ⟩\; -->\to <!--\; \to \; -->1,2,3,4$$H:\langle P\rangle \rightarrow {1,2,3,4}$ 
• $H(x,y)=(xmod4)+1$$H(x,y)=(x\ mod\ 4)+1$ 
• $(a_1,b_1,R_1)=(79,163,(135,117))$$(a_{1},b_{1},R_{1})=(79,163,(135,117))$ 
• $(a_2,b_2,R_2)=(206,19,(96,97))$$(a_{2},b_{2},R_{2})=(206,19,(96,97))$ 
• $(a_3,b_3,R_3)=(87,109,(84,62))$$(a_{3},b_{3},R_{3})=(87,109,(84,62))$ 
• $(a_4,b_4,R_4)=(219,68,(72,134))$$(a_{4},b_{4},R_{4})=(219,68,(72,134))$ 

Шаг 2. Итерации.

${\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}}$ 

Шаг 3. Обнаружение коллизии.

• При $i=12$$i=12$ : $[192]P+[24]Q=[213]P+[104]Q=(57,105)$$[192]P+[24]Q=[213]P+[104]Q=(57,105)$ 
• Получаем, что $k\equiv <!--\; \equiv \; -->\frac{192-<!--\; -\; -->213}{104-<!--\; -\; -->24}\equiv <!--\; \equiv \; -->176(mod229)$$k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$ 

ЛитератураПравить

Болотов, А. А., Гашков, С. Б., Фролов, А. Б., Часовских, А. А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. — М. : КомКнига, 2006. — С. 328. — ISBN 5-484-00443-8.

Болотов, А. А., Гашков, С. Б., Фролов, А. Б., Часовских, А. А. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. — М. : КомКнига, 2006. — С. 280. — ISBN 5-484-00444-6.

Galbraith, S.D., Smart, N.P. 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