EdDSA

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

В 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}}}$ кривые, перед тем как сможет^{[уточнить]} вычислить логарифм,[4] поэтому l должно быть достаточно большим, чтобы это было невозможно и обычно должно превышать 2^200.[5] Выбор 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[2] где:

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

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

• ${\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}$ and ${\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. Эквивалентность[6][2]

$${\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}$$

• Ed25519 home page