ECDLP (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=\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 = Ο. При этом образуется подгруппа $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ и точка P называется генератором $\langle P\rangle$.

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

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

Является самой просто атакой в реализации. Необходимо только уметь делать операцию 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$ и $\exists k:Q=[k]P$.

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

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

$\phi :G\rightarrow 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}}$

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

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

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

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

Пусть $P,Q\in C_{p^{e}}$ и $\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'$ — значение $k\ mod\ p^{t}$, то есть

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

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

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

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

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

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

$Q''=[s]Q'$ и $P''=[s]P'$

Получили ECDLP в поле $C_{p}$ в виде $Q''=[k_{t}]P''$.

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

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

Пример

$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. Найти $k\ mod\ 2$

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

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

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

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

$k\equiv 1\ (mod\ 2)$

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

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

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

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

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

Заметим, что $Q_{5}=-P_{5}$, тогда $k\equiv 4\ (mod\ 5)$

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

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

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

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

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

$k\equiv 48\ (mod\ 53)$

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

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

$k\equiv 419\ (mod\ 530)$

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

Описание

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

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

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

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

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

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

Теперь вычисляем «большие шаги». Пусть $P'=[\lceil {\sqrt {l}}\rceil ]P$, найдём $Q_{j}=Q-[j]P'$, $0\leq 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 {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do}$

   $R:=[i]P$

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

3. $\mathbf {for} \ j:=1\ \mathbf {to} \ m\ \mathbf {do}$

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

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

4. $\mathbf {if} \ T=R\ \mathbf {then}$

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

   $\mathbf {return} \ k$

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

Описание

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

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

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

Чтобы реализовать эту идею, выберем случайную функцию для итераций $f:G\rightarrow 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}$, для $\forall l\geq 0$.

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

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

Алгоритм

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

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

   Выбрать функцию $H:\langle P\rangle \rightarrow {1,2,...,L}$

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

   $\mathbf {for} \ i:=1\ \mathbf {to} \ L\ \mathbf {do}$

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

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

3. Вычисление $[c']P+[d']Q$.

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

   $X':=[c']P+[d']Q$

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

   $X'':=X',c'':=c',d'':=d'$

5. Цикл.

   $\mathbf {repeat}$

   $j:=H(X')$

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

   $X'':=X''+R_{j}$

   $c'':=c''+a_{j}\ (mod\ r)$

   $d'':=d''+b_{j}\ (mod\ r)$

   $\mathbf {until} \ X'=X''$

6. Выход.

   $\mathbf {if} d'\neq d''\ \mathbf {then}$

   $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$

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

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

Пример

$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.Определить функцию.

• $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. Итерации.

${\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$: $[192]P+[24]Q=[213]P+[104]Q=(57,105)$
• Получаем, что $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