ECDSA

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Особенности[править | править код]

Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой. В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа, не существует субэкспоненциального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривые[1].

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

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

Алгоритм ECDSA в 1999 г. был принят как стандарт ANSI, в 2000 г. — как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO. Несмотря на то, что стандарты ЭЦП созданы совсем недавно и находятся на этапе совершенствования, одним из наиболее перспективных из них на сегодняшний день является ANSI X9.62 ECDSA от 1999 — DSA для эллиптических кривых[источник не указан 2285 дней].

Выбор параметров[править | править код]

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

Параметры алгоритма[править | править код]

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

Генерирование ключей ECDSA[править | править код]

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

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

  1. Выбирает случайное или псевдослучайное целое число из интервала .
  2. Вычисляет произведение (кратное) = ·.

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

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

Вычисление цифровой подписи[править | править код]

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

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

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

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

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

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

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

Для подтверждения публичного ключа Q нужно проделать следующее ( здесь обозначает бесконечно удалённую точку):

  1. Проверить, что не равно и координаты верны;
  2. Проверить, что лежит на кривой;
  3. Проверить, что ;

ECDSA согласно стандарту ANSI X9.62[править | править код]

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

Требования к эллиптической кривой[править | править код]

Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой делилось на достаточно большое простое число . Стандарт ANSI X9.62 требует . Уравнение эллиптической кривой строится специфическим образом, используя случайные/псевдослучайные коэффициенты.

Главными параметрами при построении эллиптической кривой являются:

  1. размерность поля , где является простым числом;
  2. два элемента поля  — и , определенные уравнением эллиптической кривой , где имеет вид:
    ,
    где , , и + 0 .
  3. два элемента поля  — и , которые определяют конечную точку  — генератор группы
  4. порядок точки , где и > 4
  5. сомножитель = #/, где обозначение # означает порядок группы точек эллиптической кривой .

Генерация главных параметров[править | править код]

Один из способов генерирования криптографически надежных параметров заключается в следующем:

  1. Выбираем коэффициенты и специфическим образом используя в вычислениях случайные/псевдослучайные числа. Пусть  — эллиптическая кривая — ;
  2. Вычисляем ;
  3. Проверяем, что имеет делитель, который является большим простым числом и . Если нет, то нужно вернуться на шаг 1.
  4. Проверяем, что не делит для каждого , . Если нет, то нужно вернуться на шаг 1;
  5. Проверяем, что . Если нет, то нужно вернуть на шаг 1;
  6. Берем случайную точку и положить . Повторяем до тех пор пока .

В 1985 г. Скооф (Schoof) представил алгоритм, работающий за полиномиальное время, для подсчета , число точек эллиптической кривой определенная над полем (p — нечетное простое число). Алгоритм Скоофа является достаточно не эффективным на практике для значений , которые действительно представляют интерес, то есть . В последние несколько лет было проделано много работы по улучшению и ускорению алгоритма Скоофа, сейчас он называется SEA (Schoof-Elkies-Atkin) алгоритм. С такими улучшениями криптографически пригодные эллиптические кривые, определенные над полями, чьи порядки более, чем , могут быть сгенерированы за несколько часов на рабочих станциях.

Преимущества ECDSA перед DSA[править | править код]

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

Практическая реализация[править | править код]

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

Примечания[править | править код]

  1. Коржев В. Цифровая подпись. Эллиптические кривые. «Открытые системы» (8 августа 2002). Дата обращения: 16 ноября 2008.
  2. D. Brown. Generic groups, collision resistance, and ECDSA. «Codes and Cryptography» (26 февраля 2002). Дата обращения: 27 ноября 2008. Архивировано 27 февраля 2012 года.

Ссылки[править | править код]