ЭдДСА

ЭдДСА
Общий
Дизайнеры	Дэниел Дж. Бернштейн , Нильс Дуиф, Таня Ланге , Питер Швабе, Бо-Инь Ян и др.
Впервые опубликовано	26 сентября 2011 г. (12 лет назад)
Деталь
Структура	Криптография с эллиптической кривой

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

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

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

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

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

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

В схеме подписи EdDSA

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

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

Закрытый ключ: Закрытый ключ EdDSA — это $b$ -битовая строка $k$ который следует выбирать равномерно случайным образом. Соответствующий открытый ключ $A=sB$ , где $s=H_{0,\dots ,b-1}(k)$ является наименее значимым $b$ кусочки $H(k)$ интерпретируется как целое число в Little-endian .
Подписание: Подпись в сообщении $M$ детерминированно вычисляется как $(R,S),$ где $R=rB$ для $r=H(H_{b,\dots ,2b-1}(k)\parallel M)$ , и $S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.$ Это удовлетворяет уравнению проверки

${\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] где

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

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

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

Кривая $E(\mathbb {F} _{q})$ кривой бирационально эквивалентна Монтгомери , известной как Curve25519 . Эквивалентность ^[2]^[7] $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 детерминированно выбирает одноразовый номер как хэш части закрытого ключа и сообщения. Таким образом, как только закрытый ключ сгенерирован, EdDSA больше не нуждается в генераторе случайных чисел для создания подписей, и нет опасности, что сломанный генератор случайных чисел, используемый для создания подписи, раскроет закрытый ключ. ^[2]^: 8

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

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

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

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

Apple Watch и iPhone используют ключи Ed25519 для IKEv2. взаимной аутентификации ^[22]
Ботан
Крипто++
CryptoNote Криптовалютный протокол
Dropbear SSH ^[23]
I2Pd реализация EdDSA ^[24]
Комплект разработки Java 15
Libgcrypt
Минивывеска ^[25] и Minisign Разное ^[26] для MacOS
NaCl / либнатрий ^[27]
ОпенSSL 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]

Ссылки

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

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

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

[RFC8032-1] Jump up to: Перейти обратно: ^а ^б ^с ^д Йозефссон, С.; Люсваара, И. (январь 2017 г.). Алгоритм цифровой подписи Эдвардса-Кривой (EdDSA) . ИРФТ . дои : 10.17487/RFC8032 . ISSN 2070-1721 . RFC 8032 . Проверено 11 июля 2022 г.

[DJB-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Бернштейн, Дэниел Дж .; Дуиф, Нильс; Ланге, Таня; Швабе, Питер; Бо-Инь Ян (2012). «Высокоскоростные подписи высокой безопасности» (PDF) . Журнал криптографической инженерии . 2 (2): 77–89. дои : 10.1007/s13389-012-0027-1 . S2CID 945254 .

[3] "Программное обеспечение" . 11.06.2015 . Проверено 7 октября 2016 г. Программное обеспечение Ed25519 находится в свободном доступе.

[bjlsy2015eddsamorecurves-4] Jump up to: Перейти обратно: ^а ^б Дэниел Дж. Бернштейн; Саймон Йозефссон; Таня Ланге; Питер Швабе; Бо-Инь Ян (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] Бьюкенен, Билл (12 ноября 2018 г.). «Не играйте случайно: хаки Sony PS3 и Bitcoin Crypto. Посмотрите на эти генераторы случайных чисел» . Середина . Архивировано из оригинала 30 ноября 2018 г. Проверено 11 марта 2024 г.

[FIPS_186-5-14] Jump up to: Перейти обратно: ^а ^б ^с Муди, Дастин (3 февраля 2023 г.). FIPS 186-5: Стандарт цифровой подписи (DSS) . НИСТ . doi : 10.6028/NIST.FIPS.186-5 . S2CID 256480883 . Проверено 4 марта 2023 г.

[15] Константинос Халкиас, Франсуа Гарийо и Валерия Николаенко (01.10.2020). Укрощение множества EdDSA . Конференция по исследованиям в области стандартизации безопасности (SSR 2020) . Проверено 15 февраля 2021 г.

[16] Жаклин Брендель, Кас Кремерс, Деннис Джексон и Манг Чжао (03 июля 2020 г.). Доказуемая безопасность ed25519: Теория и практика . Симпозиум IEEE по безопасности и конфиденциальности (S&P 2021) . Проверено 15 февраля 2021 г. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

[17] "ed25519-speccheck" . Гитхаб . Проверено 15 февраля 2021 г.

[18] «Изменения по сравнению с OpenSSH 6.4» . 03 января 2014 г. Проверено 7 октября 2016 г.

[19] «Что нового в GnuPG 2.1» . 14 июля 2016 г. Проверено 7 октября 2016 г.

[20] «Вещи, которые используют Ed25519» . 06.10.2016 . Проверено 7 октября 2016 г.

[21] Харрис, Б.; Велвиндрон, Л. (февраль 2020 г.). Алгоритмы открытого ключа Ed25519 и Ed448 для протокола Secure Shell (SSH) . IETF . дои : 10.17487/RFC8709 . ISSN 2070-1721 . RFC 8709 . Проверено 11 июля 2022 г.

[22] «Системная безопасность для watchOS» . Проверено 7 июня 2021 г.

[23] Мэтт Джонстон (14 ноября 2013 г.). "DROPBEAR_2013.61тест" . Архивировано из оригинала 5 августа 2019 г. Проверено 5 августа 2019 г.

[24] «Эвристические алгоритмы и распределенные вычисления» (PDF) . Эвристические алгоритмы и распределенные вычисления : 55–56. 2015. ISSN 2311-8563 . Архивировано из оригинала (PDF) 20 октября 2016 г. Проверено 7 октября 2016 г.

[25] Фрэнк Денис. «Minisign: очень простой инструмент для подписи файлов и проверки подписей» . Проверено 7 октября 2016 г.

[26] sign-misc на GitHub

[27] Фрэнк Денис (29 июня 2016 г.). "libsodium/Журнал изменений" . Гитхаб . Проверено 7 октября 2016 г.

[28] «ИЗМЕНЕНИЯ OpenSSL» . 31 июля 2019 года. Архивировано из оригинала 18 мая 2018 года . Проверено 5 августа 2019 г.

[29] «python/ed25519.py: основные подпрограммы» . 6 июля 2011 г. Проверено 7 октября 2016 г.

[30] «Программное обеспечение: альтернативные реализации» . 11.06.2015 . Проверено 7 октября 2016 г.

[31] «eBACS: Бенчмаркинг криптографических систем ECRYPT: SUPERCOP» . 10 сентября 2016 г. Проверено 7 октября 2016 г.

[32] «Криптобиблиотека безопасности Virgil для C: Library: Foundation» . Гитхаб . Проверено 4 августа 2019 г.

[33] «Встроенная библиотека SSL wolfSSL (ранее CyaSSL)» . Проверено 7 октября 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]