ECDLP

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

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

Определения

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

[math]\displaystyle{ E: Y^2 = X^3 + aX + b }[/math], где 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) будем считать:

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

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

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

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

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

Алгоритм

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

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

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

Описание

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

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

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

[math]\displaystyle{ \phi: G\rightarrow C_{{p_1}^{e_1}}\otimes ... \otimes C_{{p_t}^{e_t}} }[/math]

где [math]\displaystyle{ C_{{p_i}^{e_i}} }[/math] — циклическая подгруппа G, [math]\displaystyle{ |C_{{p_i}^{e_i}}| = {p_i}^{e_i} }[/math]

Тогда проекция [math]\displaystyle{ \phi }[/math] на [math]\displaystyle{ C_{p^e} }[/math]:

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

Следовательно, [math]\displaystyle{ {\phi_p}(Q) = [k]{\phi_p}(P) }[/math] в [math]\displaystyle{ C_{p^e} }[/math].

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

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

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

[math]\displaystyle{ k = k_0 + {k_1}p + ... + {k_{e-1}}p^{e-1} }[/math]

Найдем значения [math]\displaystyle{ k_0,k_1,... }[/math] по индукции. Предположим, известно [math]\displaystyle{ k' }[/math] — значение [math]\displaystyle{ k\ mod\ p^t }[/math], то есть

[math]\displaystyle{ k' = k_0 + ... + k_{t-1}p^{t-1} }[/math]

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

[math]\displaystyle{ k = k' + p^tk'' }[/math]

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

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

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

[math]\displaystyle{ Q'' = [s]Q' }[/math] и [math]\displaystyle{ P''=[s]P' }[/math]

Получили ECDLP в поле [math]\displaystyle{ C_p }[/math] в виде [math]\displaystyle{ Q'' = [k_t]P'' }[/math].

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

Как говорилось выше, на практике берутся эллиптические кривые такие, что [math]\displaystyle{ N = hl }[/math], где [math]\displaystyle{ l }[/math] — очень большое простое число, что делает данный метод малоэффективным.

Пример

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

[math]\displaystyle{ E: y^2 \equiv x^3 + 71x + 602\ (mod\ 1009) }[/math]

[math]\displaystyle{ P = (1, 237), Q = (190, 271) }[/math]

[math]\displaystyle{ N = 1060 = 2^2 * 5 * 53 }[/math]

[math]\displaystyle{ |\langle P\rangle| = 530 = 2 * 5 * 53 }[/math]

Шаг 1. Найти [math]\displaystyle{ k\ mod\ 2 }[/math]

• Находим проекции точек на [math]\displaystyle{ C_2 }[/math]:

[math]\displaystyle{ P_2 = 265P = (50, 0) }[/math]

[math]\displaystyle{ Q_2 = 265Q = (50, 0) }[/math]

• Решаем [math]\displaystyle{ Q_2 = [k]P_2 }[/math]

[math]\displaystyle{ k \equiv 1\ (mod\ 2) }[/math]

Шаг 2. Найти [math]\displaystyle{ k\ mod\ 5 }[/math]

• Находим проекции точек на [math]\displaystyle{ C_5 }[/math]:

[math]\displaystyle{ P_5 = 106P = (639, 160) }[/math]

[math]\displaystyle{ Q_5 = 106Q = (639, 849) }[/math]

• Решаем [math]\displaystyle{ Q_5 = [k]P_5 }[/math]

Заметим, что [math]\displaystyle{ Q_5 = -P_5 }[/math], тогда [math]\displaystyle{ k \equiv 4\ (mod\ 5) }[/math]

Шаг 3. Найти [math]\displaystyle{ k\ mod\ 53 }[/math]

• Находим проекции точек на [math]\displaystyle{ C_{53} }[/math]:

[math]\displaystyle{ P_{53} = 10P = (32, 737) }[/math]

[math]\displaystyle{ Q_{53} = 10Q = (592, 97) }[/math]

• Решаем [math]\displaystyle{ Q_{53} = [k]P_{53} }[/math]

[math]\displaystyle{ k \equiv 48\ (mod\ 53) }[/math]

Шаг 4. Найти [math]\displaystyle{ k\ mod\ 530 }[/math]

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

[math]\displaystyle{ k \equiv 419\ (mod\ 530) }[/math]

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

Описание

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

Представим [math]\displaystyle{ k }[/math] в виде:

[math]\displaystyle{ k = k_0 + k_1\lceil {\sqrt l}\rceil }[/math]

Так как [math]\displaystyle{ k \le l }[/math], то [math]\displaystyle{ 0 \le k_0, k_1 \lt \lceil {\sqrt l}\rceil }[/math].

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

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

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

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

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

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

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

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

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

Алгоритм

1. [math]\displaystyle{ m:= \lceil {\sqrt l}\rceil }[/math]
2. [math]\displaystyle{ \mathbf{for}\ i:= 1\ \mathbf{to}\ m\ \mathbf{do} }[/math]

   [math]\displaystyle{ R := [i]P }[/math]

   сохранить [math]\displaystyle{ (R, i) }[/math]

3. [math]\displaystyle{ \mathbf{for}\ j:= 1\ \mathbf{to}\ m\ \mathbf{do} }[/math]

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

   проверить [math]\displaystyle{ T }[/math] в списке [2]

4. [math]\displaystyle{ \mathbf{if}\ T = R\ \mathbf{then} }[/math]

   [math]\displaystyle{ k:=i + j\lceil {\sqrt l}\rceil\ (mod\ l) }[/math]

   [math]\displaystyle{ \mathbf{return}\ k }[/math]

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

Описание

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

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

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

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

Так как [math]\displaystyle{ G }[/math] — конечная, то найдутся такие индексы [math]\displaystyle{ i \lt j }[/math], что [math]\displaystyle{ P_i = P_j }[/math].

Тогда [math]\displaystyle{ P_{i+1} = f(P_i) = f(P_j) = P_{j+1} }[/math].

На самом деле [math]\displaystyle{ P_{i+l} = P_{j+l} }[/math], для [math]\displaystyle{ \forall l \ge 0 }[/math].

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

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

Алгоритм

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

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

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

2. Вычисление [math]\displaystyle{ [a_i]P + [b_i]Q }[/math].

   [math]\displaystyle{ \mathbf{for}\ i:= 1\ \mathbf{to}\ L\ \mathbf{do} }[/math]

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

   [math]\displaystyle{ R_i := [a_i]P + [b_i]Q }[/math]

3. Вычисление [math]\displaystyle{ [c']P + [d']Q }[/math].

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

   [math]\displaystyle{ X' := [c']P + [d']Q }[/math]

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

   [math]\displaystyle{ X'':=X', c'':=c', d'' := d' }[/math]

5. Цикл.

   [math]\displaystyle{ \mathbf{repeat} }[/math]

   [math]\displaystyle{ j:=H(X') }[/math]

   [math]\displaystyle{ X':=X' + R_j }[/math]

   [math]\displaystyle{ c':=c' + a_j\ (mod\ r) }[/math]

   [math]\displaystyle{ d':=d' + b_j\ (mod\ r) }[/math]

   [math]\displaystyle{ \mathbf{for}\ i:= 1\ \mathbf{to}\ 2\ \mathbf{do} }[/math]

   [math]\displaystyle{ j:=H(X'') }[/math]

   [math]\displaystyle{ X'':=X'' + R_j }[/math]

   [math]\displaystyle{ c'':=c'' + a_j\ (mod\ r) }[/math]

   [math]\displaystyle{ d'':=d'' + b_j\ (mod\ r) }[/math]

   [math]\displaystyle{ \mathbf{until}\ X' = X'' }[/math]

6. Выход.

   [math]\displaystyle{ \mathbf{if} d' \ne d''\ \mathbf{then} }[/math]

   [math]\displaystyle{ k \equiv \frac{c' - c''}{d'' - d'}\ (mod\ r) }[/math]

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

Сложность алгоритма: [math]\displaystyle{ O( \sqrt{r}) }[/math].

Пример

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

[math]\displaystyle{ E: y^2 \equiv x^3 + x + 44\ (mod\ 229) }[/math]

[math]\displaystyle{ P = (5, 116), Q = (155, 166) }[/math]

[math]\displaystyle{ | \langle P\rangle | = 239 }[/math]

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

• [math]\displaystyle{ H: \langle P\rangle \rightarrow {1, 2, 3, 4} }[/math]
• [math]\displaystyle{ H(x,y) = (x\ mod\ 4) + 1 }[/math]
• [math]\displaystyle{ (a_1, b_1, R_1)=(79, 163,(135, 117)) }[/math]
• [math]\displaystyle{ (a_2, b_2, R_2)=(206, 19,(96, 97)) }[/math]
• [math]\displaystyle{ (a_3, b_3, R_3)=(87, 109,(84, 62)) }[/math]
• [math]\displaystyle{ (a_4, b_4, R_4)=(219, 68,(72, 134)) }[/math]

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

[math]\displaystyle{ \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} }[/math]

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

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

Литература

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