Цифровая подпись схема
В криптографии с открытым ключом, Алгоритм цифровой подписи по кривой Эдвардса (EdDSA ) - это схема цифровой подписи, использующая вариант подписи Шнорра на основе скрученных кривых Эдвардса. Он разработан, чтобы быть быстрее существующих схем цифровой подписи без ущерба для безопасности. Он был разработан командой, в которую входили Дэниел Дж. Бернштейн, Нильс Дуиф, Таня Ланге, Питер Швабе и Бо-Инь Ян. эталонная реализация - это общественное достояние.
Содержание
- 1 Резюме
- 2 Ed25519
- 2.1 Производительность
- 2.2 Безопасное кодирование
- 2.3 Программное обеспечение
- 3 Ed448
- 4 Ссылки
- 5 Внешние ссылки
Резюме
Ниже приводится упрощенное описание EdDSA, игнорирующее детали кодирования целых чисел и точек кривой как битовых строк; полная информация находится в статьях и RFC.
На выбор схема подписи EdDSA :
- из конечного поля сверх нечетной степени простого числа ;
- из эллиптической кривой более , чья группа из -рациональные точки имеют порядок , где - большое простое число, а называется кофактором;
- основания точка с порядком ; и
- из криптографической хеш-функции с - битовые выходные данные, где , чтобы элементы и точки кривой в могут быть представлены строками биты.
Эти параметры являются общими для всех пользователей схемы подписи EdDSA. Безопасность схемы подписи EdDSA критически зависит от выбора параметров, за исключением произвольного выбора базовой точки - например, алгоритм ро Полларда для логарифмов, как ожидается, потребует примерно сложения кривых прежде, чем он сможет вычислить дискретный логарифм, поэтому должен быть достаточно большим, чтобы это было невозможно, и обычно считается превышающим 2. Выбор ограничено выбором , поскольку по теореме Хассе не может отличаться от более чем на . Хэш-функция обычно моделируется как случайный оракул при формальном анализе безопасности EdDSA. В варианте HashEdDSA требуется дополнительная устойчивая к коллизиям хэш-функция .
В схеме подписи EdDSA
- Открытый ключ
- Открытый ключ EdDSA представляет собой точку кривой , закодированный в бит.
- Подпись
- An Подпись EdDSA в сообщении с помощью открытого ключа - это пара , закодированный в бит, точки кривой и целое число
- Закрытый ключ
- Закрытый ключ EdDSA - это b {\ displaystyle b}-битовая строка k {\ displaystyle k}, которая должна выбираться равномерно случайным образом. Соответствующий открытый ключ: A = s B {\ displaystyle A = sB}, где s = H 0,…, b - 1 (k) {\ displaystyle s = H_ { 0, \ точки, b-1} (k)}- младшие значащие b {\ displaystyle b}биты H (k) {\ displaystyle H (k)}интерпретируется как целое число с прямым порядком байтов. Подпись в сообщении M {\ displaystyle M}: (R, S) {\ displaystyle (R, S)}, где R = р В {\ displaystyle R = rB}для r = H (H b,…, 2 b - 1 (k), M) {\ displaystyle r = H (H_ {b, \ точки, 2b-1} (k), M)}и S ≡ r + H (R, A, M) s (mod). {\ displaystyle S \ Equiv r + H (R, A, M) s {\ pmod {\ ell}}.}Это удовлетворяет уравнению проверки:
2 c SB = 2 c (r + H ( R, A, M) s) B = 2 cr B + 2 c H (R, A, M) s B = 2 c R + 2 c H (R, A, M) A. {\ displaystyle {\ begin {align} 2 ^ {c} SB = 2 ^ {c} (r + H (R, A, M) s) B \\ = 2 ^ {c} rB + 2 ^ {c } H (R, A, M) sB \\ = 2 ^ {c} R + 2 ^ {c} H (R, A, M) A. \ end {align}}}Ed25519
Ed25519 - схема подписи EdDSA с использованием SHA-512 (SHA-2) и Curve25519, где
- q = 2255-19, {\ displaystyle q = 2 ^ {255} -19,}
- E / F q {\ displaystyle E / \ mathbb {F} _ {q}}- это скрученная кривая Эдвардса
- x 2 + y 2 = 1 - 121665 121666 x 2 y 2, {\ displaystyle -x ^ {2} + y ^ {2} = 1 - {\ frac {121665} {121666}} x ^ {2} y ^ {2},}- ℓ = 2 252 + 27742317777372353535851937790883648493 {\ displaystyle \ ell = 2 ^ {252} +27742317777372353535851937790883648493}и c = 3 {\ displaystyle c = 3} \ displaystyle B}- уникальная точка в E (F q) {\ displaystyle E (\ mathbb {F} _ {q})}, y {\ displaystyle y}координата 4/5 {\ displaystyle 4/5}, а x {\ displaystyle x}координата положительный.. "положительный" определяется в терминах битового кодирования:
- «положительные» координаты - это четные координаты (младший бит очищен)
- «отрицательные» координаты - нечетные координаты (установлен младший значащий бит)
- H {\ displaystyle H}- это SHA-512, где b = 256 {\ displaystyle b = 256}.
Кривая E (F q) {\ displaystyle E (\ mathbb {F} _ {q})}бирационально эквивалентен кривой Монтгомери, известной как Curve25519. Эквивалентность:
x = u v - 486664, y = u - 1 u + 1. {\ displaystyle x = {\ frac {u} {v}} {\ sqrt {-486664}}, \ quad y = {\ frac {u-1} {u + 1}}.}Производительность
Команда Бернштейна оптимизировала Ed25519 для семейства процессоров x86-64 Nehalem / Westmere. Проверка может выполняться партиями по 64 подписи для еще большей пропускной способности. Ed25519 предназначен для обеспечения устойчивости к атакам, сопоставимой с качеством 128-битных симметричных шифров. Открытые ключи имеют длину 256 бит, а подписи вдвое больше.
Безопасное кодирование
В качестве функций безопасности Ed25519 не использует операции ветвления и шаги индексации массива, которые зависят от секретных данных, поэтому для защиты от множества атак побочных каналов.
Как и другие схемы подписи на основе дискретного журнала, EdDSA использует секретное значение, называемое nonce, уникальное для каждой подписи. В схемах подписи DSA и ECDSA этот одноразовый номер традиционно генерируется случайным образом для каждой подписи - и если генератор случайных чисел когда-либо нарушается и предсказуем при создании подписи, подпись может просочиться. закрытый ключ, как это произошло с ключом подписи обновления прошивки Sony PlayStation 3. В отличие от этого, EdDSA детерминированно выбирает одноразовый номер как хэш части закрытого ключа и сообщения. Таким образом, как только закрытый ключ сгенерирован, EdDSA больше не нуждается в генераторе случайных чисел для создания подписей, и нет опасности того, что сломанный генератор случайных чисел, используемый для создания подписи, раскроет закрытый ключ.
Программное обеспечение
Известные применения Ed25519 включают OpenSSH, GnuPG и различные альтернативы, а также инструмент signify от OpenBSD. Использование Ed25519 в протоколе SSH стандартизируется. В 2019 году черновая версия стандарта FIPS 186-5 включала детерминированный Ed25519 в качестве утвержденной схемы подписи.
- эталонная реализация SUPERCOP (язык C со встроенным ассемблером )
- Медленная, но лаконичная альтернативная реализация, не включает защиту от атак по побочным каналам (Python )
- NaCl / libsodium
- CryptoNote криптовалюта протокол
- wolfSSL
- I2Pd имеет собственную реализацию EdDSA
- Minisign и Minisign Miscellanea для macOS
- Virgil PKI по умолчанию использует ключи Ed25519
- Botan
- Dropbear SSH с 2013. 61test
- OpenSSL 1.1.1
- Hashmap сервер и клиент (язык Go и Javascript )
- Libgcrypt
- JDK 15
Ed448
Ed448 - это схема подписи EdDSA с использованием SHAKE256 (SHA-3) и Curve448, определенных в RFC 8032. Она также была утверждено в проекте стандарта FIPS 186-5.
Ссылки
Внешние ссылки