Контроль Разума
Advertisement

ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом для создания цифровой подписи, аналогичный по своему строению DSA, но определённый в отличие от него не над полем целых чисел, а над полем точек эллиптической кривой.

Особенности[]

Стойкость алгоритма шифрования основывается на дискретном логарифмировании в группе точек эллиптической кривой. На данный момент нет метода решения данной задачи хотя бы с субэкспоненциальной сложностью.[1]

Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению:

«Если группа эллиптической кривой может быть смоделирована основной группой и ее хэш-функция удовлетворяет определенному обоснованному предположению, то ECDSA устойчива к chosen-message атаке с существующей фальсификацией.»[2]

Несмотря на то, что стандарты ЭЦП созданы совсем недавно и находятся на этапе совершенствования, одним наиболее перспективных из них является ANSI X.9-62 ECDSA от 1999 — DSA для эллиптических кривых, ГОСТ Р 34.10-2001.

Выбор параметров[]

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

Параметры алгоритма[]

  1. Выбор хэш-функции . Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в число.
  2. Выбор большого простого числа  — порядок одной из циклических подгрупп группы точек эллиптической кривой — размерность которого в битах совпадает с размерностью в битах значений хэш-функции .
  3. Выбор простого числа , такого, что делится на .

Генерирование ключей ECDSA[]

Для простоты будем рассматривать эллиптические кривые над полем , где  — конечное простое поле. Причем, если необходимо, конструкцию можно легко адаптировать для эллиптических кривых над другим полем.

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

  1. Выбирает случайное или псевдослучайное целое число из интервала [1,  — 1].
  2. Вычисляет произведение .

Открытым ключом пользователя А является число , а закрытым — .

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

Вычисление цифровой подписи[]

Для того, что подписать какие-либо сообщение, для которого подсчитан значение хэш-функции , причем , пользователю А должен сделать следующее:

  1. Выбрать случайное целое число в интервале [1,  — 1].
  2. Вычислить и положить в , где получается из целого числа между и приведением по модулю . Замечание: если , то уравнение подписи не зависит от секретного ключа , следовательно, не подходит в качестве значения для . Значит, в случае необходимо вернуться к шагу 1.
  3. Вычислить и положить .

Замечание: если , то значение не существует. Значит, в случае необходимо вернуться к шагу 1.

Подписью для сообщения является пара целых чисел .

Проверка цифровой подписи[]

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

  1. Получить подтвержденную копию открытого ключа пользователя А;
  2. Проверить, что числа и являются целыми числами из интервала [1,  — 1], и вычислить значение хеш-функции от сообщения;
  3. Вычислить и ;
  4. Вычислить , и относительно , как целого числа между и , положить ;
  5. Принять подпись, если и только если .

Заметим, что, если пользователь А вычислил свою подпись правильно, то , так как , и поэтому .

Преимущества ECDSA над DSA[]

ECDSA является очень привлекательным алгоритмом для реализации ЭЦП. Самым важным преимуществом ECDSA является возможность его работы на значительно меньших полях . Как, в общем, с криптографией эллиптической кривой, предполагается, что битовый размер открытого ключа, который будет необходим для ESDSA, равен двойному размеру секретного ключа в битах. Для сравнения, при уровне безопасности в 80 бит получаем, то есть атакующему необходимо примерно 2^80 версий подписи для нахождения секретного ключа. При этом размер открытого ключа DSA равен, по крайней мере, 1024 бит, когда как для открытого ключа ECDSA — 160 бит. С другой стороны размер подписи одинаков и для DSA, и для ECDSA: 4t бит, где t — уровень безопасности, измеренный в битах, то есть — примерно 320 бит для уровня безопасности в 80 бит.

Практическая реализация[]

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

Существуют отдельные компании занимающиеся распространением. Установкой и обслуживанием подобных программных пакетов. Наиболее заметным игроком в мире является компания SPYRUS, которая занимается внедрением программных продуктов данной тематики корпорации Microsoft.

Примечания[]

  1. {{ |author = Коржев В. | url = http://www.morepc.ru/security/crypt/os200207010.html | title = Цифровая подпись. Эллиптические кривые | publisher = «Открытые системы» № 7-8/2002 | datepublished = 8 августа 2002 | accessdate = 16 ноября 2008 }}
  2. D. Brown (26 февраля 2002) Generic groups, collision resistance, and ECDSA. «Codes and Cryptography».  Проверено 27 ноября 2008.

Ссылки[]

  • SPYRUS Crypto Toolbox (2001). — Программное приложения для реализации криптосистем.  Проверено 27 ноября 2008.


de:ECDSA en:Elliptic Curve DSA es:ECDSA fr:Elliptic curve digital signature algorithm

Advertisement