ЭдДСА

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

В криптографии с открытым ключом алгоритм цифровой подписи Эдвардса ( 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 критически зависит от выбора параметров, за исключением произвольного выбора базовой точки - например, ожидается, что ро-алгоритм Полларда для логарифмов будет приблизительно складывать кривые, прежде чем он сможет вычислить дискретный логарифм, ^[5] so должно быть достаточно большим, чтобы это было невозможно, и обычно принимается равным 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 представляет собой -битную строку , которую следует выбирать случайным образом. Соответствующий открытый ключ — , где — младшие биты интерпретируются как целое число с прямым порядком байтов. Подпись в сообщении — это где для и ${\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]}

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

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

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

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

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

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

Эд448

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

Рекомендации

1. Йозефссон, С.; Люсваара, И. (январь 2017 г.). Алгоритм цифровой подписи Эдвардса-Кривой (EdDSA). ИРФТ . дои : 10.17487/RFC8032 . ISSN  2070-1721. RFC 8032 . Проверено 11 июля 2022 г.
2. Бернштейн, Дэниел Дж .; Дуиф, Нильс; Ланге, Таня; Швабе, Питер; Бо-Инь Ян (2012). «Высокоскоростные подписи высокой безопасности» (PDF) . Журнал криптографической инженерии . 2 (2): 77–89. дои : 10.1007/s13389-012-0027-1 . S2CID  945254.
3. «Программное обеспечение». 11.06.2015 . Проверено 7 октября 2016 г. Программное обеспечение Ed25519 находится в свободном доступе.
4. Дэниел Дж. Бернштейн; Саймон Йозефссон; Таня Ланге; Питер Швабе; Бо-Инь Ян (4 июля 2015 г.). EdDSA для получения дополнительных кривых (PDF) (Технический отчет) . Проверено 14 ноября 2016 г.
5. Дэниел Дж. Бернштейн; Таня Ланге; Питер Швабе (01 января 2011 г.). О правильном использовании карты отрицания в методе Ро Полларда (Технический отчет). Электронный архив криптологии IACR. 2011/003 . Проверено 14 ноября 2016 г.
6. Бернштейн, Дэниел Дж.; Ланге, Таня. «ECDLP Security: Ро». SafeCurves: выбор безопасных кривых для криптографии с эллиптическими кривыми . Проверено 16 ноября 2016 г.
7. Бернштейн, Дэниел Дж .; Ланге, Таня (2007). Куросава, Каору (ред.). Более быстрое сложение и удвоение на эллиптических кривых. Достижения в криптологии — ASIACRYPT. Конспекты лекций по информатике. Том. 4833. Берлин: Шпрингер. стр. 29–50. дои : 10.1007/978-3-540-76900-2_3 . ISBN 978-3-540-76899-9. МР  2565722.
8. Бернштейн, Дэниел Дж. (22 января 2017 г.). «Ed25519: высокоскоростные подписи с высоким уровнем безопасности» . Проверено 27 сентября 2019 г. Эта система имеет цель безопасности 2^128; взлом его аналогичен взлому NIST P-256, RSA с ~3000-битными ключами, сильными 128-битными блочными шифрами и т. д.
9. Бернштейн, Дэниел Дж. (22 января 2017 г.). «Ed25519: высокоскоростные подписи с высоким уровнем безопасности» . Проверено 01 июня 2020 г. Сигнатуры умещаются в 64 байта. […] Открытые ключи занимают всего 32 байта.
10. Джонстон, Кейси (30 декабря 2010 г.). «PS3 взломана из-за плохой реализации криптографии» . Арс Техника . Проверено 15 ноября 2016 г.
11. Fail0verflow (29 декабря 2010 г.). Взлом консоли 2010: PS3 Epic Fail (PDF) . Конгресс Хаос-коммуникаций . Архивировано из оригинала (PDF) 26 октября 2018 г. Проверено 15 ноября 2016 г.{{cite conference}}: CS1 maint: числовые имена: список авторов ( ссылка )
12. «27-й Конгресс Chaos Communication: Взлом консолей 2010: Эпический провал PS3» (PDF) . Проверено 4 августа 2019 г.
13. Муди, Дастин (3 февраля 2023 г.). «FIPS 186-5: Стандарт цифровой подписи (DSS)». НИСТ . doi : 10.6028/NIST.FIPS.186-5. S2CID  256480883 . Проверено 4 марта 2023 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
14. Константинос Халкиас, Франсуа Гарийо и Валерия Николаенко (01.10.2020). Укрощение множества EdDSA. Конференция по исследованиям в области стандартизации безопасности (SSR 2020) . Проверено 15 февраля 2021 г.
15. Жаклин Брендель, Кас Кремерс, Деннис Джексон и Манг Чжао (03 июля 2020 г.). Доказуемая безопасность ed25519: Теория и практика. Симпозиум IEEE по безопасности и конфиденциальности (S&P 2021) . Проверено 15 февраля 2021 г.{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
16. "ed25519-speccheck" . Гитхаб . Проверено 15 февраля 2021 г.
17. «Изменения по сравнению с OpenSSH 6.4» . 03 января 2014 г. Проверено 7 октября 2016 г.
18. «Что нового в GnuPG 2.1» . 14 июля 2016 г. Проверено 7 октября 2016 г.
19. «Вещи, которые используют Ed25519» . 06.10.2016 . Проверено 7 октября 2016 г.
20. Харрис, Б.; Велвиндрон, Л. (февраль 2020 г.). Алгоритмы открытых ключей Ed25519 и Ed448 для протокола Secure Shell (SSH). IETF . дои : 10.17487/RFC8709 . ISSN  2070-1721. RFC 8709 . Проверено 11 июля 2022 г.
21. «Системная безопасность для watchOS» . Проверено 7 июня 2021 г.
22. Мэтт Джонстон (14 ноября 2013 г.). «DROPBEAR_2013.61тест». Архивировано из оригинала 5 августа 2019 г. Проверено 5 августа 2019 г.
23. «Эвристические алгоритмы и распределенные вычисления» (PDF) . Эвристические алгоритмы и распределенные вычисления : 55–56. 2015. ISSN  2311-8563. Архивировано из оригинала (PDF) 20 октября 2016 г. Проверено 7 октября 2016 г.
24. Фрэнк Денис. «Minisign: очень простой инструмент для подписи файлов и проверки подписей» . Проверено 7 октября 2016 г.
25. minisign-misc на GitHub
26. Фрэнк Денис (29 июня 2016 г.). "libsodium/Журнал изменений". Гитхаб . Проверено 7 октября 2016 г.
27. «ИЗМЕНЕНИЯ OpenSSL» . 31 июля 2019 года. Архивировано из оригинала 18 мая 2018 года . Проверено 5 августа 2019 г.
28. «python/ed25519.py: основные подпрограммы». 6 июля 2011 г. Проверено 7 октября 2016 г.
29. «Программное обеспечение: альтернативные реализации». 11.06.2015 . Проверено 7 октября 2016 г.
30. «eBACS: Сравнительный анализ криптографических систем ECRYPT: SUPERCOP» . 10 сентября 2016 г. Проверено 7 октября 2016 г.
31. "Криптобиблиотека безопасности Virgil для C: Library: Foundation" . Гитхаб . Проверено 4 августа 2019 г.
32. «Встроенная библиотека SSL wolfSSL (ранее CyaSSL)» . Проверено 7 октября 2016 г.

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

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