Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Случайный выбор (Е,В). Взяв какое-либо большое конечное поле F9, можно следующим образом осуществить одновременный выбор E и В = (х, у) Є Е. (Будем предполагать, что характеристика р поля F9 больше 3, так что эллиптическая кривая задана уравнением (1) из § 1; при q = 2Г или Зг нетрудно сделать очевидные изменения в дальнейшем изложении.) Выбираем сначала случайным образом три
* 2 3
элемента из F9 в качестве х,у,а. Далее полагаем b = у — (х + ах). Убеждаемся в том, что кубический многочлен X + ах + b не имеет
3 2
кратных корней, что равносильно проверке условия 4а + 276 ф 0. (Если это условие не выполняется, берем другую случайную тройку х, у, а.) Полагаем В = (х, у). Тогда В — точка, на эллиптической кри-
2 3
вой у = X -f ах + Ь.
Число JV точек кривой можно найти несколькими способами. Первый полиномиальный алгоритм для вычисления # Е, построенный Рене Шуфом (Rene Schoof), является даже детерминистическим. Он основывается на нахождении значения jf. E по модулю I для всех простых чисел /, меньших некоторой границы. Для этого анализируется действие автоморфизма Фробениуса (отображения в р-ю степень) на точках порядка /.
В статье Шуфа оценка времени работы была фактически О (log q), т.е. хотя и полиномиальной, однако быстро растущей. Вначале казалось, что алгоритм не имеет практического значения. Однако с тех пор многие пытались повысить скорость алгоритма Шуфа (Миллер (V. Miller), Элкис (N. Elkis), Бухман (J. Buchman), Мюллер (V. Muller), Менезес (A. Menezes), Чарлап (L. Charlap), Коули (R. Coley) и Роббинс (D. Robbins)). Кроме того, Эткин (А. О. L. Atkin) разработал другой метод, который, хотя и не гарантирует полиномиального времени работы, на практике дает весьма удовлетворительные результаты. В результате всех этих усилий стало возможным вычислять порядок произвольной эллиптической кривой над F9, если q — степень простого числа, записываемая 50 или даже 100 знаками. Некоторые методы нахождения числа точек на эллиптической кривой рассматриваются в работах из списка литературы в конце этого параграфа.
Следует также отметить, что хотя для реализации систем Диффи-Хеллмана или Эль-Гамаля знать JV не нужно, на практике желательно быть уверенным в их надежности, которая зависит от того, имеет ли JV большой простой делитель. Если JV есть произведение малых простых чисел, то для решения задачи дискретного логарифми-
208
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
рования можно использовать метод Полига-Силвера-Хеллмана (см. § IV. 3). Заметим, что метод Полига-Силвера-Хеллмана решает задачу дискретного логарифмирования в любой конечной абелевой группе (в отличие от также рассмотренного в § IV. 3 алгоритма вычисления индекса, который зависит от особенностей F9). Таким образом, нужно знать, что N не есть произведение малых простых чисел и не похоже, что это можно узнать, если не найти фактически значение N.
Редукция глобальной пары (Е,В) по модулю р. Упомянем теперь второй способ нахождения пары, состоящей из эллиптической кривой и точки на ней. Выберем сначала раз и навсегда «глобальную» эллиптическую кривую и точку бесконечного порядка на ней. Итак, пусть E — эллиптическая кривая, определенная над полем рациональных чисел (или, для большей общности, можно было бы использовать эллиптическую кривую, определенную над некоторым числовым полем), ж В — точка бесконечного порядка на Е.
Пример 2. Точка В = (0,0) является точкой бесконечного по-
2 3
рядка на эллиптической кривой Е: у + у = х — х ж фактически порождает всю группу рациональных точек на Е.
Пример 3. Точка В = (0,0) является точкой бесконечного по-
2 3 2
рядка на Е: у -\- у = х + х и порождает всю группу рациональных точек.
Далее, мы выбираем большое простое число р (или, если наша эллиптическая кривая определена над расширением К поля Q, выбираем некоторый простой идеал в К) ж рассматриваем редукцию E ж В по модулю р. Точнее, для всех р, за исключением нескольких малых простых чисел, коэффициенты в уравнении для E имеют взаимно простые с р знаменатели и, следовательно, могут рассматриваться как коэффициенты в уравнении по модулю р. Если сделать замену переменных,
2 3
приведя полученное уравнение над Fp к виду у = х + ах + 6, то кубический многочлен в правой части не будет иметь кратных корней (за исключением нескольких малых простых р) ж дает поэтому эллиптическую кривую над Fp (которую мы будем обозначать E (mod р)). Координаты точки В, будучи также приведенными по модулю р, дают точку на эллиптической кривой E (mod р), которую мы будем обозначать В (mod р).
При использовании этого второго способа мы раз и навсегда фиксируем E ж В и за счет этого получаем много различных возможностей посредством изменения простого р.
Порядок точки В. С какой вероятностью «случайная» точка В на «случайной» эллиптической кривой оказывается порождающим
§ 2. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ
209
элементом? Или, в случае нашего второго метода выбора (E, В), какова вероятность того, что (для случайного р) точка В при редукции по модулю р дает образующий элемент кривой E (mod р)1 Этот вопрос ¦ близок к следующему вопросу о мультипликативных группах конечных полей: пусть целое Ь фиксированно, а простое р случайно; какова вероятность того, что b — образующий в F*? Вопрос изучался как для конечных полей, так и для эллиптических кривых. Более подробное изложение можно найти в работе Гупты (Gupta) и Мурти (Murty), приведенной в списке литературы.
