Лекция: Атаки на шифры определенные эллиптическими кривыми

Пусть конечное поле, характеристика p 2. Рассмотрим многочлен вида

,

. Через обозначим множество корней многочлена Е в поле вместе с бесконечной точкой µ. Таким образом,

.

Очевидно, что если, то. Ранее в параграфе §5.7было показано, что на (в частности, на ) вводится групповая операция.

В криптографической практике используют циклические подгруппы групп точек эллиптической кривой над конечным полем. Стойкость соответствующих криптографических протоколов определяется сложностью проблемы дискретного логарифмирования в этих подгруппах. Центральным параметром здесь является порядок циклической подгруппы. Если это число составное, то группа содержит собственные подгруппы. Поэтому задача вычисления дискретного логарифма в циклической группе сводится к одной или нескольким задачам дискретного логарифмирования в собственных подгруппах, то есть группах меньшего порядка. В настоящее время известен эффективный алгоритм вычисления порядка групп для любых эллиптических кривых Е над произвольным конечным полем. Этот алгоритм основан на применении теории модулярных функций, поэтому его изложение выходит за рамки этой книги. Зная порядок группы, легко получить порядок любой ее циклической подгруппы.

Приведем здесь алгоритм, решающий следующую задачу. Пусть G конечная абелева группа в мультипликативной записи. Задан элемент и требуется вычислить его порядок n в группе G. Предположим, что известна граница сверху для порядка группы G, то есть. Тогда. В случае эллиптической кривой выполняется очевидное неравенство. Приведем алгоритм, принадлежащий Шенксу.

Входные данные алгоритма. Группа G (конечная абелева) в мультипликативной записи, число В такое, что и элемент. Выходные данные алгоритма. .

Шаг 1. Вычислить. Вычислить элементы 1, g,…, gr-1, упорядочить массив пар, по второй координате.

Шаг 2. Вычислить. Для каждого b, вычислить и проверить является ли этот элемент группы второй координатой какой-либо пары из упорядоченного массива пар. Если это так и, то запомнить число .

Шаг 3. Число n есть наименьшее среди чисел, вычисленных на предыдущем шаге. Алгоритм заканчивает свою работу.

Докажем теперь, что алгоритм всегда даст правильный результат. Для этого достаточно заметить, что неизвестное число n может быть записано в виде, где. Действительно, разделим n на r с остатком. С учетом значения r нетрудно получить, что и частное и остаток лежат между 0 и r-1: .

Сложность алгоритма оценивается следующим образом. Полагают, что время выполнения одной операции и время сравнения двух элементов в группе G совпадают. На шаге 1 требуется вычислить r элементов группы G и упорядочить массив, состоящий из r пар. Это требует не более операций. На шаге 2 требуется r раз произвести поиск в упорядоченном массиве пар. Это также требует не более операций сравнения в группе G. Таким образом, общая оценка сложности алгоритма Шенкса имеет вид операций. При этом объем использованной памяти составляет ячеек. Следует упомянуть, что в закрытой печати этот алгоритм открытый Шенксом в 1969 году был опубликован ранее Шенкса в 1962 году А.О. Гельфондом. Для атаки на проблему дискретного логарифма существенно используют разложение порядка группы. Соответствующий алгоритм и оценки были получены и опубликованы в 1965 году в закрытой печати В.И.Нечаевым. В 1977 году близкий к нему алгоритм был опубликован Полигом и Хеллманом и независимо Зильбером. Применительно к мультипликативной группе оба алгоритма прекрасно представлены в книге [Нечаев В.И. Элементы криптографии. М.: Высшая школа, 1999]. Применительно к эллиптическим кривым они описаны в книге [А.А. Блотова, С.Б. Гашкова, А.Б. Фролова. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М., КомКнига, 2006].

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

Входные данные алгоритма. Группа G (конечная абелева) в мультипликативной записи, элемент, для некоторого n и для некоторых В, С. Выходные данные алгоритма. Наименьшее натуральное n0такое, что и .

Шаг 1. Вычислить. Вычислить элементы gc, gc+1,…, grc+r-1, упорядочить массив пар, по второй координате.

Шаг 2. Вычислить. Для каждого b, вычислить и проверить является ли этот элемент группы второй координатой какой-либо пары из упорядоченного массива пар. Если это так и, то запомнить число .

Шаг 3. Число n0есть наименьшее среди чисел, вычисленных на предыдущем шаге. Алгоритм заканчивает свою работу.

Доказывается, что алгоритм действительно вычисляет требуемое n0. Очевидно также, что число n0которое находит алгоритм, не обязательно является точным порядком элемента g. Это число может быть кратным точного порядка g. Доказывается, что сложность алгоритма составляет операций в группе G. Объем использованной памяти составляет ячеек. Отметим, что этот алгоритм не имеет отношения к ускорению собственно алгоритма Шенкса (вычисление дискретного логарифма при известном порядке группы, что характерно для протоколов на эллиптических кривых), так как лишь уточняет порядок группы. С точки зрения атаки принципиальное ускорение достигается при использовании разложения порядка группы в случае, когда в этом разложении отсутствует большой множитель. Отсюда и криптографическое требование к порядку группы – обязательность большого множителя.

Вернемся к эллиптической кривой. Пусть Р точка из. Требуется узнать точный порядок l точки Р в группе. Известна следующая теорема Хассе

ТЕОРЕМА. Пусть. Тогда .

Из теоремы Хассе следует, что существует натуральное n кратное l такое, что (например, таким n может являться ). Значит, применив изложенный выше алгоритм, можно найти такое n за операций в. Число n следует далее разложить на простые множители. Потом уже легко вычислить точный порядок Р в. Изложенный алгоритм является экспоненциальным, то есть он не эффективен при больших q. Однако при сравнительно небольших он вполне приемлем.

Глава 50.