EdDSA

В криптографии с открытым ключом , Edwards кривой Алгоритм цифровой подписи ( EdDSA ) является цифровая подпись схема с использованием варианта Шнорра подписи , основанной на искривленных кривых Edwards . ^[1] Он разработан, чтобы быть быстрее существующих схем цифровой подписи без ущерба для безопасности. Он был разработан командой, в которую входили Даниэль Дж. Бернштейн , Нильс Дуиф, Таня Ланге , Питер Швабе и Бо-Инь Ян. ^[2] эталонная реализация является программным обеспечением общественного достояния . ^[3]

Резюме [ править ]

Ниже приводится упрощенное описание EdDSA без учета деталей кодирования целых чисел и точек кривой как битовых строк; полная информация в статьях и RFC. ^{[4] [2] [1]}

Схема подписи EdDSA - это выбор:

• из конечного поля над нечетной мощностью ;${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle q}$
• на эллиптической кривой над которой группа из рациональных точек имеет порядок , в котором большое число и называется кофактором;${\ displaystyle E}$${\ displaystyle \ mathbb {F} _ {q}}$${\ Displaystyle Е (\ 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 в решающей степени зависит от выбора параметров, за исключением произвольного выбора базовой точки - например, ожидается , что алгоритм Ро Полларда для логарифмов потребует приблизительно сложения кривых, прежде чем сможет вычислить дискретный логарифм ^[5]. so должен быть достаточно большим, чтобы это было невозможно, и обычно превышает 2 ²⁰⁰ . ^[6] Выбор ограничен выбор , так как по теореме Хассе , не может отличаться от более чем . Хеш-функция${\displaystyle {\sqrt {\ell \pi /4}}}$${\displaystyle \ell }$${\displaystyle \ell }$${\displaystyle q}$${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$${\displaystyle q+1}$${\displaystyle 2{\sqrt {q}}}$${\displaystyle H}$обычно моделируется как случайный оракул при формальном анализе безопасности EdDSA. В варианте HashEdDSA требуется дополнительная хеш-функция, устойчивая к коллизиям .${\displaystyle H'}$

В схеме подписи EdDSA

Открытый ключ

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

Подпись

Подпись EdDSA в сообщении с помощью открытого ключа - это закодированная в битах пара точки кривой и целого числа, удовлетворяющая уравнению проверки.${\displaystyle 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)}$${\displaystyle b}$${\displaystyle H(k)}$${\displaystyle M}$${\displaystyle (R,S)}$${\displaystyle 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 [ править ]

Ed25519 - это схема подписи EdDSA с использованием SHA-512 (SHA-2) и 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}$ а также ${\displaystyle c=3}$
• ${\displaystyle B}$- единственная точка , координата которой положительна. "положительный" определяется в терминах битового кодирования:${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle y}$${\displaystyle 4/5}$${\displaystyle x}$
  
  • "положительные" координаты - это четные координаты (младший бит очищен)
  • «отрицательные» координаты - нечетные координаты (установлен младший бит)
• ${\displaystyle H}$это SHA-512 , с .${\displaystyle b=256}$

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

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

Производительность [ править ]

Первоначальная команда оптимизировала Ed25519 для семейства процессоров x86-64 Nehalem / Westmere . Проверка может выполняться партиями по 64 подписи для еще большей пропускной способности. Ed25519 предназначен для обеспечения устойчивости к атакам, сопоставимой с качеством 128-битных симметричных шифров . ^[8] Открытые ключи имеют длину 256 бит, а подписи вдвое больше. ^[9]

Безопасное кодирование [ править ]

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

Как и другие схемы подписи на основе дискретного журнала, EdDSA использует секретное значение, называемое одноразовым идентификатором, уникальным для каждой подписи. В схемах подписи DSA и ECDSA этот одноразовый номер традиционно генерируется случайным образом для каждой подписи - и если генератор случайных чисел когда-либо сломается и станет предсказуемым при создании подписи, подпись может вызвать утечку закрытого ключа, как это произошло с прошивкой Sony PlayStation 3 обновить ключ подписи. ^{[10] [11] [12]}Напротив, EdDSA детерминированно выбирает одноразовый номер как хэш части закрытого ключа и сообщения. Таким образом, после того, как закрытый ключ сгенерирован, EdDSA больше не нуждается в генераторе случайных чисел для создания подписей, и нет опасности, что сломанный генератор случайных чисел, используемый для создания подписи, раскроет закрытый ключ.

Несоответствия в стандартизации и реализации [ править ]

Обратите внимание, что для EdDSA предпринимаются две попытки стандартизации: одна от IETF, информационная RFC  8032 и одна от NIST как часть FIPS 186–5 (2019). ^[13] Различия между стандартами были проанализированы, ^{[14] [15]} и доступны тест-векторы. ^[16]

Программное обеспечение [ править ]

Известные применения Ed25519 включают OpenSSH , ^[17] GnuPG ^[18] и различные альтернативы, а также инструмент signify от OpenBSD . ^[19] Использование Ed25519 в протоколе SSH стандартизируется. ^[20] В 2019 году черновая версия стандарта FIPS 186-5 включала детерминированный Ed25519 в качестве утвержденной схемы подписи. ^[21]

• Эталонная реализация SUPERCOP ^[22] ( язык C со встроенным ассемблером )
• Медленная, но краткая альтернативная реализация ^[23] не включает защиту от атак по побочным каналам ^[24] ( Python )
• NaCl / либнатрий ^[25]
• Протокол криптовалюты CryptoNote
• wolfSSL ^[26]
• I2Pd имеет собственную реализацию EdDSA ^[27]
• Minisign ^[28] и Minisign Miscellanea ^[29] для macOS
• Вирджил PKI по умолчанию использует ключи Ed25519 ^[30]
• Ботан
• Dropbear SSH с 2013 г. 61test ^[31]
• OpenSSL 1.1.1 ^[32]
• Сервер и клиент Hashmap ( язык Go и Javascript )
• Libgcrypt
• Комплект для разработки Java 15

Ed448 [ править ]

Ed448 - это схема подписи EdDSA с использованием SHA-3 и Curve448, определенная в RFC 8032 . Он также был утвержден в проекте стандарта FIPS 186-5. ^[21] 

Ссылки [ править ]

Внешние ссылки [ править ]

• Ed25519 домашняя страница