Принцип работы ECDSA

ECDSA (Elliptic Curve Digital Signature Algorithm) основан на свойствах эллиптических кривых над конечными полями и используется для создания цифровых подписей, обеспечивающих аутентичность и целостность данных при сравнительно небольших размерах ключей. В контексте JavaScript-библиотеки Stanford Javascript Crypto Library реализация ECDSA опирается на модульную арифметику, операции над точками эллиптической кривой и криптографически стойкие генераторы случайных чисел.

Эллиптическая кривая в криптографии задаётся уравнением вида:

y² = x³ + ax + b (mod p)

где p — большое простое число, определяющее конечное поле. Ключевым свойством является то, что множество точек на кривой образует абелеву группу относительно операции сложения точек.

Операции над точками включают:

  • сложение двух различных точек
  • удвоение точки
  • умножение точки на скаляр (повторное сложение)

Скалярное умножение:

k · G = G + G + … + G (k раз)

лежит в основе генерации ключей и подписи.

Генерация ключевой пары

ECDSA использует пару ключей:

  • приватный ключ d — случайное число
  • публичный ключ Q — точка на кривой

Связь определяется выражением:

Q = d · G

где G — базовая точка (generator point), фиксированная для конкретной кривой.

В Stanford Javascript Crypto Library приватный ключ обычно представлен как битовый массив или число в диапазоне порядка группы.

Пример генерации ключа:

var keypair = sjcl.ecc.elGamal.generateKeys(256);
var priv = keypair.sec;
var pub = keypair.pub;

Хотя в SJCL API чаще используется ElGamal-обёртка, внутри применяются те же операции эллиптической криптографии.

Процесс создания цифровой подписи

Подпись сообщения m включает несколько шагов.

  1. Вычисление хеша сообщения:

z = H(m)

В SJCL часто используется SHA-256:

var hash = sjcl.hash.sha256.hash(message);
  1. Генерация случайного числа k

k должен быть уникальным и криптографически стойким. Повторное использование k приводит к компрометации приватного ключа.

  1. Вычисление точки на кривой:

R = k · G

Берётся x-координата точки:

r = R.x mod n

  1. Вычисление второй части подписи:

s = k⁻¹ (z + r · d) mod n

Итоговая подпись состоит из пары (r, s).

Важность случайного числа k

Слабость или повторное использование k приводит к восстановлению приватного ключа:

d = (s·k - z) · r⁻¹ mod n

Поэтому в реализациях SJCL генерация случайных чисел зависит от криптостойкого PRNG, обычно связанного с sjcl.random.

sjcl.random.addEntropy(window.crypto.getRandomValues(new Uint32Array(32)));

Проверка подписи

Проверка выполняется без знания приватного ключа.

  1. Вычисляется:

w = s⁻¹ mod n

  1. Далее:

u1 = z · w mod n u2 = r · w mod n

  1. Вычисляется точка:

X = u1·G + u2·Q

  1. Подпись считается валидной, если:

X.x mod n == r

Реализация в SJCL

В Stanford Javascript Crypto Library операции ECDSA скрыты за ECC-модулем, который использует оптимизированные алгоритмы:

  • Jacobian coordinates для ускорения сложения точек
  • Montgomery reduction для модульной арифметики
  • precomputation таблицы для ускорения scalar multiplication

Пример работы с подписью:

var sig = priv.sign(hash);
var ok = pub.verify(hash, sig);

Эллиптические кривые в SJCL

Библиотека поддерживает несколько стандартных кривых, включая:

  • secp256r1 (NIST P-256)
  • secp256k1 (используется в криптовалютах)

Кривая задаётся параметрами (a, b, p, G, n, h), где:

  • n — порядок группы
  • h — кофактор

Безопасность ECDSA

Безопасность алгоритма опирается на сложность задачи дискретного логарифмирования на эллиптической кривой (ECDLP).

Основные угрозы:

  • повторное использование nonce k
  • слабый генератор случайных чисел
  • side-channel атаки
  • неправильная проверка подписи

SJCL минимизирует часть рисков за счёт строгой работы с энтропией, но безопасность конечной системы зависит от корректной интеграции.

Особенности реализации в JavaScript

ECDSA в JavaScript имеет дополнительные ограничения:

  • отсутствие аппаратного ускорения в чистом виде
  • зависимость от качества JS-движка
  • необходимость защиты от утечек через тайминги

SJCL решает часть проблем через:

  • постоянное время выполнения критических операций
  • минимизацию ветвлений в криптографическом коде
  • использование заранее подготовленных таблиц для ускорения вычислений

Формальное представление подписи

ECDSA можно записать как систему:

(r, s) = ( (kG)x mod n, k⁻¹(z + rd) mod n )

а проверка как:

r ≟ ( (z w G + r w Q)x mod n )

где:

  • G — генератор
  • Q — публичный ключ
  • d — приватный ключ
  • k — одноразовый nonce
  • z — хеш сообщения

Практическое значение в криптосистемах

ECDSA используется в:

  • TLS сертификатах
  • криптовалютах
  • системах аутентификации
  • цифровых подписях документов

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

Работа с большими числами

Все операции в SJCL выполняются над большими целыми числами, представленными через внутренний тип bigint-подобной структуры:

  • разбиение на 24- или 32-битные слова
  • операции сложения и умножения по словам
  • оптимизация через Karatsuba multiplication для больших значений

Взаимодействие с энтропией

Генерация ключей и nonce зависит от пула энтропии:

  • движения мыши
  • события клавиатуры
  • системные таймеры
  • криптографический RNG браузера

Если энтропии недостаточно, SJCL блокирует генерацию ключей до накопления минимального уровня случайности.

Ошибки реализации ECDSA

На практике наиболее критичные ошибки:

  • повтор nonce k
  • использование предсказуемого RNG
  • отсутствие проверки r и s на диапазон
  • некорректная обработка больших чисел (overflow)

SJCL закрывает часть этих проблем на уровне библиотеки, но логика приложения остаётся критической точкой уязвимости.

Оглавление