Теория чисел
Тесты простоты
Каждый TLS-сертификат содержит RSA- или ECDSA-ключ, созданный из случайных простых чисел. Браузер Chrome проверяет простоту числа из 617 цифр прежде чем доверять серверу. За этим стоит алгоритм Миллера-Рабина - 40 раундов, каждый один вызов pow() - вся проверка за микросекунды. Как он гарантирует, что составное не проскользнёт? Именно это разберём.
- **OpenSSL RSA:** BN_generate_prime_ex() - пробное деление до 2000, затем Миллер-Рабин с 64 раундами; ~100 мс на 2048-битный ключ
- **Python sympy.isprime:** детерминированный для n < 3.3·10²⁴ (фиксированные базы), вероятностный для больших
- **Java BigInteger.isProbablePrime(k):** k итераций Миллера-Рабина; Java HTTPS-соединения используют это при генерации ключей
Предварительные знания
Пробное деление и тест Ферма
Проверка простоты - одна из самых практически важных задач в криптографии. Наивный метод - пробное деление на все простые до √n - работает за O(√n), что неприемлемо для 1024-битных чисел. Тест Ферма ускоряет проверку, но имеет критический изъян.
**Пробное деление:** проверить p ≤ √n. - Сложность: O(√n) - для 512-битного n это 2²⁵⁶ операций. Нереально. **Тест Ферма:** если aⁿ⁻¹ ≢ 1 (mod n) для некоторого a - n составное. - Если aⁿ⁻¹ ≡ 1 (mod n) для многих a - n «вероятно простое» - Сложность: O(log² n) - молниеносно - Изъян: числа Кармайкла проходят тест для ВСЕХ a с gcd(a,n)=1
561 = 3 × 11 × 17 - первое число Кармайкла. Для него aⁿ⁻¹ ≡ 1 (mod 561) для всех a, взаимно простых с 561. Использовать тест Ферма в криптографии нельзя без защиты от Кармайкла.
Тест Ферма показывает 2⁵⁶⁰ ≡ 1 (mod 561). Что можно заключить?
Тест Миллера-Рабина
Тест Миллера-Рабина - золотой стандарт проверки простоты в криптографии. Он устраняет уязвимость теста Ферма, используя дополнительное условие: квадратные корни из 1 по простому модулю могут быть только ±1.
**Идея Миллера-Рабина:** если n простое и n−1 = 2ˢ·d, то для любого a: 1. a^d ≡ 1 (mod n), ИЛИ 2. a^(2ʲ·d) ≡ −1 (mod n) для некоторого j ∈ {0,...,s−1} Если ни одно из условий не выполнено - n составное (a - «свидетель»). **Вероятностный тест:** для случайного a вероятность ошибки ≤ 1/4 за раунд. После k раундов - ≤ 4^(−k). **Детерминированный вариант:** для n < 3.3·10²⁴ достаточно проверить a ∈ {2,3,5,7,11,13,17,19,23,29,31,37}.
| n < | Достаточные базы | Источник |
|---|---|---|
| 2 047 | {2} | Pomerance et al. |
| 3 215 031 751 | {2, 3, 5, 7} | Jaeschke |
| 3.3 × 10²⁴ | {2,3,5,7,11,13,17,19,23,29,31,37} | Sinclair |
| ∞ | k случайных баз | Ошибка ≤ 4⁻ᵏ |
Тест Миллера-Рабина с 40 раундами: вероятность ложноположительного ответа (составное принято за простое)?
AKS и другие детерминированные тесты
До 2002 года не существовало полиномиального детерминированного алгоритма проверки простоты. Алгоритм AKS (Агравал-Каял-Саксена) решил эту теоретическую задачу, хотя на практике проигрывает Миллеру-Рабину.
**Теорема AKS (2002):** PRIMES ∈ P - простота проверяется за полиномиальное время. Алгоритм: n простое ⟺ (X + a)ⁿ ≡ Xⁿ + a (mod Xʳ − 1, n) для подходящего r и всех a ≤ √φ(r)·log n. **Сложность:** O(log^{7.5}(n)) - теоретически полиномиальная. **Тест Люка (Lucas primality test):** n простое ⟺ существует a: aⁿ⁻¹ ≡ 1 (mod n) и для каждого простого q | (n−1): a^{(n-1)/q} ≢ 1 (mod n). Требует знания разложения n−1. **На практике:** - Миллер-Рабин с 40 раундами: достаточно для RSA - OpenSSL, Python, Java: используют Миллер-Рабин - AKS: теоретически важен, практически слишком медленен
Как TLS генерирует ключи на практике: OpenSSL вызывает BN_generate_prime_ex(), которая генерирует случайные нечётные числа, быстро отсеивает делителями до 2000 (пробным делением), затем применяет Миллер-Рабин с 64 раундами. Для 2048-битного ключа это занимает ~100 мс на обычном CPU.
Почему AKS не используется в реальных криптосистемах вместо Миллера-Рабина?
Ключевые идеи
- **Пробное деление:** O(√n) - слишком медленно для 512+ бит; числа Кармайкла ломают тест Ферма
- **Миллер-Рабин:** O(k·log³ n); вероятность ошибки ≤ 4⁻ᵏ; детерминированный для n < 3.3·10²⁴
- **AKS (2002):** PRIMES ∈ P доказано; практически медленнее Миллера-Рабина на порядки
- **На практике:** OpenSSL/Python/Java используют Миллер-Рабин с 20-64 раундами
Связанные темы
Тесты простоты опираются на всю предшествующую теорию:
- Теоремы Ферма и Эйлера — Тест Миллера-Рабина - усиленная версия теста Ферма с проверкой квадратных корней
- Распределение простых — ТПЧ определяет число кандидатов для генерации RSA-простых
- Числа в криптографии — Генерация RSA-ключей в OpenSSL - прямое применение тестов простоты
Вопросы для размышления
- Число Кармайкла обходит тест Ферма для всех взаимно простых оснований. Почему тест Миллера-Рабина обнаруживает такие числа?
- AKS доказывает PRIMES ∈ P. Означает ли это, что задача факторизации тоже решается за полиномиальное время?
- Если квантовый компьютер реализует алгоритм Шора, как это повлияет на генерацию простых для криптографии?