Русская Википедия:ECDLP

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

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

Определения

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

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

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

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

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

Алгоритм

<math>k:=1</math>
<math>R:=[k]P</math>
if <math>R = Q</math>, then <math>k</math> — решение
else <math>k:=k+1</math>; перейти к [2].

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

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

Описание

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

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

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

<math>\phi: G\rightarrow C_{{p_1}^{e_1}}\otimes ... \otimes C_{{p_t}^{e_t}}</math>

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

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

<math>\phi_p = \begin{cases}

G\rightarrow C_{p^e} \\ R\longmapsto [\frac{N}{p^e}]R \end{cases}</math>

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

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

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

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

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

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

Тогда <math>Q = [k']P + [k]([p^t]P)</math>.

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

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

Получили ECDLP в поле <math>C_p</math> в виде <math>Q = [k_t]P</math>.

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

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

Пример

<math> E: y^2 \equiv x^3 + 71x + 602\ (mod\ 1009)</math>

<math> |\langle P\rangle| = 530 = 2 * 5 * 53</math>

Шаг 1. Найти <math>k\ mod\ 2</math>

Находим проекции точек на <math>C_2</math>:

Решаем <math>Q_2 = [k]P_2</math>

<math>k \equiv 1\ (mod\ 2)</math>

Шаг 2. Найти <math>k\ mod\ 5</math>

Находим проекции точек на <math>C_5</math>:

Решаем <math>Q_5 = [k]P_5</math>

Заметим, что <math>Q_5 = -P_5</math>, тогда <math>k \equiv 4\ (mod\ 5)</math>

Шаг 3. Найти <math>k\ mod\ 53</math>

Находим проекции точек на <math>C_{53}</math>:

Решаем <math>Q_{53} = [k]P_{53}</math>

<math>k \equiv 48\ (mod\ 53)</math>

Шаг 4. Найти <math>k\ mod\ 530</math>

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

<math>k \equiv 419\ (mod\ 530)</math>

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

Описание

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

Представим <math>k</math> в виде:

<math>k = k_0 + k_1\lceil {\sqrt l}\rceil </math>

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

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

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

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

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

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

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

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

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

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

Алгоритм

<math>m:= \lceil {\sqrt l}\rceil</math>
<math> \mathbf{for}\ i:= 1\ \mathbf{to}\ m\ \mathbf{do} </math>
<math> R := [i]P</math>

сохранить <math>(R, i)</math>
<math> \mathbf{for}\ j:= 1\ \mathbf{to}\ m\ \mathbf{do} </math>
<math> T := Q - [j\lceil {\sqrt l}\rceil]P</math>

проверить <math>T</math> в списке [2]
<math> \mathbf{if}\ T = R\ \mathbf{then}</math>
<math> k:=i + j\lceil {\sqrt l}\rceil\ (mod\ l)</math>

<math>\mathbf{return}\ k</math>

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

Описание

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

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

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

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

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

Тогда <math>P_{i+1} = f(P_i) = f(P_j) = P_{j+1}</math>.

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

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

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

Алгоритм

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

Выбрать функцию <math>H:\langle P\rangle \rightarrow {1, 2, ..., L} </math>
Вычисление <math>[a_i]P + [b_i]Q</math>.
<math> \mathbf{for}\ i:= 1\ \mathbf{to}\ L\ \mathbf{do} </math>
Взять случайные <math>a_i,b_i \in [0, r-1]</math>

<math>R_i := [a_i]P + [b_i]Q</math>
Вычисление <math>[c']P + [d']Q</math>.
Взять случайные <math>c',d' \in [0, r-1]</math>

<math>X' := [c']P + [d']Q</math>
Подготовка к циклу.
<math>X:=X', c:=c', d := d'</math>
Цикл.
<math> \mathbf{repeat}</math>
<math>j:=H(X')</math>

<math>X':=X' + R_j</math>

<math>c':=c' + a_j\ (mod\ r)</math>

<math>d':=d' + b_j\ (mod\ r)</math>

<math> \mathbf{for}\ i:= 1\ \mathbf{to}\ 2\ \mathbf{do} </math>
<math>j:=H(X)</math>

<math>X:=X + R_j</math>

<math>c:=c + a_j\ (mod\ r)</math>

<math>d:=d + b_j\ (mod\ r)</math>

<math> \mathbf{until}\ X' = X</math>
Выход.
<math> \mathbf{if} d' \ne d\ \mathbf{then}</math>
<math>k \equiv \frac{c' - c}{d - d'}\ (mod\ r)</math>

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

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

Пример

<math> E: y^2 \equiv x^3 + x + 44\ (mod\ 229)</math>

<math>| \langle P\rangle | = 239</math>

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

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

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

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

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:ECDLP

Содержание

Определения

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

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

Алгоритм

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

Описание

Пример

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

Описание

Алгоритм

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

Описание

Алгоритм

Пример

Литература

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты