User:AC POINT

В криптографических системах с открытым ключом, Edwards-curve Digital Signature Algorithm (EdDSA) – схема цифровой подписи использующая вариант схемы подписи Шнора основанной на эллиптической кривой Эдвардса. Она спроектирована так что бы быть быстрее по сравнению с существующей схемой цифровой подписи без ущерба для ее безопасности. Она была разработана Дэниелом Дж. Бернштайном, Нильсом Дуйфом, Таней Ланге, Питером Швабе и Бо-Инь Яном.

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

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

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

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

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

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

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

Подпись

Подпись EdDSA в сообщении M посредством открытого ключа A является парой (R,S), закодированная в 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 называется b-битовая строка 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 }}.}$$. Это удовлетворяет уравнению проверки:

$${\displaystyle {\begin{aligned}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{aligned}}}$$

Ed25519 – схема подписи EdDSA использующая SHA-512 и Curve25519 где: *q= 2^255-19 *${\displaystyle E/\mathbb {F} _{q}}$ – элептическая кривая Эдвардса $${\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}$$ *l= 2^255+27742317777372353535851937790883648493 и с=3 *B – уникальная точка ${\displaystyle E(\mathbb {F} _{q})}$ чья y координата – 4/5, а x координата – положительная(если говорить в терминах битового кодирования) H – SHA512, с b=256 Кривая ${\displaystyle E(\mathbb {F} _{q})}$ бирационально эквивалентна кривой Монтгомери, известной как Curve25519. Эквивалентность $${\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 использует секретное значение называемое одноразовым номер, уникальным для каждой подписи. В схемах подписи DSA и ECDSA этот одноразовый номер традиционно генерируется случайно для каждой сигнатуры и если генератор случайных чисел сломан или предсказуем во время формирования подписи, подпись может слить приватный ключ, что и случилось с ключом подписи обновления прошивки для приставки Sony PlayStation 3. По сравнению с ними, EdDSA выбирает одноразовые номера детерминировано, как хэш закрытого ключа и сообщения. Таким образом, однажды сгенерировав приватный ключ, EdDSA в дальнейшем не нуждается в генераторе случайных чисел для того что бы делать подписи, и нет никакой опасности что сломанный генератор случайных чисел используемый для создания цифровой подписи раскроет приватный ключ.

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

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

Категория:Эллиптическая криптография Категория:Электронная подпись