Вычислительная теория чисел

RSA-2048 держится лишь потому, что нет быстрого алгоритма факторизации. Но 'нет известного' ≠ 'не существует'. История криптографии - это гонка: математики придумывают всё более хитрые алгоритмы (GNFS взломал RSA-512 в 1999), а криптографы увеличивают размер ключей. Понимать вычислительную теорию чисел - значит понимать реальные пределы безопасности.

• **RSA и GNFS:** 512-битный RSA взломан в 1999 за 35 CPU-лет; именно поэтому сейчас используют 2048+ бит
• **rho Полларда в Bitcoin:** алгоритм используется для поиска коллизий в слабых ECC-реализациях
• **Index Calculus и Diffie-Hellman:** уязвимость DH в Zp* к Index Calculus - причина перехода на ECDH

Предварительные знания

• Primality Tests
• Number Theory in Cryptography

B-гладкие числа и решето Эратосфена

Атака на RSA-512 (1999) использовала B-гладкие числа: квадратичное решето нашло множители 512-битного модуля за 8000 MIPS-лет. **B-гладкое число** - число, все простые делители которого не превышают B. B-гладкие числа - ключевое понятие для факторизационных алгоритмов: если в процессе вычислений удаётся получить B-гладкое число, его можно полностью разложить, используя лишь малые простые из factor base.

Ψ(x, B) = #{n <= x : n является B-гладким}. Приближение: Ψ(x, B) ≈ x * u^(-u), где u = log(x)/log(B). Пример: для x = 10^20, B = 10^3: u = 20/3 ≈ 6.7, доля B-гладких ≈ (6.7)^(-6.7) ≈ 10^(-5.5). Это объясняет, почему алгоритмы на B-гладких числах эффективны при правильном выборе B.

Алгоритм rho Полларда

**Алгоритм rho Полларда** (1975) факторизует N за O(N^(1/4)) операций. Идея: случайное блуждание x_{n+1} = x_n^2 + c (mod N) рано входит в цикл (парадокс дня рождения), и gcd разности двух значений с N даёт нетривиальный делитель.

Floyd's cycle detection (черепаха и заяц): x идёт по одному шагу, y - по два. Когда x = y (mod p), где p - делитель N, получаем gcd(|x-y|, N) > 1. Ожидаемое количество шагов: O(p^(1/2)) где p - наименьший простой делитель N. Если N = p*q (p ~ q ~ sqrt(N)), то O(N^(1/4)).

Решето числового поля (GNFS)

**General Number Field Sieve (GNFS)** - самый быстрый известный алгоритм факторизации для больших чисел. Работает за субэкспоненциальное время L(1/3, (64/9)^(1/3)). Именно от него зависит безопасность RSA: 2048-битный ключ RSA требует ~2^112 операций для GNFS.

L_n(alpha, c) = exp((c+o(1)) * (log n)^alpha * (log log n)^(1-alpha)) - субэкспоненциальная сложность. L(1) = экспоненциальная; L(0) = полиномиальная; L(1/2) = квадратичное решето; L(1/3) = GNFS. GNFS для 1024-битного N: ~10^30 операций. Для 2048-битного: ~10^48 операций - практически невозможно.

Алгоритмы дискретного логарифма

**Задача дискретного логарифма (DLP):** дано g, h в группе G, найти x: g^x = h. На этой задаче строится безопасность Diffie-Hellman и DSA. Сложность DLP зависит от группы: в Zp* - субэкспоненциально (Index Calculus); в E(Fp) - только экспоненциально (нет Index Calculus для кривых общего положения).

BSGS (Шэнкс, 1971): O(sqrt(|G|)) времени и памяти. Общий алгоритм для любой группы. Index Calculus (для Zp*): выбирает factor base {p1,...,pk}, логарифмы малых простых находит решением системы линейных уравнений. Для 2048-битного p: L(1/3) сложность - уязвимо аналогично RSA. Именно поэтому в DH нужны 2048-битные простые.

Ключевые идеи

• **B-гладкие числа** - основа квадратичного решета и GNFS; плотность Ψ(x,B)/x ≈ u^(-u) где u=log(x)/log(B)
• **rho Полларда** - O(N^(1/4)) факторизация через случайное блуждание и поиск цикла (Floyd)
• **GNFS** - субэкспоненциальный L(1/3) алгоритм; определяет практическую безопасность RSA
• **BSGS** - O(sqrt(|G|)) для DLP в любой группе; Index Calculus ускоряет до L(1/3) в Zp* но не в E(Fp)

Связанные темы

Вычислительная теория чисел - прямая основа современной криптографии:

• Тесты простоты — Алгоритмы факторизации и проверки простоты тесно связаны; часть факторизационных идей используется в тестах
• Числа в криптографии — RSA и DH безопасны именно потому, что факторизация и DLP вычислительно трудны
• Эллиптические кривые — ECDLP труднее DLP в Zp* - именно поэтому ECC даёт меньший ключ при той же безопасности

Вопросы для размышления

• GNFS взломал RSA-512 в 1999. Как оценить, когда будет взломан RSA-1024 и RSA-2048 - исходя из субэкспоненциального роста сложности?
• Алгоритм rho Полларда использует парадокс дней рождения. Как именно? Какую вероятностную интуицию стоит здесь иметь?
• Квантовый алгоритм Шора решает факторизацию и DLP за полиномиальное время. Что именно ломается в RSA, DH и ECC при появлении квантового компьютера?

Связанные уроки

• alg-33-randomized