Лаборатория теории чисел: RSA, простота, обратное по модулю

Зачем эта лаборатория

Криптография с открытым ключом — основа интернет-безопасности. HTTPS, цифровые подписи, шифрование, blockchain — всё базируется на трёх алгоритмах: RSA (1977), DSA/ECDSA (1990s), Diffie-Hellman (1976). Понимание их работы требует знания теории чисел: простоты, факторизации, модульной арифметики, обратных элементов. Эта лаборатория показывает базовые операции пошагово.

Тест Миллера–Рабина

Простые числа — фундамент RSA. Для генерации 2048-битного ключа нужно найти два простых числа по 1024 бита каждое. Перебор кандидатов с пробным делением заняли бы вечность; нужен быстрый вероятностный тест.

Тест Миллера–Рабина (1976, M.O. Rabin; ранее M.M. Miller, 1976) основан на следующем факте: если n простое и a, такое что 1 < a < n, то либо a^d ≡ 1 (mod n), либо a^(2^r·d) ≡ -1 (mod n) для некоторого 0 ≤ r < s, где n-1 = 2^s·d. Если для случайно выбранного a свойство нарушается — n точно составное. Если выполняется — n вероятно простое.

С 12 свидетелями (наша реализация) для чисел до 3.3 × 10²⁴ тест детерминирован.

Расширенный алгоритм Евклида

Классический алгоритм Евклида находит НОД(a, b). Расширенный — дополнительно находит коэффициенты x, y такие, что a·x + b·y = gcd(a, b). Это критически важно для криптографии: позволяет найти обратный элемент по модулю d = e⁻¹ mod φ — приватный ключ RSA.

Сложность — O(log min(a, b)) — экстремально быстро даже для огромных чисел.

RSA — пошагово

1. Генерация ключей: выбираем простые p, q; вычисляем n = pq, φ = (p−1)(q−1).
2. Публичная экспонента: e — целое, взаимно простое с φ. Стандарт — e = 65537 = 2¹⁶ + 1.
3. Приватная экспонента: d = e⁻¹ mod φ через расширенный Евклид.
4. Публичный ключ: (n, e). Можно публиковать в открытом виде.
5. Приватный ключ: (n, d). Хранится в секрете.
6. Шифрование: c = m^e mod n, где m — сообщение (число меньше n).
7. Дешифрование: m = c^d mod n. Только владелец d может расшифровать.

Безопасность RSA основана на том, что зная только n, e и c, невозможно эффективно вычислить m — для этого пришлось бы факторизовать n, что занимает экспоненциальное время для больших n.

ECDSA и эллиптические кривые

Эллиптические кривые — другой класс групп с операцией сложения, на которых задача дискретного логарифма (восстановления k из k·G, где G — генератор) считается вычислительно неразрешимой. ECDSA использует это для подписей: 256-битный ключ ECDSA даёт криптостойкость, эквивалентную 3072-битному RSA.

Реализовать ECDSA в браузере с нуля — сложная задача (требует константного времени, защиты от time-attack), поэтому в нашей лаборатории — только теоретическое описание. Для практической работы — Web Crypto API.