ПРИМЕНЕНИЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ В КРИПТОГРАФИИ

Введение

Эллиптической кривой является множество точек, которые удовлетворяют уравнению y² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆.

Если положить, что характеристика поля не равна 2 и 3, тогда эллиптическая кривая будет плоской кривой, которая определена уравнением вида

y² = x³ + ax + b, где a и b — действительные числа. Этот вид уравнений

называется уравнениями Вейерштрасса.

Эллиптические кривые бывают гладкими и сингулярными. Для гладких эллиптических кривых всегда выполняется неравенство:4a³ + 27b² ≠ 0.

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

Рисунок 1. Слева в 1 и 2 столбце приведены примеры гладких эллиптических кривых, в 3 столбце - сингулярных, справа эллиптическая кривая в общем виде.

Эллиптические кривые в криптографии

Важным моментом является то, что все рассмотренные до этого кривые являются эллиптическими кривыми над вещественными числами. Отсюда возникает проблема округления. Т.е., пользуясь кривыми над вещественными числами, невозможно получить биекцию между исходным текстом и зашифрованными данными. Чтобы не возникала проблема округления, в криптографии используются только эллиптические кривые над конечными полями. Таким образом, эллиптической кривой будет являться набор точек, координаты которых принадлежат конечному полю. На сегодняшний день в криптографии используются два вида эллиптических кривых: над конечным полем Z_P, которое является кольцом вычетов по модулю простого числа. А также над полем GF(2^m), являющимся бинарным конечным полем. Эллиптических кривые над полем GF(2^m) обладают важным свойством. Элементы поля GF(2^m) можно легко представить в виде n-битных кодовых слов, что позволяет ускорить аппаратную реализацию эллиптических алгоритмов.

Все математические операции на эллиптических кривых над конечным полем производятся, опираясь на законы конечного поля, над которым эллиптическая кривая построена. Таким образом, при вычислении, например, суммы двух точек эллиптической кривой E над кольцом вычетов Z_P операции производятся по модулю числа p. Однако если сложить два одинаковых элемента из бинарного конечного поля, то в результате получается 0, поскольку сложение происходит по модулю 2. Получается, что характеристика этого поля равна 2. Но эллиптическая кривая вида y² = x³ + ax + b, описанная над полем характеристики 2 или 3, становится сингулярной, что является нежелательным для использования в криптографии. Поэтому над бинарным конечным полем применяются кривые вида:

y² + xy = x³ + ax² + b, где b≠0.

Другим важным понятием эллиптической криптографии является порядок эллиптической кривой, показывающий количество точек кривой над конечным полем. По теорема Хассе утверждается, что при количество точек N кривой, которая определена над полем Z_q с q элементами, справедливо равенство: |N - (q + 1)| ≤ 2√q.Учитывая, что бинарное конечное поле GF(2ⁿ)  состоит из 2ⁿ элементов, можно утверждать, что порядок кривой  E₂ⁿ(a,b) равен 2ⁿ+1-t, где |t| ≤ √(2ⁿ).Если t делится на характеристику поля без остатка, эллиптическая кривая над бинарным конечным полем в таком случае называется суперсингулярной.

Криптография на эллиптических кривых

Все точки эллиптической кривой над конечным полем образуют группу. И для такой группы определены операция сложения и умножения точки G на число k, представляя умножение как сумма G+G+..+G из k слагаемых. Пусть имеется сообщение M, которое представлено в виде целого числа. Сообщение можно зашифровать пользуясь выражением: C=M*G. Возникает задача определения сложности восстановления сообщения M, при известных параметрах кривой E(a,b), зашифрованного текста С и точки G. Данная задача является не чем иным, как дискретным логарифмом на эллиптической кривой, и быстрого решения она не имеет. Кроме того, принято считать, что задача дискретного логарифма на эллиптической кривой значительно труднее для решения, чем задача дискретного логарифмирования в конечных полях. Наиболее быстрые методы, которые разработаны для конечных полей, становятся бесполезными в случае эллиптических кривых. Для решения дискретного логарифма на конечном поле существуют сравнительно быстрые алгоритмы, которые имеют сложность

O(exp(c(log p log log p)^d)), где p является размером поля, а c и d некоторыми константами. Данные алгоритмы носят название "субэкспоненциальные" и позволяют достаточно легко раскрывать дискретный логарифм в конечном поле, при условии, что размер поля очень большой, порядка 2¹⁰²⁴.

Наряду с дискретными логарифмами на конечных полях наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность O(√q), где q — количество точек эллиптической кривой. Следовательно, для обеспечения уровня стойкости в 2⁸⁰ операций нужно, чтобы значение q=2¹⁶⁰. При вычислении дискретного логарифма в конечном поле необходимо поле порядка q=2¹⁰²⁴, чтобы получить аналогичный уровень сложности.

Следует иметь ввиду, что мощность вычислительной техники постоянно повышается, а значит значение q будет также постоянно увеличиваться.

Но так как графики функций O (exp(c(log p log log p)^d)) и O(√q) кординально отличаются друг от друга, в группе точек эллиптической кривой значение q будет расти в разы медленнее, чем в произвольном конечном поле.

Варианты атак

1. Алгоритм Шенкса. Алгоритм также известен как алгоритм больших и малых шагов (как Baby-step/giant-step). Для группы размером n происходит вычисление таблицы, размер которой будет n^1/2. После этого по данной таблице осуществляется поиск искомого элемента. Алгоритм обладает сложностью O(√q).
2. Уязвимость сингулярных и суперсингулярных кривых. Не существует общих методов решения задачи дискретного логарифма на эллиптических кривых. Однако такие методы на самом деле существуют только для определенного рода кривых: сингулярных и суперсингулярных. Благодаря специфичным свойствам этих кривых задача дискретного логарифма на эллиптической кривой сводится к задаче дискретного логарифма в конечном поле. Поэтому для такого рода кривых стандартные 160-320 битные ключи будут сильно уязвимы. Злоумышленники смогут вскрыть секретный ключ, за относительно короткое время.
3. Алгоритм Полига-Хеллмана. Он является алгоритмом решения дискретного логарифма. Пусть n это количество точек эллиптической кривой, а также само число n раскладывается на простые числа p₁, p₂,.., p_n. Весь метод приводится к тому, что необходимо найти дискретные логарифмы по модулю простого числа p_i. После этого общее решение находится с помощью китайской теоремы об остатках. Атака сводит проблему дискретного логарифма в большом поле n к задаче с намного меньшим полем p. Для противостояния данной атаке необходимо выбирать кривые, количество точек которых делится на весьма большое простое число q≈n.
4. Уязвимость аномальных кривых. Количество точек n эллиптической кривой вычисляется по формуле n=q+1-t, где q — размер исходного поля. Если t делится на 2, кривая называется суперсингулярной, поэтому может показаться отличной идеей использовать кривые, количество точек которых равно q, т.е. t=1. Данные кривые называются аномальными. Решение дискретного логарифма на аномальных эллиптических кривых оказывается намного более простой задачей, чем для сингулярных и суперсингулярных кривых.

Список литературы:

1. Болотов А., Гашков С., Фролов А., Часовских А. Элементарное введение в эллиптическую криптографию.