Ed25519 построен на эллиптической кривой в форме twisted Edwards:
x² + y² = 1 + d·x²y²
где вычисления выполняются в конечном поле ?ₚ с модулем:
p = 2²⁵⁵ − 19
Параметр кривой:
d = −121665 / 121666 (по модулю p)
Эта форма выбрана не случайно: она обеспечивает высокую скорость операций и устойчивость к ряду атак, связанных с реализациями и побочными каналами.
Ключевая особенность twisted Edwards-кривых — симметричная и унифицированная формула сложения точек, что делает арифметику более простой и безопасной для программной реализации.
Все операции в Ed25519 выполняются по модулю p:
Число p = 2²⁵⁵ − 19 выбрано для ускорения редукции: оно близко к степени двойки, что позволяет оптимизировать операции на уровне битовых представлений.
Кривая содержит циклическую подгруппу большого простого порядка:
l = 2²⁵² + 27742317777372353535851937790883648493
Генератором является фиксированная базовая точка B.
Любой приватный ключ s интерпретируется как скаляр:
A = s · B
где A — публичный ключ.
В Ed25519 приватный ключ не используется напрямую как число. Он формируется через хэширование:
Clamping — критически важная операция:
Это гарантирует, что скаляр принадлежит корректному подмножеству группы.
Схема подписи строится на комбинации хэширования и скалярной арифметики.
Пусть:
r = SHA-512(prefix || M)
где prefix — правая половина хэша приватного ключа.
Далее:
R = r · B
k = SHA-512(R || A || M)
Хэш связывает:
Это предотвращает подмену элементов подписи.
S = (r + k · s) mod l
Подпись состоит из двух элементов:
(R, S)
Проверка основана на равенстве:
S·B = R + k·A
где:
Если равенство выполняется, подпись считается корректной.
Для twisted Edwards-кривых операция сложения точек (x₁, y₁) и (x₂, y₂) задаётся формулами:
x₃ = (x₁y₂ + y₁x₂) / (1 + d·x₁x₂y₁y₂)
y₃ = (y₁y₂ − x₁x₂) / (1 − d·x₁x₂y₁y₂)
Деление выполняется через умножение на обратный элемент в поле ?ₚ.
Для устранения дорогостоящих операций деления используется переход к проективным координатам:
(x, y) → (X, Y, Z)
где:
x = X / Z y = Y / Z
Это позволяет заменить деления умножениями и ускоряет scalar multiplication.
Скаляр s разбивается на 256-битное число с дополнительной обработкой:
Это уменьшает количество сложений точек при умножении на скаляр.
SHA-512 выполняет две разные роли:
Использование одной хэш-функции в разных контекстах не создаёт уязвимости благодаря различию входных данных.
Ключевая проблема схем подписи — утечка nonce r.
В Ed25519 nonce:
r = SHA-512(prefix || M)
Это делает его:
Тем самым устраняется класс атак, связанных с плохими RNG.
В реализациях на Jav * aScript:
Scalar multiplication обычно реализуется через алгоритм double-and-add с оптимизациями windowing.
Для криптографической устойчивости важно отсутствие зависимостей времени выполнения от секретных данных.
В реализации:
Это снижает риск timing-атак.
Уравнение:
S·B = R + k·A
можно интерпретировать как доказательство знания s, без его раскрытия.
Если переписать:
S·B = r·B + k·s·B
то становится видно, что:
S ≡ r + k·s (mod l)
Подпись связывает случайность r, сообщение M и секрет s в единую алгебраическую структуру.