В основе большинства алгоритмов цифровой подписи лежит работа в конечных полях и кольцах вычетов. Центральной операцией выступает вычисление по модулю большого числа.
Модульная арифметика определяется выражением:
a ≡ b (mod n)
где два числа считаются эквивалентными, если их разность делится на n без остатка.
Ключевые операции:
Особое значение имеет операция модульного обратного элемента:
a⁻¹ mod n
такое число, которое удовлетворяет:
a · a⁻¹ ≡ 1 (mod n)
Без вычисления обратных элементов невозможны алгоритмы RSA и DSA, а также многие операции в эллиптических кривых.
Криптографические алгоритмы оперируют числами длиной 2048, 3072 и более бит. Обычные типы JavaScript не способны хранить такие значения без потерь точности.
Поэтому используется представление через BigInt или специализированные библиотеки, такие как BigInteger в составе jsrsasign.
Число представляется как последовательность машинных слов, над которыми выполняются:
Экспоненциальная операция реализуется через повторное возведение в квадрат:
a^e mod n
вычисляется за O(log e), а не за линейное число умножений.
Криптографическая подпись не применяется к исходному сообщению напрямую. Сначала выполняется хэширование.
Хэш-функция:
H(m) → d
где:
Свойства:
В jsrsasign используются алгоритмы семейства SHA:
Математически хэш-функции строятся на битовых операциях:
Цифровая подпись определяется как результат преобразования:
S = Sign(privkey, H(m))
Проверка:
Verify(pubkey, H(m), S) → true/false
Таким образом, подпись связывает:
RSA строится на сложности разложения большого числа на простые множители.
Выбираются простые числа:
p, q
Вычисляется модуль:
n = p · q
Функция Эйлера:
φ(n) = (p − 1)(q − 1)
Выбирается открытая экспонента e, такая что:
gcd(e, φ(n)) = 1
Закрытая экспонента d вычисляется как:
d ≡ e⁻¹ (mod φ(n))
Подпись формируется как:
S = H(m)^d mod n
Проверка:
H(m) ≟ S^e mod n
Без знания p и q невозможно вычислить φ(n), а значит невозможно найти d.
Сложность задачи эквивалентна факторизации:
n → p, q
При достаточно больших ключах (2048+ бит) это вычислительно неосуществимо.
DSA основан на задаче дискретного логарифмирования.
Выбираются параметры:
Ключи:
Выбирается случайное k:
r = (g^k mod p) mod q s = k⁻¹ (H(m) + x·r) mod q
Подпись: (r, s)
w = s⁻¹ mod q u1 = H(m) · w mod q u2 = r · w mod q
v = (g^u1 · y^u2 mod p) mod q
Подпись верна, если:
v = r
В jsrsasign широко используется ECDSA, основанный на свойствах эллиптических кривых над конечными полями.
y² = x³ + ax + b (mod p)
где p — простое число.
Точки кривой образуют абелеву группу:
Основная операция:
Q = k · G
где:
Вычисление выполняется через:
Выбирается случайное k:
R = k · G r = x(R) mod n
s = k⁻¹ (H(m) + r·d) mod n
где d — приватный ключ.
Подпись: (r, s)
w = s⁻¹ mod n u1 = H(m) · w mod n u2 = r · w mod n
X = u1·G + u2·Q
Подпись корректна, если:
r ≡ x(X) mod n
Сложение точек P и Q определяется разными случаями:
λ = (y2 − y1) / (x2 − x1)
x3 = λ² − x1 − x2 y3 = λ(x1 − x3) − y1
λ = (3x1² + a) / (2y1)
x3 = λ² − 2x1 y3 = λ(x1 − x3) − y1
Все операции выполняются по модулю p.
Без криптографически стойкого генератора случайных чисел невозможна безопасность ECDSA и DSA.
Случайное число k должно:
Утечка k приводит к восстановлению приватного ключа d:
d = (s·k − H(m)) · r⁻¹ mod n
Перед криптографическими вычислениями данные преобразуются в битовые последовательности.
Используются:
Хэш-функция работает именно с этим бинарным представлением.
jsrsasign реализует описанные модели через:
ASN.1 структура кодирует ключи в виде:
что позволяет интероперабельность с PEM/DER форматами.
Основные оценки:
Именно разрыв между полиномиальными и экспоненциальными задачами формирует криптографическую стойкость.
Все операции выполняются в конечных полях:
Свойства:
Это исключает накопление ошибок округления, характерное для вещественных чисел.
Безопасность схем определяется трудностью обратных задач:
Все они принадлежат классу задач, для которых не известны эффективные квантово-устойчивые решения в классической модели вычислений.
Общая структура всех алгоритмов:
Несмотря на различие математических структур, все схемы опираются на одну идею: односторонние функции в конечных алгебраических системах.