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

Использование эллиптических кривых в криптографических целях было Нило Коблицом и Виктором Миллером в 1985 году. С 1998 года использование эллиптических кривых для решения криптографических задач, таких, как цифровая подпись, было закреплено в стандартах США ANSI X9.62 и FIPS 186-2, а в 2001 году аналогичный стандарт, ГОСТ Р34.10-2001, был принят и в России.

Особое достоинство криптосистем на эллиптических кривых состоит в том, что по сравнению с “обычными” RSA системами, они обеспечивают существенно более высокую стойкость при равной трудоемкости или, наоборот, существенно меньшую трудоемкость при равной стойкости.

В результате тот уровень стойкости, который достигается в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реализуется при размере модуля 160 бит, что обеспечивает более простую как программную, так и аппаратную реализацию.

Эллиптические кривые.

Кривая третьего порядка , задаваемая уравнением вида:

                                          (1)

называется эллиптической кривой.

, график кривой симметричен относительно оси абсцисс. Чтобы найти точки ее пересечения с осью абсцисс, необходимо решить кубическое уравнение

                                                 (2)

Дискриминант этого уравнения равен

                                                (3)

Если  уравнение (2) имеет три различных корня  если  то (2) имеет три действительных корня  (два из которых равны); если уравнение имеет один действительный корень  и два комплексно сопряженных.

Графический вид шифрования.

 – изменение знака  

Алгоритм шифрования.

Для пользователей некоторой сети выбираются общая эллиптическая кривая  и некоторая точка , такая, что … - это различные точки, а  (точка в бесконечности) для некоторого простого числа .

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

Допустим, пользователь  хочет передать сообщение пользователю .

 делает следующее:

1. Выбирает случайное число

2. Вычисляет ;

3. Шифрует

4. Посылает  криптограмму

Пользователь  после получения

1. Вычисляет

2. Дешифрует

{ – угловой коэффициент }

Цифровая подпись.

Для сообщества пользователей выбирается общая эллиптическая кривая  и точка  на ней, такая, что … суть различные точки, и  для некоторого простого числа (длина числа  равна 256 бит).

Каждый пользователь  выбирает случайное число  (секретный ключ), , и вычисляет точку на кривой  (открытый ключ). Параметры кривой и список открытых ключей передаются всем пользователям.

Чтобы подписать сообщение, Алиса делает следующее:

1. Вычисляет значение хеш-функции сообщения ;

2. Выбирает случайно число , ;

3. Вычисляет ;

4. Вычисляет  (при  возвращается к шагу 2);

5. Вычисляет  (при возвращается к шагу 2);

6. Подписывает сообщение парой чисел .

Для проверки подписанного сообщения любой пользователь, знающий открытый ключ , делает следующее:

1. Вычисляет ;

2. Убеждается, что ;

3. Вычисляет  и ;

4. Вычисляет композицию точек на кривой  и если , отвергает подпись;

5. Если , принимает подпись, в противном случае отвергает ее.