EdDSA
В криптографических системах с открытым ключом, Edwards-curve Digital Signature Algorithm (EdDSA) — схема цифровой подписи использующая вариант схемы Шнора основанной на эллиптической кривой Эдвардса[1].
Она спроектирована так, чтобы быть быстрее по сравнению с существующей схемой цифровой подписи без ущерба для её безопасности. Она была разработана Дэниелом Дж. Бернштейном[англ.], Нильсом Дуйфом, Таней Ланге, Питером Швабе и Бо-Инь Яном к 2011 году.
Дизайн
Ниже приведено упрощённое описание EdDSA, не включающее в себя детали кодирования целых чисел и точек кривой как битовых строк. Полное описание и детали данной реализации цифровой подписи можно найти в документации и соответствующих RFC[1][2][3].
В EdDSA используются следующие параметры:
- Выбор конечного поля порядка :
- Выбор эллиптической кривой над полем чья группа из рациональных точек
имеющих порядок[уточнить] , где — большое простое число, а называется кофактором - Выбор базовой точки с порядком
- И выбор защищенной от коллизии хеш функции с -битными выходами, где так что элементы конечного поля и точек кривой в могли бы быть представлены в виде строки длиной бит.
Эти параметры минимально необходимые для всех пользователей схемы подписи EdDSA. Безопасность подписи EdDSA очень сильно зависит от выбора параметров, за исключением произвольного выбора базовой точки. Например, ро-алгоритм Поларда для логарифма должен принимать примерно кривые, перед тем как сможет[уточнить] вычислить логарифм,[4] поэтому должно быть достаточно большим, чтобы это было невозможно и обычно должно превышать 2^200.[5] Выбор ограничен выбором , так как по теореме Хассе не должно отличаться от больше чем на
В рамках схемы подписи EdDSA
- Публичный ключ
- Открытый ключ в схеме EdDSA это точка кривой , закодированная в битах.
- Подпись
- Подпись EdDSA в сообщении M посредством открытого ключа является парой , закодированная в битах, точкой кривой и целым числом , удовлетворяющим уравнению проверки
- Закрытый ключ
- Закрытым ключом в схеме EdDSA называется -битовая строка , которая должна быть выбрана равномерно случайным образом. Соответствующий отрытый ключ в данном случае это , где , является наименее значимым b-битом H(k), интерпретируемым как целое число в прямом порядке байтов. Подпись сообщения M это пара (R,S) где R=rB для и . Это удовлетворяет уравнению проверки
Ed25519
Ed25519 — схема подписи EdDSA использующая SHA-512 и Curve25519[2] где:
- — эллиптическая кривая Эдвардса
- и
- — уникальная точка чья координата равна , а координата — положительная(если говорить в терминах битового кодирования),
- — SHA-512, с .
Кривая бирационально эквивалентна кривой Монтгомери, известной как Curve25519. Эквивалентность[2][6]
Эффективность
Команда Бернштейна оптимизировала 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
Примечания
- ↑ 1 2 Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA). Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 20701721. 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 23118563. Retrieved 2016-10-07.
- ↑ minisign-misc on GitHub
Ссылки
- Ed25519 home page