EdDSA

Схема цифровой подписи

В криптографии с открытым ключом алгоритм цифровой подписи на основе кривой Эдвардса ( EdDSA ) представляет собой схему цифровой подписи , использующую вариант подписи Шнорра на основе скрученных кривых Эдвардса . ^[1] Он разработан так, чтобы быть быстрее существующих схем цифровой подписи, не жертвуя безопасностью. Он был разработан командой, в которую входили Дэниел Дж. Бернстайн , Нильс Дуйф, Таня Ланге , Питер Швабе и Бо-Инь Янг. ^[2] Эталонная реализация — это программное обеспечение, находящееся в открытом доступе . ^[3]

Краткое содержание

Ниже приведено упрощенное описание EdDSA, в котором не учитываются детали кодирования целых чисел и точек кривой в виде битовых строк; полные сведения см. в статьях и RFC. ^{[4] [2] [1]}

Схема подписи EdDSA — это выбор: ^{[4] : 1–2  [2] : 5–6  [1] : 5–7}

• конечного поля над нечетной простой степенью ; ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$
• эллиптической кривой , над которой группа -рациональных точек имеет порядок , где - большое простое число и называется кофактором; ${\displaystyle E}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$ ${\displaystyle \ell }$ ${\displaystyle 2^{c}}$
• базовой точки с порядком ; и ${\displaystyle B\in E(\mathbb {F} _{q})}$ ${\displaystyle \ell }$
• криптографической хеш-функции с -битными выходами, где так, что элементы и точки кривой в могут быть представлены строками битов. ${\displaystyle H}$ ${\displaystyle 2b}$ ${\displaystyle 2^{b-1}>q}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle b}$

Эти параметры являются общими для всех пользователей схемы подписи EdDSA. Безопасность схемы подписи EdDSA критически зависит от выбора параметров, за исключением произвольного выбора базовой точки — например, ожидается , что алгоритм Полларда rho для логарифмов будет приблизительно выполнять сложения кривых, прежде чем он сможет вычислить дискретный логарифм, ^[5] поэтому должен быть достаточно большим, чтобы это было неосуществимо, и обычно принимается превышающим 2 ²⁰⁰ . ^[6] Выбор ограничен выбором , поскольку по теореме Хассе , не может отличаться от более чем на . Хеш-функция обычно моделируется как случайный оракул в формальном анализе безопасности EdDSA. ${\displaystyle {\sqrt {\ell \pi /4}}}$ ${\displaystyle \ell }$ ${\displaystyle \ell }$ ${\displaystyle q}$ ${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$ ${\displaystyle q+1}$ ${\displaystyle 2{\sqrt {q}}}$ ${\displaystyle H}$

В рамках схемы подписи EdDSA

Открытый ключ

Открытый ключ EdDSA представляет собой точку кривой , закодированную в битах. ${\displaystyle A\in E(\mathbb {F} _{q})}$ ${\displaystyle b}$

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

Подпись EdDSA на сообщении с помощью открытого ключа представляет собой закодированную в битах пару из точки кривой и целого числа, удовлетворяющую следующему уравнению проверки, где обозначает конкатенацию : ${\displaystyle M}$ ${\displaystyle A}$ ${\displaystyle (R,S)}$ ${\displaystyle 2b}$ ${\displaystyle R\in E(\mathbb {F} _{q})}$ ${\displaystyle 0<S<\ell }$ ${\displaystyle \parallel }$

$${\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A.}$$

Закрытый ключ

Закрытый ключ EdDSA — это -битная строка , которая должна быть выбрана равномерно случайным образом. Соответствующий открытый ключ — это , где — наименее значимые биты интерпретируются как целое число в little-endian . ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle A=sB}$ ${\displaystyle s=H_{0,\dots ,b-1}(k)}$ ${\displaystyle b}$ ${\displaystyle H(k)}$

Подписание

Подпись сообщения детерминированно вычисляется как где для , и Это удовлетворяет уравнению проверки ${\displaystyle M}$ ${\displaystyle (R,S),}$ ${\displaystyle R=rB}$ ${\displaystyle r=H(H_{b,\dots ,2b-1}(k)\parallel M)}$ $${\displaystyle S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.}$$

$${\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}}$$

Эд25519

Ed25519 — это схема подписи EdDSA, использующая SHA-512 (SHA-2) и Curve25519 ^[2] , где

• ${\displaystyle q=2^{255}-19,}$
• ${\displaystyle E/\mathbb {F} _{q}}$это скрученная кривая Эдвардса

$${\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}$$

• ${\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}$и ${\displaystyle c=3}$
• ${\displaystyle B}$является уникальной точкой, координата которой находится в и чья координата положительна. «положительная» определяется в терминах битового кодирования: ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle y}$ ${\displaystyle 4/5}$ ${\displaystyle x}$
  
  • «положительные» координаты — четные координаты (младший бит очищен)
  • «Отрицательные» координаты — нечетные координаты (установлен младший значащий бит)
• ${\displaystyle H}$это SHA-512 , с . ${\displaystyle b=256}$

Кривая бирационально эквивалентна кривой Монтгомери , известной как Curve25519 . Эквивалентность ^{[2] [7]} ${\displaystyle E/\mathbb {F} _{q}}$ $${\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}$$

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

Первоначальная команда оптимизировала Ed25519 для семейства процессоров x86-64 Nehalem / Westmere . Проверка может выполняться пакетами по 64 подписи для еще большей пропускной способности. Ed25519 предназначен для обеспечения устойчивости к атакам, сопоставимой с качественными 128-битными симметричными шифрами . ^[8]

Длина открытых ключей составляет 256 бит, а длина подписей — 512 бит. ^[9]

Безопасное кодирование

Ed25519 разработан для того, чтобы избежать реализаций, использующих условия ветвления или индексы массива, зависящие от секретных данных, ^{[2] : 2  [1] : 40,} чтобы смягчить атаки по сторонним каналам .

Как и в других схемах подписи на основе дискретного журнала, EdDSA использует секретное значение, называемое одноразовым номером , уникальным для каждой подписи. В схемах подписи DSA и ECDSA этот одноразовый номер традиционно генерируется случайным образом для каждой подписи, и если генератор случайных чисел когда-либо сломается и будет предсказуемым при создании подписи, подпись может привести к утечке закрытого ключа, как это произошло с ключом подписи обновления прошивки Sony PlayStation 3. ^{[10] [11] [12] [13]}

В отличие от этого, EdDSA выбирает nonce детерминированно как хэш части закрытого ключа и сообщения. Таким образом, как только закрытый ключ сгенерирован, EdDSA больше не нуждается в генераторе случайных чисел для создания подписей, и нет опасности, что сломанный генератор случайных чисел, используемый для создания подписи, раскроет закрытый ключ. ^{[2] : 8}

Несоответствия стандартизации и внедрения

Обратите внимание, что существуют две попытки стандартизации EdDSA: одна от IETF, информационный RFC  8032, и одна от NIST как часть FIPS 186-5. ^[14] Различия между стандартами были проанализированы, ^{[15] [16]} и доступны тестовые векторы. ^[17]

Программное обеспечение

Известные применения Ed25519 включают OpenSSH , ^[18] GnuPG ^[19] и различные альтернативы, а также инструмент signify от OpenBSD . ^[20] Использование Ed25519 (и Ed448) в протоколе SSH было стандартизировано. ^[21] В 2023 году окончательная версия стандарта FIPS 186-5 включала детерминированный Ed25519 в качестве утвержденной схемы подписи. ^[14]

• Apple Watch и iPhone используют ключи Ed25519 для взаимной аутентификации IKEv2 ^[22]
• Ботан
• Крипто++
• Криптовалютный протокол CryptoNote
• Dropbear SSH ^[23]
• Реализация EdDSA в I2Pd ^[24]
• Комплект разработчика Java 15
• Libgcrypt
• Minisign ^[25] и Minisign Miscellanea ^[26] для macOS
• NaCl / либнатрий ^[27]
• OpenSSL 1.1.1 ^[28]
• Python — медленная, но лаконичная альтернативная реализация, ^[29] не включает защиту от атак по сторонним каналам ^[30]
• Эталонная реализация Supercop ^[31] ( язык C со встроенным ассемблером )
• Virgil PKI по умолчанию использует ключи Ed25519 ^[32]
• волкSSL ^[33]

Эд448

Ed448 — это схема подписи EdDSA с использованием SHAKE256 и Curve448, определенная в RFC  8032. Она также была одобрена в окончательной версии стандарта FIPS 186-5. ^[14]

Ссылки

1. Josefsson, S.; Liusvaara, I. (январь 2017 г.). Алгоритм цифровой подписи Edwards-Curve (EdDSA). IRTF . doi : 10.17487/RFC8032 . ISSN  2070-1721. RFC 8032 . Получено 11 июля 2022 г. .
2. Бернстайн, Дэниел Дж .; Дуйф, Нильс; Ланге, Таня; Швабе, Питер; Бо-Инь Ян (2012). «Высокоскоростные высоконадежные подписи» (PDF) . Журнал криптографической инженерии . 2 (2): 77–89. doi : 10.1007/s13389-012-0027-1 . S2CID  945254.
3. "Программное обеспечение". 2015-06-11 . Получено 2016-10-07 . Программное обеспечение Ed25519 находится в общественном достоянии.
4. Дэниел Дж. Бернштейн; Саймон Йозефссон; Таня Ланге; Питер Швабе; Бо-Инь Ян (4 июля 2015 г.). EdDSA для получения дополнительных кривых (PDF) (Технический отчет) . Проверено 14 ноября 2016 г.
5. Daniel J. Bernstein; Tanja Lange; Peter Schwabe (2011-01-01). О правильном использовании карты отрицания в методе Полларда rho (технический отчет). Архив IACR Cryptology ePrint. 2011/003 . Получено 2016-11-14 .
6. Бернстайн, Дэниел Дж.; Ланге, Таня. "Безопасность ECDLP: Rho". SafeCurves: выбор безопасных кривых для криптографии на основе эллиптических кривых . Получено 16.11.2016 .
7. Бернстайн, Дэниел Дж .; Ланге, Таня (2007). Куросава, Каору (ред.). Более быстрое сложение и удвоение на эллиптических кривых. Достижения в криптологии — ASIACRYPT. Конспект лекций по информатике. Том 4833. Берлин: Springer. С. 29–50. doi : 10.1007/978-3-540-76900-2_3 . ISBN 978-3-540-76899-9. МР  2565722.
8. Бернстайн, Дэниел Дж. (2017-01-22). "Ed25519: высокоскоростные высоконадежные подписи" . Получено 2019-09-27 . Эта система имеет целевой уровень безопасности 2^128; ее взлом имеет такую ​​же сложность, как взлом NIST P-256, RSA с ключами длиной ~3000 бит, надежные 128-битные блочные шифры и т. д.
9. Бернстайн, Дэниел Дж. (2017-01-22). "Ed25519: высокоскоростные высоконадежные подписи" . Получено 2020-06-01 . Подписи умещаются в 64 байта. […] Открытые ключи занимают всего 32 байта.
10. Джонстон, Кейси (2010-12-30). "PS3 взломана через плохую реализацию криптографии". Ars Technica . Получено 2016-11-15 .
11. fail0verflow (29.12.2010). Взлом консолей 2010: эпический провал PS3 (PDF) . Chaos Communication Congress . Архивировано из оригинала (PDF) 26.10.2018 . Получено 15.11.2016 .{{cite conference}}: CS1 maint: numeric names: authors list (link)
12. "27-й конгресс Chaos Communication: Взлом консолей 2010: эпический провал PS3" (PDF) . Получено 04.08.2019 .
13. Бьюкенен, Билл (2018-11-12). «Не играем случайно: взломы Sony PS3 и Bitcoin Crypto. Следите за генераторами случайных чисел». Medium . Архивировано из оригинала 2018-11-30 . Получено 2024-03-11 .
14. Муди, Дастин (2023-02-03). FIPS 186-5: Стандарт цифровой подписи (DSS). NIST . doi :10.6028/NIST.FIPS.186-5. S2CID  256480883 . Получено 2023-03-04 .
15. Константинос Халкиас, Франсуа Гарийо и Валерия Николаенко (2020-10-01). Укрощение множества EdDSA. Исследовательская конференция по стандартизации безопасности (SSR 2020) . Получено 2021-02-15 .
16. Жаклин Брендель, Кас Кремерс, Деннис Джексон и Манг Чжао (2020-07-03). Доказуемая безопасность ed25519: теория и практика. Симпозиум IEEE по безопасности и конфиденциальности (S&P 2021) . Получено 15 февраля 2021 г.{{cite conference}}: CS1 maint: multiple names: authors list (link)
17. "ed25519-speccheck". GitHub . Получено 2021-02-15 .
18. "Изменения с OpenSSH 6.4". 2014-01-03 . Получено 2016-10-07 .
19. "Что нового в GnuPG 2.1". 2016-07-14 . Получено 2016-10-07 .
20. "Вещи, которые используют Ed25519". 2016-10-06 . Получено 2016-10-07 .
21. Harris, B.; Velvindron, L. (февраль 2020 г.). Ed25519 и Ed448 Алгоритмы открытого ключа для протокола Secure Shell (SSH). IETF . doi : 10.17487/RFC8709 . ISSN  2070-1721. RFC 8709 . Получено 11 июля 2022 г. .
22. "Системная безопасность для watchOS" . Получено 2021-06-07 .
23. Мэтт Джонстон (2013-11-14). "DROPBEAR_2013.61test". Архивировано из оригинала 2019-08-05 . Получено 2019-08-05 .
24. "Эвристические алгоритмы и распределенные вычисления" (PDF) . Эвристические алгоритмы и распределенные вычисления (на русском языке): 55–56. 2015. ISSN  2311-8563. Архивировано из оригинала (PDF) 2016-10-20 . Получено 07.10.2016 .
25. Фрэнк Денис. "Minisign: невероятно простой инструмент для подписи файлов и проверки подписей" . Получено 07.10.2016 .
26. minisign-misc на GitHub
27. Фрэнк Денис (29.06.2016). "libsodium/ChangeLog". GitHub . Получено 07.10.2016 .
28. "OpenSSL CHANGES". 31 июля 2019 г. Архивировано из оригинала 18 мая 2018 г. Получено 5 августа 2019 г.
29. "python/ed25519.py: основные подпрограммы". 2011-07-06 . Получено 2016-10-07 .
30. "Программное обеспечение: Альтернативные реализации". 2015-06-11 . Получено 2016-10-07 .
31. "eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP". 2016-09-10 . Получено 2016-10-07 .
32. "Virgil Security Crypto Library for C: Library: Foundation". GitHub . Получено 2019-08-04 .
33. "wolfSSL Embedded SSL Library (ранее CyaSSL)" . Получено 2016-10-07 .

Внешние ссылки

• Домашняя страница Ed25519