EdDSA

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

• 1 Резюме
• 2 Ed25519
  • 2.1 Производительность
  • 2.2 Безопасное кодирование
  • 2.3 Программное обеспечение
• 3 Ed448
• 4 Ссылки
• 5 Внешние ссылки

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

На выбор схема подписи EdDSA :

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

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

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

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

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

Подпись

An Подпись EdDSA в сообщении $M\; \{\backslash \; displaystyle\; M\}$с помощью открытого ключа $A\; \{\backslash \; displaystyle\; A\}$- это пара $(R,\; S)\; \{\; \backslash \; displaystyle\; (R,\; S)\}$, закодированный в $2\; b\; \{\backslash \; displaystyle\; 2b\}$бит, точки кривой $R\; \in \; E\; (F\; q)\; \{\; \backslash \; displaystyle\; R\; \backslash \; in\; E\; (\backslash \; mathbb\; \{F\}\; \_\; \{q\})\}$и целое число , удовлетворяющее уравнению проверки $2\; c\; SB\; =\; 2\; c\; R\; +\; 2\; c\; H\; (R,\; А,\; М)\; А.\; \{\backslash \; displaystyle\; 2\; ^\; \{c\}\; SB\; =\; 2\; ^\; \{c\}\; R\; +\; 2\; ^\; \{c\}\; H\; (R,\; A,\; M)\; A.\}$

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

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

Ed25519 - схема подписи EdDSA с использованием SHA-512 (SHA-2) и Curve25519, где

• $q\; =\; 2255-19,\; \{\backslash \; displaystyle\; q\; =\; 2\; ^\; \{255\}\; -19,\}$
• $E\; /\; F\; q\; \{\backslash \; displaystyle\; E\; /\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\}$- это скрученная кривая Эдвардса

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

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

Производительность

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

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

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

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

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

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

• эталонная реализация SUPERCOP (язык C со встроенным ассемблером )
• Медленная, но лаконичная альтернативная реализация, не включает защиту от атак по побочным каналам (Python )
• NaCl / libsodium
• CryptoNote криптовалюта протокол
• wolfSSL
• I2Pd имеет собственную реализацию EdDSA
• Minisign и Minisign Miscellanea для macOS
• Virgil PKI по умолчанию использует ключи Ed25519
• Botan
• Dropbear SSH с 2013. 61test
• OpenSSL 1.1.1
• Hashmap сервер и клиент (язык Go и Javascript )
• Libgcrypt
• JDK 15

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

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