Открыть сервис
Главная → Блог → Edwards-curve Digital Signature Algorithm

Edwards-curve Digital Signature Algorithm

Edwards-curve Digital Signature Algorithm (EdDSA) — это криптографический алгоритм с открытым ключом, предназначенный для создания и проверки цифровых подписей. Он основан на эллиптических кривых в форме Эдвардса (Edwards curves) и является альтернативой ранее распространённому алгоритму ECDSA (Elliptic Curve Digital Signature Algorithm). EdDSA был разработан для обеспечения высокой производительности и безопасности при минимальных требованиях к вычислительным ресурсам, что делает его особенно привлекательным для встраиваемых систем, мобильных устройств и протоколов с ограниченными ресурсами. Наиболее известной реализацией EdDSA является алгоритм Ed25519, использующий кривую Curve25519.

История

Разработка EdDSA началась в 2011 году, когда криптограф Дэниел Бернштейн (Daniel J. Bernstein) и его коллеги опубликовали статью «High-speed high-security signatures». В этой работе они предложили новый подход к созданию цифровых подписей на основе эллиптических кривых в форме Эдвардса, впервые описанных Харольдом Эдвардсом в 2007 году. Основной целью было устранение недостатков ECDSA, таких как зависимость от генератора случайных чисел, уязвимости к атакам по времени и сложность реализации.

В 2014 году алгоритм Ed25519 был включён в стандарт IETF RFC 8032, что официально закрепило его как рекомендуемый механизм цифровых подписей. С тех пор EdDSA получил широкое распространение: он используется в протоколах SSH, TLS 1.3, DNSSEC, а также в таких криптовалютах, как Monero, Stellar и Cardano. В России алгоритм не входит в перечень утверждённых ГОСТ Р 34.10, но активно применяется в коммерческих и открытых проектах.

Классификация

EdDSA относится к следующим категориям криптографических алгоритмов:

  • Асимметричные алгоритмы: использует пару ключей (открытый и закрытый) для подписи и проверки.
  • Алгоритмы на эллиптических кривых: базируется на математических свойствах эллиптических кривых, а именно на кривых в форме Эдвардса.
  • Цифровые подписи: предназначен для подтверждения подлинности и целостности данных.

Устройство и принцип работы

Математическая основа

EdDSA использует эллиптические кривые в форме Эдвардса, задаваемые уравнением:

\[ x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2 \]

где \(d\) — константа, не равная 0 и 1. Для Ed25519 используется кривая с параметром \(d = -121665/121666\) над конечным полем простого порядка \(p = 2^{255} - 19\). Эта кривая обладает высокой скоростью вычислений и устойчивостью к известным атакам.

Генерация ключей

  1. Закрытый ключ: генерируется случайным образом (например, 256-битная строка для Ed25519).
  2. Открытый ключ: вычисляется как скалярное умножение закрытого ключа на базовую точку кривой \(B\). В Ed25519 открытый ключ представляет собой 256-битное значение.

Процесс подписи

Подпись сообщения \(M\) выполняется в несколько этапов:

  1. Вычисляется хеш-значение \(h\) от закрытого ключа и сообщения (например, с помощью SHA-512).
  2. Определяется детерминированный одноразовый номер \(r\) на основе хеша, что исключает необходимость в генераторе случайных чисел.
  3. Вычисляется точка \(R = r \cdot B\).
  4. Вычисляется значение \(S = r + h \cdot \text{sk} \mod L\), где \(L\) — порядок базовой точки.
  5. Подпись состоит из пары \((R, S)\).

Проверка подписи

Проверка подписи \((R, S)\) для сообщения \(M\) и открытого ключа \(PK\):

  1. Вычисляется хеш \(h\) от \(R\), \(PK\) и \(M\).
  2. Проверяется равенство: \(S \cdot B = R + h \cdot PK\).
  3. Если равенство выполняется, подпись считается действительной.

Характеристики

Преимущества

  • Высокая производительность: EdDSA значительно быстрее ECDSA и RSA при аналогичном уровне безопасности. Например, проверка подписи Ed25519 занимает около 0,1 миллисекунды на современном процессоре.
  • Детерминированность: подпись не зависит от случайных чисел, что исключает риск утечки ключа из-за плохого генератора случайных чисел.
  • Устойчивость к атакам по времени: реализация алгоритма не содержит условных переходов, зависящих от секретных данных.
  • Компактность: размер подписи составляет 64 байта для Ed25519, а открытый ключ — 32 байта.

Недостатки

  • Ограниченная гибкость: EdDSA использует фиксированные кривые, что может быть неудобно для некоторых специфических применений.
  • Сложность реализации: хотя алгоритм проще ECDSA, его корректная реализация требует глубоких знаний криптографии.
  • Совместимость: не все старые системы поддерживают EdDSA, что требует обновления программного обеспечения.

Применение

EdDSA используется в различных областях, где требуется безопасная и быстрая цифровая подпись:

Примеры реализации

Ed25519

Наиболее распространённая реализация EdDSA, использующая кривую Curve25519. Она обеспечивает 128-битный уровень безопасности и широко поддерживается в библиотеках:

  • libsodium (популярная криптографическая библиотека)
  • OpenSSL (начиная с версии 1.1.1)
  • Bouncy Castle (для Java и C#)
  • NaCl (оригинальная реализация Бернштейна)

Ed448

Менее распространённая реализация, использующая кривую Curve448, которая обеспечивает 224-битный уровень безопасности. Описана в том же RFC 8032 и используется в тех же протоколах, но реже из-за большего размера ключей и подписей.

Интересные факты

  • Название «Ed25519» происходит от комбинации «Edwards curve» и «25519» — порядка поля \(2^{255} - 19\).
  • Алгоритм был разработан с учётом требований к защите от атак по времени, что делает его одним из самых безопасных для использования в реальных системах.
  • В 2019 году Ed25519 был включён в стандарт FIPS 186-5 (Draft), что может привести к более широкому принятию в государственных системах США.
  • В России алгоритм не входит в утверждённые государственные стандарты, но его использование не запрещено и допускается в коммерческих проектах.

Критика

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

Источники

  • RFC 8032 — Edwards-Curve Digital Signature Algorithm (EdDSA)
  • Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang. «High-speed high-security signatures» (2011)
  • Документация библиотеки libsodium
  • Стандарт FIPS 186-5 (Draft)

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы