EdDSA

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

История

Разработка EdDSA связана с работами канадского криптографа Дэниела Бернстайна. В 2006 году Бернстайн совместно с Таньей Ланге и Питером Швабе представил алгоритм подписи на основе кривых Эдвардса, который был назван EdDSA. Основой для алгоритма послужили эллиптические кривые, впервые описанные в 1987 году американским математиком Гарольдом Эдвардсом, который предложил новую форму уравнения эллиптической кривой, упрощающую вычисления.

В 2011 году Бернстайн, Ланге и Швабе опубликовали формальное описание EdDSA, а также конкретную реализацию на кривой Curve25519, получившую название Ed25519. Эта реализация быстро завоевала популярность благодаря своей скорости, безопасности и простоте реализации. В 2012 году Ed25519 была включена в протокол SSH, а затем и в другие криптографические библиотеки и протоколы, такие как OpenSSH, GnuPG, TLS 1.3 и Signal.

В 2017 году Национальный институт стандартов и технологий США (NIST) начал процесс стандартизации постквантовой криптографии, в рамках которого EdDSA рассматривался как один из кандидатов. В 2020 году EdDSA был включён в стандарт NIST SP 800-186 «Рекомендации по криптографии на эллиптических кривых» как официально рекомендованный алгоритм. В России алгоритм не стандартизирован, однако его использование допускается в рамках международных протоколов и систем, не подпадающих под требования ГОСТ Р 34.10-2012.

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

EdDSA можно классифицировать по нескольким признакам:

• По типу кривой: алгоритм использует кривые в форме Эдвардса, которые являются частным случаем эллиптических кривых. Наиболее распространённые кривые — Ed25519 (на основе Curve25519) и Ed448 (на основе Curve448).
• По методу генерации подписи: EdDSA является детерминированным алгоритмом — значение подписи для одного и того же сообщения и одного и того же закрытого ключа всегда одинаково. Это отличает его от ECDSA, где используется случайное значение (nonce), что может приводить к уязвимостям при плохой генерации случайных чисел.
• По области применения: EdDSA используется в системах аутентификации, цифровых подписях, протоколах обмена ключами и блокчейн-технологиях.

Устройство и характеристики

Кривые Эдвардса

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

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

где \( d \) — константа, не равная 0 и 1. Кривые Эдвардса обладают рядом преимуществ перед кривыми в форме Вейерштрасса, используемыми в ECDSA:

• Симметрия: операции сложения точек и удвоения выполняются по одинаковым формулам, что упрощает реализацию и защищает от атак по времени.
• Высокая скорость: вычисления на кривых Эдвардса выполняются быстрее, чем на кривых Вейерштрасса, особенно при использовании специальных кривых, таких как Curve25519.
• Устойчивость к атакам: кривые Эдвардса не имеют точек с нулевой координатой, что исключает некоторые типы атак, связанные с неопределённостью операций.

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

Для работы EdDSA необходимы следующие параметры:

• Кривая: набор параметров, включающий порядок кривой, базовую точку \( B \) и константу \( d \).
• Хеш-функция: используется для вычисления хеша сообщения и генерации подписи. В Ed25519 применяется SHA-512, в Ed448 — SHAKE256.
• Закрытый ключ: случайное число, которое хранится в секрете.
• Открытый ключ: точка на кривой, вычисляемая как \( A = s \cdot B \), где \( s \) — закрытый ключ.

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

1. Генерация закрытого ключа: генерируется случайное число \( s \) длиной, равной размеру хеша (например, 256 бит для Ed25519).
2. Вычисление открытого ключа: \( A = s \cdot B \).
3. Подпись сообщения \( m \):

• Вычисляется хеш \( r = H(s, m) \), где \( H \) — хеш-функция.
• Вычисляется точка \( R = r \cdot B \).
• Вычисляется хеш \( h = H(R, A, m) \).
• Вычисляется значение \( S = r + h \cdot s \mod q \), где \( q \) — порядок кривой.
• Подпись представляет собой пару \( (R, S) \).

Процесс верификации

1. Получатель знает открытый ключ \( A \), сообщение \( m \) и подпись \( (R, S) \).
2. Вычисляется хеш \( h = H(R, A, m) \).
3. Проверяется равенство: \( S \cdot B = R + h \cdot A \).
4. Если равенство выполняется, подпись считается действительной.

Преимущества перед ECDSA

• Детерминированность: отсутствие зависимости от генератора случайных чисел исключает уязвимости, связанные с повторным использованием nonce.
• Скорость: Ed25519 работает быстрее ECDSA на кривой P-256, особенно на процессорах без аппаратного ускорения.
• Меньший размер ключей и подписей: для Ed25519 размер закрытого ключа — 32 байта, открытого — 32 байта, подписи — 64 байта. Для ECDSA на P-256 эти размеры составляют 32, 32 и 64 байта соответственно, но при этом Ed25519 обеспечивает более высокий уровень безопасности (128-битный против 128-битного, но с большим запасом).
• Устойчивость к атакам по времени: реализация EdDSA может быть выполнена таким образом, что время выполнения не зависит от входных данных.

Применение

EdDSA широко применяется в различных областях криптографии и информационной безопасности:

• Протоколы аутентификации: Ed25519 используется в протоколе SSH для аутентификации пользователей и серверов. Начиная с OpenSSH 6.5 (2014 год), поддержка Ed25519 включена по умолчанию.
• Цифровые подписи: в протоколе TLS 1.3 (RFC 8446) Ed25519 и Ed448 являются обязательными для реализации алгоритмами подписи.
• Блокчейн-технологии: EdDSA используется в криптовалютах, таких как Monero, Stellar, Cardano, а также в системе распределённых реестров Hyperledger. В Bitcoin и Ethereum используется ECDSA, но в некоторых форках (например, Bitcoin Cash) рассматривается переход на EdDSA.
• Мессенджеры и протоколы обмена сообщениями: протокол Signal, используемый в мессенджерах Signal, WhatsApp (продукт Meta, признанной экстремистской и запрещённой в РФ) и Facebook Messenger (компания Meta признана экстремистской и запрещена в РФ), применяет Ed25519 для аутентификации и обмена ключами.
• Системы управления версиями: Git поддерживает подпись коммитов с помощью Ed25519 через GnuPG.

Критика

Несмотря на преимущества, EdDSA имеет и некоторые недостатки:

• Совместимость: не все старые системы и библиотеки поддерживают EdDSA, что может потребовать обновления программного обеспечения.
• Стандартизация: в России и некоторых других странах EdDSA не включён в национальные стандарты криптографии, что ограничивает его применение в государственных информационных системах.
• Постквантовая устойчивость: как и все алгоритмы на основе эллиптических кривых, EdDSA уязвим для атак с использованием квантовых компьютеров, работающих по алгоритму Шора. В связи с этим ведутся разработки постквантовых алгоритмов подписи, таких как CRYSTALS-Dilithium и FALCON.

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

• Алгоритм Ed25519 настолько быстр, что может генерировать подписи со скоростью более 100 000 подписей в секунду на современном процессоре.
• В 2019 году в библиотеке libsodium была обнаружена уязвимость, связанная с неправильной реализацией Ed25519, которая позволяла подделывать подписи. Уязвимость была исправлена в следующей версии.
• EdDSA является одним из немногих алгоритмов, которые были рекомендованы IETF (Internet Engineering Task Force) для использования в протоколах Интернета без оговорок.

Источники

• Bernstein, D. J., Lange, T., & Schwabe, P. (2011). «EdDSA: High-speed high-security signatures». Journal of Cryptographic Engineering.
• NIST SP 800-186. «Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters».
• RFC 8032. «Edwards-Curve Digital Signature Algorithm (EdDSA)».
• Bernstein, D. J. (2006). «Curve25519: New Diffie-Hellman speed records». Public Key Cryptography — PKC 2006.
• Langley, A., & Hamburg, M. (2014). «Ed25519: high-speed high-security signatures». OpenSSH release notes.