§ 2. Ключевой обмен и шифрование с использованием группы точек эллиптической кривой

Теперь опишем аналоги некоторых широко распространенных систем с открытым ключом, основанные на задаче дискретного логарифмирования на эллиптической кривой, определенной над конечным полем .

Аналог ключевого обмена Диффи–Хеллмана. Предположим, что абоненты А и Б хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего они открыто выбирают какое-либо конечное поле и какую-либо эллиптическую кривую Е над ним. Их ключ строится по случайной точке Р на этой эллиптической кривой. Если у них есть случайная точка Р, то, например, ее x-координата дает случайный элемент , который можно затем преобразовать в r-разрядное целое число в р-ричной системе счисления (где ), и это число может служить ключом в их классической криптосистеме. Они должны выбрать точку Р так, чтобы все их сообщения друг другу были открытыми и все же никто, кроме них двоих, ничего бы не знал о Р.

Абоненты (пользователи) А и Б первым делом открыто выбирают точку В Е в качестве «основания»; B играет ту же роль, что образующий q в системе Диффи–Хеллмана для конечных полей. Мы, однако, не требуем, чтобы B была образующим элементом в группе точек кривой E. Эта группа может и не быть циклической. Даже если она циклическая, можно не тратить время на проверку того, что В – образующий элемент (или даже на нахождение общего числа N точек, которое не понадобится в последующем). Нам хотелось бы, чтобы порожденная В подгруппа была большой, предпочтительно того же порядка величины, что и сама Е. Позже мы рассмотрим этот вопрос. Пока что предположим, что В – взятая открыто точка на Е весьма большого порядка (равного либо N, либо большому делителю N).

Чтобы образовать ключ, абонент А вначале случайным образом выбирает целое число 𝑎, сравнимое по порядку величины с q (которое близко к N); это число он держит в секрете. Он вычисляет 𝑎𝐵 Е и передает эту точку открыто. Абонент Б делает то же самое: он выбирает случайно b и открыто передает 𝑏𝐵 Е. Тогда используемый ими секретный ключ – это Р = 𝑎𝑏𝐵 Е. Оба пользователя могут вычислить этот ключ. Например, абонент А знает 𝑏𝐵 (точка была передана открыто) и свое собственное секретное 𝑎. Однако любая третья сторона знает лишь 𝑎𝐵 и 𝑏𝐵. Кроме решения задачи дискретного логарифмирования – нахождения 𝑎 по 𝐵 и 𝑎𝐵 (или нахождения 𝑏 по 𝐵 и 𝑏𝐵) – по-видимому, нет способа найти 𝑎𝑏𝐵, зная лишь 𝑎𝐵 и 𝑏𝐵.

Пример 16. Возьмем р = 211, (что соответствует кривой ) и B = (2, 2). Можно подсчитать, что 241B = 𝒪. Личным ключом пользователя А является а = 121, поэтому его открытым ключом будет = 121(2, 2) = (115, 48). Личным ключом пользователя Б является b = 203, поэтому его открытым ключом будет 203(2, 2) = (130, 203). Общим секретным ключом является 121(130, 203) = 203(115, 48) = (161,169).

Общий секретный ключ представляет собой пару чисел. Если этот ключ предполагается использовать в качестве сеансового ключа для традиционного шифрования, то из этой пары чисел необходимо генерировать одно подходящее значение. Можно, например, использовать просто координату 𝑥 или некоторую простую функцию от 𝑥.

Аналог системы Мэсси–Омуры. Как и в случае конечного поля, это криптосистема с открытым ключом для передачи элементов сообщения 𝑚, которые мы теперь представим точками фиксированной (и не скрываемой) эллиптической кривой Е над (q берется большим). Предполагается также, что общее число N точек на Е вычислено и не составляет секрета. Каждый пользователь системы секретно выбирает такое целое случайное число е между 1 и N, что НОД(e, N) = 1. Используя алгоритм Евклида, он находит затем обратное к числу е по модулю N, т. е. такое целое число d, что de 1(modN). Если пользователь А хочет послать пользователю Б сообщение , то он сначала посылает ему точку (индекс А указывает на пользователя А). Это ничего не говорит пользователю Б, который, не зная ни , ни , не может восстановить . Однако не придавая этому значения, он умножает ее на свое и посылает обратно пользователю А. На третьем шаге пользователь А должен частично раскрыть свое сообщение, умножив на .Так как 𝑁 = 𝒪 и = 1(modN), при этом получается точка которую пользователь А возвращает пользователю Б. Тот может теперь прочитать сообщение, умножив точку на .

Заметим, что злоумышленник может узнать , и . Если бы он умел решать задачу дискретного логарифмирования на Е, то мог бы определить по первым двум точкам, вычислить = (modN) и = .

Аналог системы Эль-Гамаля. Это другая криптосистема с открытым ключом для передачи сообщений . Как и в описанной выше системе ключевого обмена, мы исходим из несекретных данных:

а) конечного поля ;

б) определенной над ним эллиптической кривой Е;

в) точки-«основания» В на ней (знать общее число N точек на Е не нужно).

Каждый из пользователей выбирает случайное целое число 𝑎, которое держит в секрете, затем находит и делает общедоступной точку 𝑎𝐵.

Чтобы послать пользователю Б сообщение , пользователь А выбирает случайно целое число k и посылает пару точек {kB, + k В} (где В – открытый ключ пользователя Б). Чтобы прочитать сообщение, пользователь Б умножает первую точку из полученной пары на свое секретное число и вычитает результат умножения из второй точки:

+ k( В) – (kB) = .

Таким образом, пользователь А посылает замаскированное вместе с «подсказкой» k𝐵, при помощи которой можно снять «маску» k В, если знать секретное число . Злоумышленник, который умеет решать задачу дискретного логарифмирования на Е, может, конечно, найти , зная В и В.

Пример 17. Рассмотрим случай р = 751, (–1,188) (что соответствует кривой и G = (0, 376)). Предположим, что пользователь А собирается отправить пользователю Б сообщение, которое кодируется эллиптической точкой = (562,201), и что пользователь А выбирает случайное число k = 386. Открытым ключом пользователя Б является = (201,5). Мы имеем 386(0,376) = (676,558) и (562,201) + 386(201, 5) = (385, 328). Таким образом, пользователь А должен послать шифрованный текст {(676, 558), (385, 328)}.

Выбор кривой и точки. Существуют различные способы выбора эллиптической кривой и (в системах Диффи–Хеллмана и Эль-Гамаля) точки В на ней.

1. Случайный выбор (Е, В).

Взяв какое-либо большое конечное поле , можно следующим образом осуществить одновременный выбор Е и В = (x, у) Е. Будем предполагать, что характеристика р поля больше 3, так что эллиптическая кривая задана уравнением (1) из § 1 гл. 1; при q = или нетрудно сделать очевидные изменения. Выбираем сначала случайным образом три элемента из в качестве 𝑥, 𝑦, 𝑎. Далее полагаем . Убеждаемся в том, что кубический многочлен не имеет кратных корней, что равносильно проверке условия . Если это условие не выполняется, берем другую случайную тройку 𝑥, 𝑦, 𝑎. Полагаем В = (𝑥, 𝑦). Тогда В – точка на эллиптической кривой .

Число N точек кривой можно найти несколькими способами. Первый полиномиальный алгоритм для вычисления 𝑁(Е), построенный Рене Шуфом (Rene Schoof), является даже детерминированным. Он основывается на нахождении значения 𝑁(Е) по модулю l для всех простых чисел l, меньших некоторой границы. Для этого анализируется действие автоморфизма Фробениуса (отображения в р-ю степень) на точках порядка l.

В статье Шуфа оценка времени работы была фактически представлена как O( ), т. е. хотя и полиномиальной, однако быстро растущей. Вначале казалось, что алгоритм не имеет практического значения. Однако с тех пор многие пытались повысить скорость алгоритма Шуфа: Миллер (V. Miller), Элкис (N. Elkis). Бухман (J. Buchman), Мюллер (V. Muller), Менезес (A. Menezes), Чарлап (L. Charlap), Коули (R. Coley) и Роббинс (D. Robbins). Кроме того, Эткин (А. О. L. Atkin) разработал другой метод, который хотя и не гарантирует полиномиального времени работы, на практике дает весьма удовлетворительные результаты. Все эти усилия дали возможность вычислять порядок произвольной эллиптической кривой над , если q – степень простого числа, записываемая 50 или даже 100 знаками. Более подробно это обсуждается в гл. 3^*.

Следует также отметить, что хотя для реализации систем Диффи–Хеллмана или Эль-Гамаля знать N не нужно, на практике желательно быть уверенным в их надежности, которая зависит от того, имеет ли N большой простой делитель. Если N есть произведение малых простых чисел, то для решения задачи дискретного логарифмирования можно использовать метод Полига–Силвера–Хеллмана. Заметим, что метод Полига–Силвера–Хеллмана решает задачу дискретного логарифмирования в любой конечной абелевой группе (в отличие от алгоритма вычисления индекса, который зависит от особенностей ). Таким образом, нужно знать, что N не есть произведение малых простых чисел и не похоже, что это можно узнать, если не найти фактически значение N.

2. Редукция глобальной пары (Е, В) по модулю р.

Выберем сначала раз и навсегда «глобальную» эллиптическую кривую и точку бесконечного порядка на ней. Итак, пусть Е – эллиптическая кривая, определенная над полем рациональных чисел (или, для большей общности, можно было бы использовать эллиптическую кривую, определенную над некоторым числовым полем), и В – точка бесконечного порядка на Е.

Пример 18. Точка В = (0,0) является точкой бесконечного порядка на эллиптической кривой Е: и фактически порождает всю группу рациональных точек на Е.

Пример 19. Точка В = (0,0) является точкой бесконечного порядка на Е: и порождает всю группу рациональных точек.

Далее мы выбираем большое простое число р (или, если наша эллиптическая кривая определена над расширением 𝕂 поля ℚ, выбираем некоторый простой идеал в 𝕂) и рассматриваем редукцию Е и В по модулю р. Точнее, для всех р, за исключением нескольких малых простых чисел, коэффициенты в уравнении для Е имеют взаимно простые с р знаменатели и, следовательно, могут рассматриваться как коэффициенты в уравнении по модулю р. Если сделать замену переменных, приведя полученное уравнение над к виду то кубический многочлен в главной части не будет иметь кратных корней (за исключением нескольких малых простых р) и дает поэтому эллиптическую кривую над (которую мы будем обозначать Е(modp)). Координаты точки В, будучи также приведенными по модулю р, дают точку на эллиптической кривой Е(modp), которую мы будем обозначать В(modp).

При использовании этого способа мы раз и навсегда фиксируем Е и В и за счет этого получаем много различных возможностей посредством изменения простого р.

Порядок точки В. С какой вероятностью «случайная» точка В на «случайной» эллиптической кривой оказывается порождающим элементом? Или, в случае второго способа выбора (Е, В), какова вероятность того, что (для случайного р) точка В при редукции по модулю дает образующий элемент кривой Е(modp)? Этот вопрос близок к следующему вопросу о мультипликативных группах конечных полей: пусть целое b фиксировано, а простое р случайно; какова вероятность того, что b – образующий элемент в ? Вопрос изучался как для конечных полей, так и для эллиптических кривых.

Как упоминалось выше, описанные криптосистемы могут быть надежными, даже если точка В не является порождающим элементом. Фактически нужно, чтобы в циклической группе, порождаемой В, задача дискретного логарифмирования не была эффективно разрешима. Это будет так (т.е.все известные методы решения задачи дискретного логарифмирования в произвольной абелевой группе оказываются слишком медленными), если порядок B делится на очень большое простое число, скажем, имеющее порядок величины, близкий к N.

Один из способов гарантировать, что наш выбор B является надлежащим (а фактически, что B порождает эллиптическую кривую) – это взять такую эллиптическую кривую и такое конечное поле, чтобы число точек N было простым числом. Тогда всякая точка В 𝒪 будет порождающим элементом. Если использовать первый из описанных выше способов, то при фиксированном можно продолжать выбор пар (Е, В), пока не найдется такая, для которой число точек на Е есть простое число (что можно определить одним из известных тестов на простоту). Если применять второй способ, то для фиксированной глобальной эллиптической кривой Е над ℚ можно продолжать выбирать простые р, пока не найдем кривую Е(modp), число точек на которой простое. Как долго нам придется ждать? Этот вопрос аналогичен следующему вопросу о группах : является ли (р – 1)/2 простым числом, т. е. верно ли, что любой элемент, отличный от ±1, – либо порождающий, либо квадрат порождающего элемента? Ни для эллиптических кривых, ни для конечных полей вопрос пока не получил явного ответа, однако в обоих случаях предполагается, что вероятность выбора р с требующимся свойством есть O(1/ ).

Замечание. Для того чтобы Е(modp) имела простой порядок N при большом р, надо выбирать Е так, чтобы она имела тривиальное кручение, т. е. чтобы на ней не было точек конечного порядка, кроме 𝒪. В противном случае N будет делиться на порядок периодической подгруппы.

Безопасность криптографии с использованием эллиптических кривых. Безопасность, обеспечиваемая криптографическим подходом на основе эллиптических кривых, зависит от того, насколько трудной для решения оказывается задача определения k по данным kP и Р. Наиболее быстрым из известных на сегодня методов логарифмирования на эллиптической кривой является так называемый ρ-метод Полларда (Pollard). Сравним эффективность этого метода и метода разложения на простые множители с помощью решета в поле чисел общего вида (табл. 8).

Таблица 8