ECDLP

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

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

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

${\displaystyle 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) будем считать:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 1. Найти ${\displaystyle k\ mod\ 2}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представим ${\displaystyle k}$ в виде:

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

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

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

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

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

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

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

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

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

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

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

1. ${\displaystyle m:=\lceil {\sqrt {l}}\rceil }$
2. ${\displaystyle \mathbf {for} \ i:=1\ \mathbf {to} \ m\ \mathbf {do} }$

   ${\displaystyle R:=[i]P}$

   сохранить ${\displaystyle (R,i)}$

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

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

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

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

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

   ${\displaystyle \mathbf {return} \ k}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   ${\displaystyle X'':=X',c'':=c',d'':=d'}$

5. Цикл.

   ${\displaystyle \mathbf {repeat} }$

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

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

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

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

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

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

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

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

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

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

6. Выход.

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

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

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

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

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

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

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

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

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

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

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

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

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

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