ECDLP

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

Записи [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.

Алгоритм

if , then  — решение else ; перейти к .

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

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

Описание Пусть G — подгруппа E(Fp), (то есть предполагается, что число N может быть факторизовано), и .

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

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

где  — циклическая подгруппа G,

Тогда проекция на :

Следовательно, в .

Покажем, как решить задачу в , сведя её к решению ECDLP в .

Пусть и .

Число определено по модулю . Тогда можно записать k в следующем виде:

Найдем значения по индукции. Предположим, известно  — значение , то есть

Теперь хотим определить и таким образом вычислить :

Тогда .

Пусть и , тогда

Теперь  — элемент порядка , чтобы получить элемент порядка и, следовательно, свести задачу в необходимо умножить предыдущее выражение на . Т.о. и

Получили ECDLP в поле в виде .

Предполагая, что можно решить эту задачу в , находим решение в . Используя китайскую теорему об остатках, получаем решение ECDLP в .

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

Пример

Шаг 1. Найти Находим проекции точек на :

Решаем

Шаг 2. Найти Находим проекции точек на :

Решаем Заметим, что , тогда

Шаг 3. Найти Находим проекции точек на :

Решаем

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

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

Описание Пусть  — циклическая подгруппа .

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

Так как , то .

Вычисляем список «маленьких шагов» , и сохраняем пары .

Сложность вычислений: .

Теперь вычисляем «большие шаги». Пусть , найдём , .

Во время поиска пробуем найти среди сохранённых пар такую, что . Если удалось найти такую пару, то .

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

. Сложность вычислений «больших шагов»:.

В таком случае общая сложность метода , но также требуется памяти для хранения, что является существенным минусом алгоритма.

Алгоритм

сохранить

проверить в списке

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

Описание Пусть  — циклическая подгруппа .

Основная идея метода — найти различные пары и по модулю такие, что .

Тогда или . Следовательно, .

Чтобы реализовать эту идею, выберем случайную функцию для итераций , и случайную точку для начала обхода. Следующая точка вычисляется как .

Так как  — конечная, то найдутся такие индексы , что .

Тогда .

На самом деле , для .

Тогда последовательность  — периодична с периодом (см. рис).

Так как f случайная функция, то, согласно парадоксу дней рождения, совпадение случится примерно через итераций. Для ускорения поиска коллизий используется метод, придуманный Флойдом для поиска длины цикла: вычисляется сразу пара значений для , пока не найдется совпадение.

Алгоритм Инициализация. Выбрать число ветвей L (обычно берётся 16) Выбрать функцию Вычисление .

Взять случайные

Вычисление . Взять случайные

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

Цикл.

Выход.

ОШИБКА или запустить алгоритм ещё раз.

Сложность алгоритма: .

Пример

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

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

Шаг 3. Обнаружение коллизии. При : Получаем, что

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

Категория:Криптография