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 для эллиптических кривых.[источник не указан 564 дня]

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

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

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

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

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

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

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

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

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

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

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

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

  1. Выбрать случайное целое число .
  2. Вычислить и положить в , где получается из целого числа между и приведением по модулю .
    Замечание: если , то уравнение подписи не зависит от секретного ключа , и следовательно, не подходит в качестве цифровой подписи. Значит, в случае необходимо вернуться к шагу 1.
  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 бит.

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

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

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

Ссылки[править | править вики-текст]