EdDSA

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

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

Дизайн

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

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

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

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

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

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

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

Подпись

Подпись EdDSA в сообщении M посредством открытого ключа $A$ является парой $(R,S)$, закодированная в $2b$ битах, точкой кривой $R\in E({𝔽}_q)$ и целым числом $0<S<\ell$, удовлетворяющим уравнению проверки $$2^{c}SB=2^{c}R+2^{c}H(R,A,M)A.$$

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

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

$$\begin{array}{cc}{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{array}$$

Ed25519

Ed25519 — схема подписи EdDSA использующая SHA-512 и и эллиптическую кривую, связанную с Curve25519 где:

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

$$-x^2+y^2=1-\frac{121665}{121666}{x}^2{y}^2,$$

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

Кривая $E({𝔽}_q)$ бирационально эквивалентна кривой Монтгомери, известной как edwards25519. Эквивалентность $$x=\frac{u}{v}\sqrt{-486664},y=\frac{u-1}{u+1}.$$

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

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

Ссылки

• Ed25519 home page