Открыть сервис
Главная → Блог → Алгоритм Ed25519

Алгоритм Ed25519

Ed25519 — это криптографический алгоритм цифровой подписи, основанный на эллиптических кривых, разработанный Дэниелом Бернштейном, Нильсом Дюфом, Таньей Ланге, Питером Швабе и Бо-Инь Янгом. Алгоритм является реализацией схемы подписи EdDSA (Edwards-curve Digital Signature Algorithm) на эллиптической кривой Curve25519, известной как Edwards25519. Ed25519 обеспечивает высокую скорость вычислений, устойчивость к атакам по сторонним каналам и компактный размер подписи (64 байта) и открытого ключа (32 байта). Алгоритм широко применяется в системах аутентификации, защищённой передаче данных и криптовалютах.

История и разработка

Предпосылкой к созданию Ed25519 стала необходимость в криптографических алгоритмах, сочетающих высокую производительность, безопасность и устойчивость к побочным атакам. Традиционные схемы, такие как ECDSA (Elliptic Curve Digital Signature Algorithm), имели недостатки: они требовали генерации качественных случайных чисел для каждой подписи, что могло приводить к утечкам ключей при некачественном генераторе случайных чисел, и были подвержены атакам по времени выполнения.

В 2011 году группа исследователей под руководством Дэниела Бернштейна представила спецификацию Ed25519, которая стала частью более широкого семейства EdDSA. Алгоритм был опубликован в виде открытого документа и быстро привлёк внимание криптографического сообщества. В 2012 году Ed25519 был включён в библиотеку NaCl (Networking and Cryptography library), а затем стал стандартом де-факто для многих проектов, включая OpenSSH (с версии 6.5), GnuPG (с версии 2.1) и протокол Signal.

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

Ed25519 базируется на эллиптической кривой Edwards25519, которая является скрученной кривой Эдвардса (twisted Edwards curve). Кривая задаётся уравнением:

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

где \( d = -121665/121666 \) (в поле простого порядка \( p = 2^{255} - 19 \)).

Ключевые параметры

  • Поле: \( \mathbb{F}_p \), где \( p = 2^{255} - 19 \) — простое число.
  • Порядок кривой: \( 8 \cdot L \), где \( L = 2^{252} + 27742317777372353535851937790883648493 \) — простое число.
  • Базовая точка: \( B \) — точка на кривой с координатами \( (15112221349535890701246040893115142247711809802394787781536049995508555584247, 46316835694926478169428394003475163141307993866256225615783033603165251855960) \).
  • Размер ключа: 32 байта для закрытого ключа, 32 байта для открытого ключа.
  • Размер подписи: 64 байта (32 байта для компоненты \( R \) и 32 байта для компоненты \( S \)).

Алгоритм работы

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

  1. Закрытый ключ \( sk \) — это случайная строка из 32 байт.
  2. Хеш-функция SHA-512 применяется к \( sk \), результат разделяется на две половины:
  • Первая половина (32 байта) используется для вычисления скаляра \( a \): после очистки младших 3 бит, установки старшего бита и сброса второго старшего бита.
  • Вторая половина (32 байта) используется как секретный префикс \( prefix \) для подписи.
  1. Открытый ключ \( pk \) вычисляется как \( pk = a \cdot B \), где \( B \) — базовая точка кривой.

Создание подписи

Для сообщения \( M \) процесс подписи включает:

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

Верификация подписи

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

  1. Проверяет, что \( S \) находится в диапазоне \( [0, L) \).
  2. Вычисляет \( h = \text{SHA-512}(R || pk || M) \), редуцированное по модулю \( L \).
  3. Проверяет уравнение: \( S \cdot B = R + h \cdot pk \).
  4. Если равенство выполняется, подпись считается действительной.

Преимущества и особенности

Безопасность

  • Стойкость к коллизиям: Использование SHA-512 обеспечивает высокую криптографическую стойкость.
  • Детерминированность: Подпись не зависит от генератора случайных чисел, что исключает утечки из-за слабого источника энтропии.
  • Устойчивость к атакам по времени: Алгоритм спроектирован так, чтобы время выполнения не зависело от секретных данных.
  • Защита от атак с использованием побочных каналов: Операции с фиксированным временем выполнения и отсутствие ветвлений на основе секретных значений.

Производительность

  • Скорость: Ed25519 значительно быстрее ECDSA на кривой P-256 (secp256r1) и RSA при генерации ключей и верификации подписей.
  • Компактность: Размер ключа и подписи в 2-4 раза меньше, чем у RSA-2048.
  • Энергоэффективность: Низкое потребление ресурсов делает алгоритм подходящим для встраиваемых систем и мобильных устройств.

Применение

Криптовалюты

Ed25519 широко используется в блокчейн-проектах. Например, в криптовалюте Monero (XMR) алгоритм применяется для подписи транзакций, обеспечивая анонимность и безопасность. В Cardano (ADA) Ed25519 является основой для подписи транзакций и управления адресами. В Solana (SOL) алгоритм используется для быстрой верификации транзакций, что способствует высокой пропускной способности сети.

Протоколы связи

  • SSH: OpenSSH поддерживает Ed25519 с версии 6.5 (2014 год). Ключи Ed25519 считаются стандартом для современных SSH-соединений.
  • TLS: В протоколе Transport Layer Security (TLS 1.3) Ed25519 включён в список рекомендуемых алгоритмов подписи.
  • Signal: Протокол Signal, используемый в одноимённом мессенджере, применяет Ed25519 для аутентификации и подписи ключей.

Операционные системы

  • Linux: Многие дистрибутивы, включая Ubuntu, Fedora и Arch Linux, поддерживают Ed25519 для аутентификации по SSH и подписи пакетов.
  • macOS: Система использует Ed25519 для подписи кода и аутентификации в iCloud.
  • Windows: Начиная с Windows 10, встроенная поддержка Ed25519 через API Cryptography Next Generation (CNG).

Библиотеки и инструменты

  • Libsodium: Популярная криптографическая библиотека, реализующая Ed25519 через функции crypto_sign_*.
  • OpenSSL: С версии 1.1.1 (2018 год) включает поддержку Ed25519.
  • GnuPG: С версии 2.1 (2014 год) поддерживает ключи Ed25519.

Критика и ограничения

Потенциальные уязвимости

  • Квантовая уязвимость: Как и все алгоритмы на эллиптических кривых, Ed25519 не устойчив к атакам с использованием квантовых компьютеров. Разработка постквантовых алгоритмов (например, на основе решёток) ведётся, но Ed25519 остаётся стандартом для классических вычислений.
  • Реализационные ошибки: Неправильная реализация (например, отсутствие проверки принадлежности точки кривой) может привести к уязвимостям. В 2019 году были обнаружены ошибки в некоторых реализациях, позволяющие подделывать подписи при определённых условиях.

Сравнение с альтернативами

  • ECDSA: Ed25519 превосходит ECDSA по скорости и безопасности, но ECDSA более широко распространён в старых системах.
  • RSA: RSA проигрывает Ed25519 по производительности и размеру ключей, но остаётся стандартом для сертификатов X.509.
  • Schnorr: Ed25519 является вариантом схемы Шнорра, но с детерминированными подписями и использованием кривой Edwards25519.

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

  • Название «Ed25519» происходит от комбинации «Edwards curve» и «25519» — отсылки к простому числу \( 2^{255} - 19 \), используемому в кривой Curve25519.
  • Алгоритм был разработан в рамках проекта «Twisted Edwards curves» и впервые опубликован в 2011 году на конференции SAC (Selected Areas in Cryptography).
  • Ed25519 является частью стандарта IETF RFC 8032 (2017 год), который описывает схему EdDSA.
  • В 2014 году исследователи из Университета Иллинойса показали, что Ed25519 может быть реализован на микроконтроллерах с тактовой частотой 8 МГц, что делает его пригодным для IoT-устройств.

Источники

  • Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B. Y. (2012). High-speed high-security signatures. Journal of Cryptographic Engineering, 2(2), 77-89.
  • RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA). Internet Engineering Task Force (IETF), 2017.
  • Bernstein, D. J. (2006). Curve25519: New Diffie-Hellman speed records. Public Key Cryptography – PKC 2006, 207-228.
  • Langley, A. (2014). Ed25519 in OpenSSH. Imperial Violet (блог).
  • Документация библиотеки Libsodium (версия 1.0.18).

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

На главную BFOmetr →

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