EdDSA

В криптографических системах с открытым ключом, Edwards-curve Digital Signature Algorithm (EdDSA) — схема цифровой подписи использующая вариант схемы Шнора основанной на эллиптической кривой Эдвардса^[1].

Она спроектирована так, чтобы быть быстрее по сравнению с существующей схемой цифровой подписи без ущерба для её безопасности. Она была разработана Дэниелом Дж. Бернштейном, Нильсом Дуйфом, Таней Ланге, Питером Швабе и Бо-Инь Яном к 2011 году.

Дизайн[править | править код]

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

В EdDSA используются следующие параметры:

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

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

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

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

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

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

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

Ed25519[править | править код]

Ed25519 — схема подписи EdDSA использующая SHA-512 и 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$ and $c=3,$
$B$ — уникальная точка $E(\mathbb {F} _{q})$ чья $y$ координата — $4/5$ , а $x$ координата — положительная(если говорить в терминах битового кодирования),
$H$ — SHA-512, с $b=256$ .

Кривая $E(\mathbb {F} _{q})$ бирационально эквивалентна кривой Монтгомери, известной как Curve25519. Эквивалентность^[6]^[2]

x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.

Эффективность[править | править код]

Команда Бернштейна оптимизировала Ed25519 для семейства процессоров x86-64 Nehalem/Westmere. Верификация может быть выполнена пакетами по 64 цифровые подписи для ещё большей пропускной способности. Ed25519 предназначена для обеспечения сопротивления атакам, сопоставимых с качеством 128-битных симметричных шифров. Публичные ключи — 256 битные в длину, а подпись имеет размер в два раза больше.

Безопасное кодирование[править | править код]

В качестве функции безопасности Ed25519 не использует операции ветвления и шаги индексации массивов, которые зависят от секретных данных, для предотвращения атак по сторонним каналам.

Так же как и другие дискретно логарифмические схемы подписи, EdDSA использует секретное значение, называемое одноразовым номером, уникальным для каждой подписи. В схемах подписи DSA и ECDSA этот одноразовый номер традиционно генерируется случайно для каждой сигнатуры, и, если генератор случайных чисел сломан или предсказуем во время формирования подписи, подпись может слить приватный ключ, что и случилось с ключом подписи обновления прошивки для приставки Sony PlayStation 3^[7]^[8]. По сравнению с ними, EdDSA выбирает одноразовые номера детерминировано, как хеш закрытого ключа и сообщения. Таким образом, однажды сгенерировав приватный ключ, EdDSA в дальнейшем не нуждается в генераторе случайных чисел для того, чтобы делать подписи, и нет никакой опасности, что сломанный генератор случайных чисел, используемый для создания цифровой подписи, раскроет приватный ключ.

Программное обеспечение[править | править код]

Известные применения Ed25519 включают в себя OpenSSH,^[9] GnuPG^[10] и различные альтернативы, а также инструмент значений от OpenBSD.^[11]

Референтная реализация SUPERCOP^[12] (язык Си с применением ассемблерных вставок)
Медленная, но лаконичная альтернативная реализация, не включающая защиту от атак по сторонним каналам (Python)
NaCl / libsodium^[13]
Протокол криптовалюты CryptoNote
wolfSSL^[14]
I2Pd имеет собственную реализацию EdDSA^[15]
Minisign и Minisign Miscellanea для macOS^[16]
Virgil PKI использует Ed25519 ключи по умолчанию
Botan
Dropbear SSH с теста 2013.61
OpenSSL 1.1.1 (поддержка TLS 1.3 и SHA3 в дополнение к X25519/Ed25519)
Hashmap Server and Client (язык Go и Javascript)
Libgcrypt

Примечания[править | править код]

↑ ¹ ² Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA). Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070—1721. RFC 8032. Retrieved 2017-07-31.
↑ ¹ ² ³ Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2012). «High-speed high-security signatures» (PDF). Journal of Cryptographic Engineering. 2 (2): 77-89. doi:10.1007/s13389-012-0027-1.
↑ Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe, and Bo-Yin Yang (2015-07-04). EdDSA for more curves (PDF)(Technical report). Retrieved 2016-11-14.
↑ Daniel J. Bernstein, Tanja Lange, and Peter Schwabe (2011-01-01). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. Retrieved 2016-11-14.
↑ Daniel J. Bernstein and Tanja Lange. «ECDLP Security: Rho». SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved 2016-11-16.
↑ Bernstein, Daniel J.; Lange, Tanja (2007). Kurosawa, Kaoru, ed. Faster addition and doubling on elliptic curves. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science. 4833. Berlin: Springer. pp. 29-50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.
↑ Johnston, Casey (2010-12-30). «PS3 hacked through poor cryptography implementation». Ars Technica. Retrieved 2016-11-15.
↑ fail0verflow (2010-12-29). Console Hacking 2010: PS3 Epic Fail (PDF). 27C3: 27th Chaos Communication Conference. Retrieved 2016-11-15.
↑ «Changes since OpenSSH 6.4». 2014-01-03. Retrieved 2016-10-07.
↑ What’s new in GnuPG 2.1". 2016-07-14. Retrieved 2016-10-07.
↑ «Things that use Ed25519». 2016-10-06. Retrieved 2016-10-07.
↑ «eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP». 2016-09-10. Retrieved 2016-10-07.
↑ Frank Denis (2016-06-29). «libsodium/ChangeLog». Retrieved 2016-10-07.
↑ «wolfSSL Embedded SSL Library (formerly CyaSSL)». Retrieved 2016-10-07.
↑ «Heuristic Algorithms and Distributed Computing»(PDF) (in Russian). 2015. pp. 55-56. ISSN 2311-8563. Retrieved 2016-10-07.
↑ minisign-misc on GitHub

Ссылки[править | править код]

Ed25519 home page

[:0-1] ¹ ² Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA). Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070—1721. RFC 8032. Retrieved 2017-07-31.

[:1-2] ¹ ² ³ Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2012). «High-speed high-security signatures» (PDF). Journal of Cryptographic Engineering. 2 (2): 77-89. doi:10.1007/s13389-012-0027-1.

[3] Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe, and Bo-Yin Yang (2015-07-04). EdDSA for more curves (PDF)(Technical report). Retrieved 2016-11-14.

[4] Daniel J. Bernstein, Tanja Lange, and Peter Schwabe (2011-01-01). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. Retrieved 2016-11-14.

[5] Daniel J. Bernstein and Tanja Lange. «ECDLP Security: Rho». SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved 2016-11-16.

[6] Bernstein, Daniel J.; Lange, Tanja (2007). Kurosawa, Kaoru, ed. Faster addition and doubling on elliptic curves. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science. 4833. Berlin: Springer. pp. 29-50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.

[7] Johnston, Casey (2010-12-30). «PS3 hacked through poor cryptography implementation». Ars Technica. Retrieved 2016-11-15.

[8] 0verflow (2010-12-29). Console Hacking 2010: PS3 Epic Fail (PDF). 27C3: 27th Chaos Communication Conference. Retrieved 2016-11-15.

[9] «Changes since OpenSSH 6.4». 2014-01-03. Retrieved 2016-10-07.

[10] What’s new in GnuPG 2.1". 2016-07-14. Retrieved 2016-10-07.

[11] «Things that use Ed25519». 2016-10-06. Retrieved 2016-10-07.

[12] «eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP». 2016-09-10. Retrieved 2016-10-07.

[13] Frank Denis (2016-06-29). «libsodium/ChangeLog». Retrieved 2016-10-07.

[14] «wolfSSL Embedded SSL Library (formerly CyaSSL)». Retrieved 2016-10-07.

[15] «Heuristic Algorithms and Distributed Computing»(PDF) (in Russian). 2015. pp. 55-56. ISSN 2311-8563. Retrieved 2016-10-07.

[16] sign-misc on GitHub

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]