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$, где 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}{\underbrace{P+P+...+P}}$

Записи [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=\overline{1,s}\}$ и точка P называется генератором $⟨P⟩$.

Алгоритмы решения

Полный перебор

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

Алгоритм

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

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

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

Описание

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

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

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

$\varphi :G\to C_{{p_1}^{e_1}}\otimes ...\otimes C_{{p_t}^{e_t}}$

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

Тогда проекция $\varphi$ на $C_{p^e}$:

${\varphi }_p=\{\begin{array}{l}G\to C_{p^e}\\ R⟼[\frac{N}{p^e}]R\end{array}$

Следовательно, ${\varphi }_p(Q)=[k]{\varphi }_p(P)$ в $C_{p^e}$.

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

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

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

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

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

$k^{\prime }=k_0+...+k_{t-1}{p}^{t-1}$

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

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

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

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

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

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

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

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

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

Пример

$Q=[k]P(mod1009)$

$E:y^2\equiv x^3+71x+602(mod1009)$

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

$N=1060=2^2*5*53$

$|⟨P⟩|=530=2*5*53$

Шаг 1. Найти $kmod2$

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

$P_2=265P=(50,0)$

$Q_2=265Q=(50,0)$

• Решаем $Q_2=[k]P_2$

$k\equiv 1(mod2)$

Шаг 2. Найти $kmod5$

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

$P_5=106P=(639,160)$

$Q_5=106Q=(639,849)$

• Решаем $Q_5=[k]P_5$

Заметим, что $Q_5=-P_5$, тогда $k\equiv 4(mod5)$

Шаг 3. Найти $kmod53$

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

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

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

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

$k\equiv 48(mod53)$

Шаг 4. Найти $kmod530$

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

$k\equiv 419(mod530)$

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

Описание

Пусть $G=⟨P⟩$ — циклическая подгруппа $E(F_p);|⟨P⟩|=l;Q\in G$.

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

$k=k_0+k_1\lceil \sqrt{l}\rceil$

Так как $k\le l$, то $0\le k_0,k_1<\lceil \sqrt{l}\rceil$.

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

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

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

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

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

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

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

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

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

Алгоритм

1. $m:=\lceil \sqrt{l}\rceil$
2. $\mathbf{𝐟}\mathbf{𝐨}\mathbf{𝐫}i:=1\mathbf{𝐭}\mathbf{𝐨}m\mathbf{𝐝}\mathbf{𝐨}$

   $R:=[i]P$

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

3. $\mathbf{𝐟}\mathbf{𝐨}\mathbf{𝐫}j:=1\mathbf{𝐭}\mathbf{𝐨}m\mathbf{𝐝}\mathbf{𝐨}$

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

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

4. $\mathbf{𝐢}\mathbf{𝐟}T=R\mathbf{𝐭}\mathbf{𝐡}\mathbf{𝐞}\mathbf{𝐧}$

   $k:=i+j\lceil \sqrt{l}\rceil (modl)$

   $\mathbf{𝐫}\mathbf{𝐞}\mathbf{𝐭}\mathbf{𝐮}\mathbf{𝐫}\mathbf{𝐧}k$

ρ-метод Полларда

Описание

Пусть $G=⟨P⟩$ — циклическая подгруппа $E(F_p);|G|=r;Q\in G$.

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

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

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

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

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

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

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

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

Алгоритм

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

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

   Выбрать функцию $H:⟨P⟩\to 1,2,...,L$

2. Вычисление $[a_i]P+[b_i]Q$.

   $\mathbf{𝐟}\mathbf{𝐨}\mathbf{𝐫}i:=1\mathbf{𝐭}\mathbf{𝐨}L\mathbf{𝐝}\mathbf{𝐨}$

   Взять случайные $a_i,b_i\in [0,r-1]$

   $R_i:=[a_i]P+[b_i]Q$

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

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

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

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

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

5. Цикл.

   $\mathbf{𝐫}\mathbf{𝐞}\mathbf{𝐩}\mathbf{𝐞}\mathbf{𝐚}\mathbf{𝐭}$

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

   $X^{\prime }:=X^{\prime }+R_j$

   $c^{\prime }:=c^{\prime }+a_j(modr)$

   $d^{\prime }:=d^{\prime }+b_j(modr)$

   $\mathbf{𝐟}\mathbf{𝐨}\mathbf{𝐫}i:=1\mathbf{𝐭}\mathbf{𝐨}2\mathbf{𝐝}\mathbf{𝐨}$

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

   $X^{″}:=X^{″}+R_j$

   $c^{″}:=c^{″}+a_j(modr)$

   $d^{″}:=d^{″}+b_j(modr)$

   $\mathbf{𝐮}\mathbf{𝐧}\mathbf{𝐭}\mathbf{𝐢}\mathbf{𝐥}{X}^{\prime }=X^{″}$

6. Выход.

   $\mathbf{𝐢}\mathbf{𝐟}{d}^{\prime }\ne d^{″}\mathbf{𝐭}\mathbf{𝐡}\mathbf{𝐞}\mathbf{𝐧}$

   $k\equiv \frac{c^{\prime }-c^{″}}{d^{″}-d^{\prime }}(modr)$

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

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

Пример

$Q=[k]P(mod229)$

$E:y^2\equiv x^3+x+44(mod229)$

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

$|⟨P⟩|=239$

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

• $H:⟨P⟩\to 1,2,3,4$
• $H(x,y)=(xmod4)+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. Итерации.

$\begin{array}{ccccccc}Iteration& c^{\prime }& d^{\prime }& [c^{\prime }]P+[d^{\prime }]Q& c^{″}& d^{″}& [c^{″}]P+[d^{″}]Q\\ 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{(}\mathbf{𝟓}\mathbf{𝟕},\mathbf{𝟏}\mathbf{𝟎}\mathbf{𝟓}\mathbf{)}& 213& 104& \mathbf{(}\mathbf{𝟓}\mathbf{𝟕},\mathbf{𝟏}\mathbf{𝟎}\mathbf{𝟓}\mathbf{)}\\ \end{array}$

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

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

Литература

Болотов, А. А., Гашков, С. Б., Фролов, А. Б., Часовских, А. А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. — М. : КомКнига, 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