ECDLP (Elliptic Curve Discrete Logarithm Problem) — задача дискретного логарифмирования в группе точек эллиптической кривой.
Пусть даны эллиптическая кривая E, конечно поле Fp и точки P, Q ∈ E(Fp). Задача ECDLP: найти такое k, если оно существует, что Q = [k]P.
Определения
Эллиптической кривой E над конечным полем Fp называется кривая вида (форма Вейерштрасса):
, где a, b ∈ Fp.
Набор точек на эллиптической кривой в поле Fp, включающий точку «бесконечность» (обозначается как Ο), образует конечную абелеву группу и обозначается как E(Fp).
Точка Q ∈E (Fp) называется обратной точкой к P ∈ E(Fp), если P + Q = Ο и обозначается как Q = -P.
Для натурального числа n и P ∈ E(Fp) будем считать:
![{\displaystyle [n]P=\underbrace {P+P+...+P} _{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c4dc02931a252e7af560096531c4bd73811236e)
Записи [n]P и nP эквиваленты. Определение можно расширить для любого целого числа n, если использовать -P.
Порядком группы точек называется число N равное мощности множества E(Fp) и обозначается как |E(Fp)| = N. Обычно в эллиптической криптографии берутся кривые такие, что N = h * l, где h = 1, 2 или 4, а l — большое простое число.
Порядком точки P ∈ E(Fp) называется минимальное число s такое, что [s]P = Ο. При этом образуется подгруппа
и точка P называется генератором
.
Алгоритмы решения
Полный перебор
Является самой просто атакой в реализации. Необходимо только уметь делать операцию R = [k]P.
Алгоритм
![{\displaystyle k:=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/467746bdc42fc61bb35fb9e0c5b894e1b7a53c15)
![{\displaystyle R:=[k]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fece7aab267ef33e1982f5bde4368c74c9dcae8f)
- if
, then
— решение - else
; перейти к [2].
Сложность алгоритма: Ο(N).
Описание
Пусть G — подгруппа E(Fp),
(то есть предполагается, что число N может быть факторизовано),
и
.
Будем решать задачу о поиске k по модулю
, затем, используя китайскую теорему об остатках, найдем решение k по модулю N.
Из теории групп известно, что существует изоморфизм групп:
![{\displaystyle \phi :G\rightarrow C_{{p_{1}}^{e_{1}}}\otimes ...\otimes C_{{p_{t}}^{e_{t}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/824bd1fc511b36f0f407124b6c7115742e827c89)
где
— циклическая подгруппа G,
Тогда проекция
на
:
![{\displaystyle \phi _{p}={\begin{cases}G\rightarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22990b1f87af4c880b2ffb1c120d092d63a9ec7e)
Следовательно,
в
.
Покажем, как решить задачу в
, сведя её к решению ECDLP в
.
Пусть
и
.
Число
определено по модулю
. Тогда можно записать k в следующем виде:
![{\displaystyle k=k_{0}+{k_{1}}p+...+{k_{e-1}}p^{e-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8b8a5c57eeaff0b159073d6f34dc7c0d1605dc1)
Найдем значения
по индукции. Предположим, известно
— значение
, то есть
![{\displaystyle k'=k_{0}+...+k_{t-1}p^{t-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad7f2873c1150083af5bdedb2fe15af58bd89136)
Теперь хотим определить
и таким образом вычислить
:
![{\displaystyle k=k'+p^{t}k''}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a0a4d8fb5cc41435d452a4e4a1e1b5bd89ff3f7)
Тогда
.
Пусть
и
, тогда
Теперь
— элемент порядка
, чтобы получить элемент порядка
и, следовательно, свести задачу в
необходимо умножить предыдущее выражение на
. Т.о.
и ![{\displaystyle P''=[s]P'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9b1102147f30b131e846a68cfc7e9f96380f5a6)
Получили ECDLP в поле
в виде
.
Предполагая, что можно решить эту задачу в
, находим решение
в
. Используя китайскую теорему об остатках, получаем решение ECDLP в
.
Как говорилось выше, на практике берутся эллиптические кривые такие, что
, где
— очень большое простое число, что делает данный метод малоэффективным.
Пример
Шаг 1. Найти
- Находим проекции точек на
:
![{\displaystyle P_{2}=265P=(50,0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ee91d29a759db7a7b98517bb8f030456cf19ca8)
![{\displaystyle Q_{2}=265Q=(50,0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7b1c0e2befcc9e5b33fff246632c4ae4a2f3986)
- Решаем
![{\displaystyle Q_{2}=[k]P_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c3dd0f467ae3a4a3e79f5878bf89a7100d99cb4)
![{\displaystyle k\equiv 1\ (mod\ 2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/967ea573f25d257ee9516e9584aff5af66ade426)
Шаг 2. Найти
- Находим проекции точек на
:
![{\displaystyle P_{5}=106P=(639,160)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d87c79c50dd9bf9af3b32809065c56c92566065)
![{\displaystyle Q_{5}=106Q=(639,849)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/729669e4250604ac552895d7507a65a86bcc0df9)
- Решаем
![{\displaystyle Q_{5}=[k]P_{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1fbf50b8e3404d6f723797d77ea58fab62ddf6a)
- Заметим, что
, тогда ![{\displaystyle k\equiv 4\ (mod\ 5)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abd1eacafb8e719b99a418205528779e0c1eee7d)
Шаг 3. Найти
- Находим проекции точек на
:
![{\displaystyle P_{53}=10P=(32,737)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee81885be3d9da982ebe35a28088a7543b229e9f)
![{\displaystyle Q_{53}=10Q=(592,97)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43f001ccfede5d40efc873db8e01734076e65f7e)
- Решаем
![{\displaystyle Q_{53}=[k]P_{53}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2357101e41011bfbca5e585500d41e033a052950)
![{\displaystyle k\equiv 48\ (mod\ 53)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bb5604fe4c789673fe88cab36e54bbe4e299694)
Шаг 4. Найти
- Из китайской теоремы об остатках для значений, полученных на предыдущих шагах 1-3, имеем, что
![{\displaystyle k\equiv 419\ (mod\ 530)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61be2baf323f1f875beeda8fa9c34477fad84531)
Описание
Пусть
— циклическая подгруппа
.
Представим
в виде:
![{\displaystyle k=k_{0}+k_{1}\lceil {\sqrt {l}}\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/432a85b52e6324f394d1405b1a6a274158ada00b)
Так как
, то
.
Вычисляем список «маленьких шагов»
,
и сохраняем пары
.
Сложность вычислений:
.
Теперь вычисляем «большие шаги». Пусть
, найдём
,
.
Во время поиска
пробуем найти среди сохранённых пар
такую, что
. Если удалось найти такую пару, то
.
Или, что то же самое:
![{\displaystyle [i]P=Q-[j\lceil {\sqrt {l}}\rceil ]P,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f488ccbe8f7705f236893abe7475357e39d3a1f)
.
Сложность вычислений «больших шагов»:
.
В таком случае общая сложность метода
, но также требуется
памяти для хранения, что является существенным минусом алгоритма.
Алгоритм
![{\displaystyle m:=\lceil {\sqrt {l}}\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/622109841687418b48a49bd12786db2f9d999e2b)
![{\displaystyle R:=[i]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9641367721067f18d00d262c56a6042e19801dc)
- сохранить
![{\displaystyle (R,i)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/970cfd385827d2f20bc1b1b51bef3e9caef0d06c)
![{\displaystyle T:=Q-[j\lceil {\sqrt {l}}\rceil ]P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7318583a0bbe3b9efe03ed3f389fdbc4716e8b4)
- проверить
в списке [2]
![{\displaystyle k:=i+j\lceil {\sqrt {l}}\rceil \ (mod\ l)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e2260a15a34607009e9248b09d3fe67a1aca915)
![{\displaystyle \mathbf {return} \ k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ef85821d943d172d7fe48b30dc3cc2473484293)
Описание
Пусть
— циклическая подгруппа
.
Основная идея метода — найти различные пары
и
по модулю
такие, что
.
Тогда
или
. Следовательно,
.
Чтобы реализовать эту идею, выберем случайную функцию для итераций
, и случайную точку
для начала обхода. Следующая точка вычисляется как
.
Так как
— конечная, то найдутся такие индексы
, что
.
Тогда
.
На самом деле
, для
.
Тогда последовательность
— периодична с периодом
(см. рис).
Так как f случайная функция, то, согласно парадоксу дней рождения, совпадение случится примерно через
итераций. Для ускорения поиска коллизий используется метод, придуманный Флойдом для поиска длины цикла: вычисляется сразу пара значений
для
, пока не найдется совпадение.
Алгоритм
- Инициализация.
- Выбрать число ветвей L (обычно берётся 16)
- Выбрать функцию
![{\displaystyle H:\langle P\rangle \rightarrow {1,2,...,L}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8929f8f26aa1a3d94961fd3f47b101fdf36f43fd)
- Вычисление
.
- Взять случайные
![{\displaystyle a_{i},b_{i}\in [0,r-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36da5d7faf7fe288ab9e55e2259438f87cef3d9d)
![{\displaystyle R_{i}:=[a_{i}]P+[b_{i}]Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65bb8992eba9c7dcabb6abc7ceed90791a8b149f)
- Вычисление
. - Взять случайные
![{\displaystyle c',d'\in [0,r-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adf0c8286f3967bcd111090b9b43675d6590d37f)
![{\displaystyle X':=[c']P+[d']Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/888a428d2b00e7d06ea8015075d96a2cbbfb23eb)
- Подготовка к циклу.
![{\displaystyle X'':=X',c'':=c',d'':=d'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/788cb2427de3e9561772c7d74240a55a3cc977d9)
- Цикл.
![{\displaystyle j:=H(X')}](https://wikimedia.org/api/rest_v1/media/math/render/svg/063b079914da34c45b2868e43d7b85413f91399e)
![{\displaystyle X':=X'+R_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1611efbdd7edc5c01322b06ee0a0d27c68be39a)
![{\displaystyle c':=c'+a_{j}\ (mod\ r)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9618b21b174978495792929c9d114eb6d3d2a086)
![{\displaystyle d':=d'+b_{j}\ (mod\ r)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1abad7ce70d1855bbd6b33d0a3c1c992f547aaf9)
![{\displaystyle j:=H(X'')}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed178164efba322f91872692a91819a2f23ca4cb)
![{\displaystyle X'':=X''+R_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5a97d747d32a4c725bdbb7c7a6e8deed796c85c)
![{\displaystyle c'':=c''+a_{j}\ (mod\ r)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a8ad337241ca327ab77a8b5e01d1f2769c0e93c)
![{\displaystyle d'':=d''+b_{j}\ (mod\ r)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f054bc6aaacf506cce24d211cf5c6664c57f677e)
![{\displaystyle \mathbf {until} \ X'=X''}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1a389202e00e1c39d6a3026dcdd5a79f3d437fc)
- Выход.
![{\displaystyle k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba7f28a14028b03a809f3024b7e249f0ba021326)
ОШИБКА или запустить алгоритм ещё раз.
Сложность алгоритма:
.
Пример
Шаг 1.Определить функцию.
![{\displaystyle H:\langle P\rangle \rightarrow {1,2,3,4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ac9b6fb698b0b67e95787d918e666b603e93e58)
![{\displaystyle H(x,y)=(x\ mod\ 4)+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3002982084fb0860cd767a1d347ad322df9e520b)
![{\displaystyle (a_{1},b_{1},R_{1})=(79,163,(135,117))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c006fd8835ad9580fbcb990ceb49bd7936cdb5d5)
![{\displaystyle (a_{2},b_{2},R_{2})=(206,19,(96,97))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f7e25021debb777418826eb731d3f2ee22f7d4f)
![{\displaystyle (a_{3},b_{3},R_{3})=(87,109,(84,62))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/802baa84d1467b3a10814c03bf9cacf61a8bfceb)
![{\displaystyle (a_{4},b_{4},R_{4})=(219,68,(72,134))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/252cc2e155233740904a805cdc3e69668a52df4f)
Шаг 2. Итерации.
Шаг 3. Обнаружение коллизии.
- При
: ![{\displaystyle [192]P+[24]Q=[213]P+[104]Q=(57,105)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7e31b7310cc241817a48f4d70750fb098b333b4)
- Получаем, что
![{\displaystyle k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fde4a6bc216a574a20de6f247b9da6317494b13b)
Литература
Болотов, А. А., Гашков, С. Б., Фролов, А. Б., Часовских, А. А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. — М. : КомКнига, 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