Дизайн
Ниже приведено упрощённое описание 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 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.
- 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.
- ↑ 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
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .