ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом, использующийся для построения и проверки электронной цифровой подписи при помощи криптографии на эллиптических кривых.
Алгоритм достаточно популярен в области электронных цифровых подписей из-за сложности задачи, на которой основано вычисление закрытого ключа из открытого. ECDSA принят различными организациями в качестве стандарта. Алгоритм состоит из четырёх частей: генерация основных параметров, генерация ключевой пары, создание и проверка цифровой подписи. В общем случае, считается достаточно безопасным (для соответствующих уровней криптостойкостей), а также имеет реализации во множестве криптографических библиотек.
Эллиптические кривые в качестве математического понятия изучаются уже достаточно давно. Например, ещё у древнегреческого математика Диофанта в III веке нашей эры в труде «Арифметика» были задачи, которые сводились к нахождению рациональных точек на эллиптической кривой. Однако, их применение для реальных задач, в частности, для области криптографии, было неизвестно до конца XX века. В 1985 году Виктор Миллер и Нил Коблиц предложили использование эллиптических кривых для криптографии.
В 1991 году Национальным институтом стандартов и технологий (NIST) был разработан DSA, построенный на идее использования проблемы дискретного логарифма. Вскоре после этого NIST запросил публичные комментарии по поводу своего предложения о схемах цифровой подписи. Воодушевившись данной идеей, Скотт Ванстоун в статье «Responses to NIST’s proposal» предложил аналог алгоритму цифровой подписи, использующий криптографию на эллиптических кривых (ECDSA).
В период с 1998-2000 гг. ECDSA был принят различными организациями как стандарт (ISO 14888-3, ANSI X9.62, IEEE 1363—2000, FIPS 186-2).
Область применения ECDSA ограничивается областью применения электронной цифровой подписи. Другими словами, в тех местах, где может потребоваться проверка целостности и авторства сообщения. Например, использование в криптовалютных транзакциях (в биткойне и эфириуме) для обеспечения того, чтобы средства могли быть потрачены только своими законными владельцами.
Основными параметрами (англ. domain parameters) эллиптической кривой над конечным полем называется совокупность следующих величин:
Параметры должны быть выбраны таким образом, чтобы эллиптическая кривая, определённая над конечным полем , была устойчива ко всем известным атакам, применимым к ECDLP. Помимо этого могут быть и другие ограничения, связанные с соображениями безопасности или реализации. Как правило, основные параметры являются общими для группы сущностей, однако в некоторых приложениях (реализациях), они могут быть специфичными для каждого конкретного пользователя
Для практического применения ECDSA налагают ограничения на поля, в которых определены эллиптические кривые. Для простоты рассмотрим случай реализации алгоритмов, когда — простое конечное поле (для других полей — аналогично), тогда наше эллиптическое уравнение принимает вид .
Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой делилось на достаточно большое простое число . Стандарт ANSI X9.62 требует . Предлагается следующий алгоритм:
Ввод: Порядок поля , индикатор представления поля для , - уровень безопасности: и . Вывод: Основные параметры эллиптической кривой . |
Шаг 1. Выберите верифицировано случайным образом элементы , удовлетворяющие условию . Шаг 2. , порядок кривой можно вычислить при помощи алгоритма SEA. Шаг 3. Проверьте, что при большом простом числе . Если нет, тогда перейдите к шагу 1. Шаг 4. Проверьте, что . Если нет, тогда перейдите к шагу 1. Шаг 5. Проверьте, что . Если нет, тогда перейдите к шагу 1. Шаг 6. . Шаг 7. Выберите произвольную точку и задайте . Повторяйте, пока , где - бесконечно удалённая точка Шаг 8. Верните |
Алгоритмы верификации случайным образом дают гарантию того, что эллиптическая кривая над конечным полем была сгенерирована абсолютно случайно.
Будем рассматривать обмен сообщениями между Алисой и Бобом. Предварительно используя алгоритм генерации основных параметров, Алиса получает свои основные параметры эллиптической кривой. Используя следующую последовательность действий, Алиса сгенерирует себе открытый и закрытый ключ.
Ввод: Основные параметры эллиптической кривой . Вывод: Открытый ключ - , закрытый ключ - . |
Шаг 1. Выберите случайное или псевдослучайное целое число . Шаг 2. Вычислите координаты точки на эллиптической кривой . Шаг 3. Верните . |
Целью проверки открытого ключа является подтверждение того, что открытый ключ обладает определенными арифметическими свойствами. Успешное выполнение данного алгоритма демонстрирует, что соответствующий закрытый ключ математически существует, но не гарантирует, что кто-то не вычислил данный закрытый ключ или что заявленный владелец действительно обладает им.
Ввод: Основные параметры эллиптической кривой , открытый ключ - . Вывод: Решение о принятии или отклонении достоверности открытого ключа . |
Шаг 1. Проверьте, что . Шаг 2. Проверьте, что являются правильно представленными элементами в , т.е. целыми числами, принадлежащими . Шаг 3. Проверьте, что удовлетворяет уравнению эллиптической кривой, определяемому элементами поля . Шаг 4. Проверьте, что . Шаг 5. Если какая-либо проверка не прошла, то вернуть "Отклонить", иначе "Принять". |
Алиса, обладающая основными параметрами кривой и закрытым ключом , хочет подписать сообщение , для этого она должна сгенерировать подпись .
В дальнейшем обозначает криптографическую хэш-функцию, выходное значение которой имеют битовую длину не более (если это условие не выполняется, то выходное значение может быть усечено). Предполагается, что мы работаем с выходом функции, уже преобразованным в целое число.
Ввод: Основные параметры эллиптической кривой , закрытый ключ , сообщение . Вывод: Подпись . |
Шаг 1. Выберите случайное или псевдослучайное целое число . Шаг 2. Вычислите координаты точки . Шаг 3. Вычислите . Если , тогда перейдите к шагу 1. Шаг 4. Вычислите . Шаг 5. Вычислите . Если , тогда перейдите к шагу 1. Шаг 6. Верните . |
Чтобы проверить подпись Алисы сообщения , Боб получает аутентичную копию её основных параметров кривой и связанный с ними открытый ключ :.
Ввод: Основные параметры эллиптической кривой , открытый ключ , сообщение , подпись . Вывод: Решение о принятии или отклонении подписи. |
Шаг 1. Проверьте, что - целые числа, принадлежащие . Если какая-либо проверка не удалась, то вернуть "Отклонить". Шаг 2. Вычислите . Шаг 3. Вычислите . Шаг 4. Вычислите и . Шаг 5. Вычислите координаты точки . Шаг 6. Если , то вернуть "Отклонить". Иначе вычислить . Шаг 7. Если , то вернуть "Принять", иначе "Отклонить" |
В данном примере будут описываться только значащие вычислительные шаги в алгоритмах, считая, что все проверки могут быть сделаны без текстового описания.
1. Используя алгоритм генерации основных параметров, получим следующие значения: , эллиптическая кривая , и базовая точка с порядком .
2. Сгенерируем пару ключей в соответствии с алгоритмом генерации ключевой пары:
Шаг 1. Выбираем . Шаг 2. Вычисляем координаты точки . |
3. Алгоритмом генерации цифровой подписи подпишем сообщение, заданное в виде текста со значением хэш-функции .
Шаг 1. Выбираем . Шаг 2. Вычисляем координаты точки . Шаг 3. Вычисляем . Шаг 4. Вычисляем . |
4. Проверим достоверность подписи для сообщения с помощью алгоритма проверки цифровой подписи.
Шаг 1. Вычисляем . Шаг 2. Вычисляем и . Шаг 3. Вычисляем координаты точки . Шаг 4. Вычислим . Шаг 5. Проверяем . Принимаем подпись. |
Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению: «Если группа эллиптической кривой может быть смоделирована основной группой и её хеш-функция удовлетворяет определённому обоснованному предположению, то ECDSA устойчива к атаке на основе подобранного открытого текста с существующей фальсификацией».
Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой. В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа, не существует субэкспоненциального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривые.
Это означает, что в криптографии на эллиптических кривых можно использовать значительно меньшие параметры, чем в других системах с открытыми ключами, таких как RSA и DSA, но с эквивалентным уровнем безопасности. К примеру, битовый размер ключей: 160-битный ключ будет равносилен ключам с 1024-битным модулем в RSA и DSA при сопоставимом уровне безопасности (против известных атак). Преимущества, полученные от меньших размеров параметров (в частности, ключей), включают скорость выполнения алгоритма, эффективное использование энергии, пропускной полосы, памяти. Они особенно важны для приложений на устройствах с ограниченными возможностями, таких как смарт-карты.
Явной проблемой является отсутствие доверия к некоторым уже разработанным ранее алгоритмам. Например, NIST Special Publication 800-90, содержащая детерминированный генератор случайных битов на эллиптических кривых Dual_EC_DRBG. В самом стандарте содержится набор констант кривой, появление которых в представленном виде не объяснено, Шумоу и Фергюсон показали, что данные постоянные связаны с некоторым случайным набором чисел, работающим как бэкдор, возможно, для целей АНБ, но этому нет никаких достоверных подтверждений.
ECDSA реализован в таких криптографических библиотеках, как OpenSSL, Cryptlib, Crypto++, реализации протоколов GnuTLS, интерфейсе программирования приложений CryptoAPI. Существует и множество других программных реализаций алгоритма электронной цифровой подписи на эллиптических кривых, большинство из которых в основном сосредоточено на одном приложении, например, быстрой реализации для одного конкретного конечного поля.
Эта статья входит в число добротных статей русскоязычного раздела Википедии. |