Русская Википедия:EdDSA

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Дизайн

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

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

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

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

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

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

<math display="block"> \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>q = 2^{255} - 19,</math>
  • <math>E/\mathbb{F}_q</math> — эллиптическая кривая Эдвардса

<math display="block">-x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2,</math>

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

Кривая <math>E(\mathbb{F}_q)</math> бирационально эквивалентна кривой Монтгомери, известной как Curve25519. Эквивалентность[6][2] <math display="block"> 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
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:EdDSA&oldid=8640587