EdDSA

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

Дизайн

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

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

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

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

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

Публичный ключ
Открытый ключ в схеме EdDSA это точка кривой [math]\displaystyle{ A \in E(\mathbb{F}_q) }[/math], закодированная в b битах.
Подпись
Подпись EdDSA в сообщении M посредством открытого ключа A является парой (R,S), закодированная в 2b битах, точкой кривой [math]\displaystyle{ R \in E(\mathbb{F}_q) }[/math] и целым числом [math]\displaystyle{ 0 \lt S \lt \ell }[/math], удовлетворяющим уравнению проверки [math]\displaystyle{ 2^c S B = 2^c R + 2^c H(R, A, M) A. }[/math]
Закрытый ключ
Закрытым ключом в схеме EdDSA называется b-битовая строка k, которая должна быть выбрана равномерно случайным образом. Соответствующий отрытый ключ в данном случае это [math]\displaystyle{ A = s B }[/math], где [math]\displaystyle{ s = H_{0,\dots,b - 1}(k) }[/math], является наименее значимым b-битом H(k), интерпретируемым как целое число в прямом порядке байтов. Подпись сообщения M это пара (R,S) где R=rB для [math]\displaystyle{ r = H(H_{b,\dots,2b - 1}(k), M) }[/math] и [math]\displaystyle{ S \equiv r + H(R, A, M) s \pmod \ell. }[/math]. Это удовлетворяет уравнению проверки

[math]\displaystyle{ \begin{align} 2^c S B &= 2^c (r + H(R, A, M) s) B \\ &= 2^c r B + 2^c H(R, A, M) s B \\ &= 2^c R + 2^c H(R, A, M) A. \end{align} }[/math]

Ed25519

Ed25519 — схема подписи EdDSA использующая SHA-512 и Curve25519[2] где:

  • [math]\displaystyle{ q = 2^{255} - 19, }[/math]
  • [math]\displaystyle{ E/\mathbb{F}_q }[/math] — эллиптическая кривая Эдвардса

[math]\displaystyle{ -x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2, }[/math]

  • [math]\displaystyle{ \ell = 2^{252} + 27742317777372353535851937790883648493 }[/math] and [math]\displaystyle{ c = 3, }[/math]
  • [math]\displaystyle{ B }[/math] — уникальная точка [math]\displaystyle{ E(\mathbb{F}_q) }[/math] чья [math]\displaystyle{ y }[/math] координата — [math]\displaystyle{ 4/5 }[/math], а [math]\displaystyle{ x }[/math] координата — положительная(если говорить в терминах битового кодирования),
  • [math]\displaystyle{ H }[/math] — SHA-512, с [math]\displaystyle{ b = 256 }[/math].

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

Эффективность

Команда Бернштейна оптимизировала 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]

Примечания

  1. ↑ 1,0 1,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.
  2. ↑ 2,0 2,1 2,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. ↑ fail0verflow (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. ↑ minisign-misc on GitHub

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=EdDSA&oldid=5858203