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

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

Дизайн

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

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

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

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

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

Публичный ключ

Открытый ключ в схеме EdDSA это точка кривой ${\displaystyle A\in E(\mathbb {F} _{q})}$ , закодированная в ${\displaystyle b}$ битах.

Подпись

Подпись EdDSA в сообщении M посредством открытого ключа ${\displaystyle A}$ является парой ${\displaystyle (R,S)}$ , закодированная в ${\displaystyle 2b}$ битах, точкой кривой ${\displaystyle R\in E(\mathbb {F} _{q})}$ и целым числом ${\displaystyle 0<S<\ell }$ , удовлетворяющим уравнению проверки

$${\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R,A,M)A.}$$

Закрытый ключ

Закрытым ключом в схеме EdDSA называется ${\displaystyle b}$ -битовая строка ${\displaystyle k}$ , которая должна быть выбрана равномерно случайным образом. Соответствующий отрытый ключ в данном случае это ${\displaystyle A=sB}$ , где ${\displaystyle s=H_{0,\dots ,b-1}(k)}$ , является наименее значимым b-битом H(k), интерпретируемым как целое число в прямом порядке байтов. Подпись сообщения M это пара (R,S) где R=rB для ${\displaystyle r=H(H_{b,\dots ,2b-1}(k),M)}$ и

$${\displaystyle S\equiv r+H(R,A,M)s{\pmod {\ell }}.}$$

. Это удовлетворяет уравнению проверки

Ed25519

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

• ${\displaystyle q=2^{255}-19,}$
• ${\displaystyle E/\mathbb {F} _{q}}$ — эллиптическая кривая Эдвардса

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

Кривая ${\displaystyle E(\mathbb {F} _{q})}$ бирационально эквивалентна кривой Монтгомери, известной как Curve25519. Эквивалентность

Эффективность

Команда Бернштейна оптимизировала Ed25519 для семейства процессоров x86-64 Nehalem /Westmere. Верификация может быть выполнена пакетами по 64 цифровые подписи для ещё большей пропускной способности. Ed25519 предназначена для обеспечения сопротивления атакам, сопоставимых с качеством 128-битных симметричных шифров . Публичные ключи — 256 битные в длину, а подпись имеет размер в два раза больше.

Безопасное кодирование

В качестве функции безопасности Ed25519 не использует операции ветвления и шаги индексации массивов, которые зависят от секретных данных, для предотвращения атак по сторонним каналам .

Так же как и другие дискретно логарифмические схемы подписи, EdDSA использует секретное значение, называемое одноразовым числом , уникальным для каждой подписи. В схемах подписи DSA и ECDSA это одноразовое число традиционно генерируется случайно для каждой сигнатуры, и, если генератор случайных чисел сломан или предсказуем во время формирования подписи, подпись может слить приватный ключ, что и случилось с ключом подписи обновления прошивки для приставки Sony PlayStation 3 . По сравнению с ними, EdDSA выбирает одноразовые номера детерминировано, как хеш закрытого ключа и сообщения. Таким образом, однажды сгенерировав приватный ключ, EdDSA в дальнейшем не нуждается в генераторе случайных чисел для того, чтобы делать подписи, и нет никакой опасности, что сломанный генератор случайных чисел, используемый для создания цифровой подписи, раскроет приватный ключ.

Программное обеспечение

Известные применения Ed25519 включают в себя OpenSSH , GnuPG и различные альтернативы, а также инструмент значений от OpenBSD .

• Референтная реализация SUPERCOP ( язык Си с применением ассемблерных вставок )
• Медленная, но лаконичная альтернативная реализация, не включающая защиту от атак по сторонним каналам ( Python )
• NaCl / libsodium
• Протокол криптовалюты CryptoNote
• wolfSSL
• I2Pd имеет собственную реализацию EdDSA
• Minisign и Minisign Miscellanea для macOS
• 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

Примечания

Ссылки