EdDSA

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

  • Выбор конечного поля порядка q:
  • Выбор эллептической кривой E над полем чья группа из рациональных точек имеющих порядок , где l — большое простое число, а 2^с называется кофактором
  • Выбор базовой точки с порядком l
  • И выбор защищенной от коллизии хеш фушкции H с 2b-битными выходами, где 2^(b-1)>q так что элементы конечного поля и точек кривой в могли бы быть представлены в виде строки длинной b бит.

Эти параметры минимально необходимые для всех пользователей схемы подписи EdDSA. Безопасность подписи EdDSA очень сильно зависит от выбора параметров, за исключением произвольного выбора базовой точки. Например ро-лгоритм Поларда для логарифма должен принимать примерно кривые, перед тем как сможет вычислить логарифм,[4] поэтому l должно быть достаточно большим что бы это было не возможно и обычно должно превышать 2^200.[5] Выбор l ограничен выбором q, так как по теореме Хассе не должно отличаться от q+1 больше чем на

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

Публичный ключ
Открытый ключ в схеме EdDSA это точка кривой , закодированная в b битах.
Подпись
Подпись EdDSA в сообщении M посредством открытого ключа A является парой (R,S), закодированная в 2b битах, точкой кривой и целым числом удовлетворяющим уравнению проверки
Закрытый ключ
Закрытым ключом в схеме EdDSA называется b-битовая строка k которая должна быть выбрана равномерно случайным образом. Соответствующий окрытый ключ в данном случае это , где является наимеменее значимым b-битом H(k) интерпретируемым как целое число в прямом порядке байтов. Подпись сообщения M это пара (R,S) где R=rB для и
. Это удовлетворяет уравнению проверки

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

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

  • q= 2^255-19
  •  — эллиптическая кривая Эдвардса

  • l= 2^255+27742317777372353535851937790883648493 и с=3
  • B — уникальная точка чья y координата — 4/5, а x координата — положительная(если говорить в терминах битового кодирования)

H — SHA-512, с b=256 Кривая бирационально эквивалентна кривой Монтгомери, известной как Curve25519. Эквивалентность[6][2]

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

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

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