Криптографические системы на эллиптических кривых. – ЧАСТЬ 1

Задача вычисления дискретных логарифмов может быть сформулирована не только в конечных полях Галуа. В 1985 г. Н. Коблиц и В. Миллер независимо друг от друга пришли к идее построения криптоалгоритмов на основе алгебраических струкгур, определяемых на множестве точек эллиптической кривой [65]. Преи­мущество этих схем состоит в большей скорости выполнения шифрующих пре­образований и в обеспечении эквивалентной (по отношению к системам RSA и Диффи-Хеллмана) стойкости к криптоанализу при меньшем объеме ключа (табл. 2.12) [66]. Это связано с более высокой сложностью нахождения обрат­ной функции на эллиптической кривой, нежели сложность задачи факторизации числа и задачи целочисленного логарифмирования.

Таблица 2.12

Объем ключа для различных типов шифров с эквивалентной стойкостью

Симметричные шифры (стандарт AES)

Шифры на эллиптических кривых

Криптосистемы RSAhDH

80

163

1024

128

283

3072

192

409

7680 _

256

Л-‘. 571,-..,

4 . 15360. .. – v .,>„,.

Простейший пример построения криптосистемы на эллиптических кривых выглядит следующим образом. Пусть необходимо зашифровать сообщение М, представимое точкой на эллиптической кривой Рт (х, у).

На первом шаге выбирается простое число р ~ 2180 и параметры а и Ь для уравнения эллиптической кривой, задающие множество точек Е (а, Ь). На вто­ром шаге на кривой Ер (а, Ь) выбирается генерирующая точка G = (л,,у,). При вы­боре G важно, чтобы наименьшее п, при котором выполняется равенство wxG=0, было очень большим простым числом. Параметры криптосистемы Ер(а, Ь) и G известны всем пользователям.

Пользователь В выбирает закрытый ключ пв и вычисляет открытый ключ Рв~пв* G. Чтобы зашифровать сообщение Рт, используется открытый ключ Р8 получателя В. Пользователь А выбирает случайное целое положительное число к и вычисляет зашифрованное сообщение С , являющееся точкой на эллипти­ческой кривой:

Пользователь А зашифровал сообщение Рт, добавив к нему к * Рв. Никто не знает значения к, поэтому, хотя Рд и является открытым ключом, никто не может определить кхРв. Таким образом, криптоаналитику для восстановления сообще­ния необходимо вычислить к, зная G и k*G, что весьма нелегко сделать.

Получатель тоже не знает к, однако ему в качестве «подсказки» посылается k*G. Умножив число k*G на свой секретный ключ, адресат получит значение, добавленное отправителем к незашифрованному сообщению. Поэтому, не зная к, но имея собственный секретный ключ, получатель может восстановить ис­ходное сообщение.

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

Процедуры шифрования/дешифрования в асимметричных криптосистемах по сравнению с традиционными симметричными системами отличаются на­много большей вычислительной сложностью. Кроме того, объем криптограм­мы обычно превышает объем исходного открытого текста. Эти обстоятельства накладывают существенное ограничение на использование двухключевых криптоалгоритмов в системах передачи информации реального времени. По этой причине их обычно применяют для реализации протоколов распростра­нения ключей, используемых затем в более высокоскоростных шифрах с се­кретными ключами, и для защиты данных в приложениях, не критичных к задержке передачи.

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100