Теория чисел для криптографии

Цели урока

• Понимать, как теорема о распределении простых обеспечивает практичность генерации RSA-ключей
• Объяснять асимметрию сложности умножения и факторизации, на которой стоит RSA
• Применять теоремы Ферма и Эйлера для вычислений в модульной арифметике
• Понимать роль функции Эйлера в генерации ключей RSA и почему её вычисление требует факторизации

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

• Modular Arithmetic

2048 бит. Именно такой RSA-ключ защищает HTTPS-соединение прямо сейчас. RSA-829 (829 бит) сломали в 2020 году - потребовалось 2700 ядро-лет вычислений. RSA-2048 стоит как скала. Между ними - не линейный, а субэкспоненциальный разрыв сложности. Математика, которая делает это возможным, живёт в одном уравнении: $n = p \cdot q$.

• **Генерация RSA-ключей** - каждый раз, когда браузер устанавливает HTTPS-соединение, сервер предъявляет сертификат с RSA-ключом, построенным на двух больших простых числах. Теорема о распределении простых гарантирует, что генерация занимает миллисекунды
• **Криптовалюты** - Bitcoin и Ethereum используют криптографию на эллиптических кривых, безопасность которой опирается на аналогичные задачи из теории чисел. Функция Эйлера и теорема Ферма лежат в основе арифметики конечных полей
• **Пост-квантовая криптография** - NIST в 2024 стандартизировал CRYSTALS-Kyber и CRYSTALS-Dilithium, потому что алгоритм Шора на квантовом компьютере ломает факторизацию за полиномиальное время

Ривест, Шамир, Адлеман - и письмо из прошлого

В 1977 году трое учёных из MIT опубликовали алгоритм RSA. Ривест придумал математику за одну ночь после вечеринки. Шамир и Адлеман провозились с доказательствами. Через неделю статья была готова. Годом ранее, в 1640-м, Пьер де Ферма записал свою теорему в письме - без доказательства. Эйлер доказал её через 100 лет. RSA воспользовался обеими через 337 лет. Теория чисел не знает срока годности.

Простые числа

Каждый HTTPS-запрос в браузере начинается с рукопожатия, где сервер предъявляет ключ RSA-2048. Этот ключ - произведение двух случайных простых чисел по 1024 бита. За последние 25 лет суперкомпьютеры сломали RSA-768 (2009, 2 года вычислений) и RSA-829 (2020, 2700 ядро-лет). RSA-2048 - нетронут. Фундамент: простые числа и их свойства.

Простое число - натуральное число больше 1, которое делится только на 1 и на себя. **Основная теорема арифметики**: каждое натуральное число больше 1 раскладывается на простые множители единственным образом. 84 = 2 * 2 * 3 * 7 - и никак иначе. Простые числа - атомы целых чисел. Вся криптография с открытым ключом живёт на их свойствах.

Сколько существует простых чисел? Бесконечно - Евклид доказал это более 2300 лет назад. **Теорема о распределении простых** (1896): количество простых до числа n приблизительно n / ln(n). Среди 1024-битных чисел каждое 710-е - простое (ln(2^1024) ~ 710). Генерировать случайные большие простые - практичная задача: берём случайное нечётное число нужной длины и проверяем тест Миллера-Рабина.

**Тест Миллера-Рабина - вероятностная проверка на простоту:** Детерминированная проверка (перебор делителей до sqrt(n)) невозможна для 1024-битных чисел - слишком много делителей. Вместо этого используется тест Миллера-Рабина: 1. Выбираем случайное a в диапазоне [2, n-2] 2. Проверяем определённое свойство a относительно n 3. Если свойство нарушено - n составное (100% уверенность) 4. Если свойство выполнено - n **вероятно** простое Каждый раунд уменьшает вероятность ошибки в 4 раза. После 40 раундов вероятность ошибки < 2^(-80) - намного меньше вероятности аппаратного сбоя.

В реальных криптографических библиотеках (OpenSSL, libsodium) генерация простых включает дополнительные проверки: число не должно быть слишком близко к другому простому (защита от атаки Ферма), а p-1 должно иметь большой простой множитель (защита от алгоритма Полларда p-1). От качества этих чисел зависит безопасность каждого сгенерированного RSA-ключа.

Факторизация

Умножение двух 1024-битных простых занимает микросекунды. Обратная задача - найти эти множители по их произведению - не имеет известного эффективного алгоритма для классических компьютеров. Эта **асимметрия сложности** (легко в одну сторону, трудно в обратную) - фундамент безопасности RSA. Заметьте: не невозможна, а практически неосуществима.

**Метод Полларда rho** использует парадокс дней рождения: случайная последовательность x_(i+1) = x_i^2 + 1 mod n образует цикл, и точка входа в цикл связана с делителем n. Сложность - O(n^(1/4)), что радикально быстрее пробного деления, но всё ещё экспоненциально для RSA-размерных чисел. Переход от пробного деления к Полларду - от экспоненты к четвёртому корню. Переход к GNFS - от корня к субэкспоненте. Каждый шаг - революция.

**RSA Factoring Challenge - соревнование в факторизации:** RSA Laboratories публиковали числа-задания: - **RSA-129** (426 бит, 1977) - факторизовано в 1994, 17 лет - **RSA-768** (768 бит, 2009) - 2 года на кластере из сотен машин - **RSA-250** (829 бит, 2020) - ~2700 ядро-лет вычислений - **RSA-2048** (2048 бит) - **не факторизовано**, приз 200 000 долларов Оценка для RSA-2048: ~2^112 операций методом GNFS. При 10^18 операций/сек это ~10^15 лет - в 100 000 раз больше возраста Вселенной. Факторизация - не невозможна, а **практически неосуществима** при достаточном размере ключа.

Важно различать: **проверку на простоту** (дано n, простое ли оно?) и **факторизацию** (дано n, каковы его множители?). Проверка на простоту - в классе P (полиномиальный алгоритм AKS, 2002). Факторизация - предположительно сложнее, но формально не доказано, что она не в P. Именно это «предположительно» - ахиллесова пята RSA: если кто-то найдёт быстрый алгоритм факторизации, цифровой мир рухнет. За десятилетия исследований никто не приблизился к этому.

Малая теорема Ферма и теорема Эйлера

**Малая теорема Ферма** (1640): если p - простое и a не делится на p, то $a^{p-1} \equiv 1 \pmod{p}$. Например: $2^6 = 64 \equiv 1 \pmod{7}$. Или $3^4 = 81 \equiv 1 \pmod{5}$. Эта теорема - не курьёз. Она лежит в основе быстрого возведения в степень, тестов на простоту и доказательства корректности RSA. Ферма написал её в 1640 году - в письме на полях. Доказательства у него не было.

Малая теорема Ферма работает только для простых модулей. В RSA модуль n = p*q - составной. **Теорема Эйлера** обобщает Ферма на любой модуль: если gcd(a, n) = 1, то $a^{\varphi(n)} \equiv 1 \pmod{n}$, где $\varphi(n)$ - функция Эйлера. Для простого p: $\varphi(p) = p-1$, и теорема Эйлера превращается в теорему Ферма. Для n = p*q: $\varphi(n) = (p-1)(q-1)$ - это значение напрямую участвует в генерации ключей RSA.

**Числа Кармайкла - ловушка для теста Ферма:** Тест Ферма на простоту: если $a^{n-1} \not\equiv 1 \pmod{n}$, то n точно составное. Но существуют составные числа, которые проходят тест Ферма для ВСЕХ a! Это **числа Кармайкла**: 561 = 3 * 11 * 17 - наименьшее. Для любого a с gcd(a, 561) = 1 выполняется $a^{560} \equiv 1 \pmod{561}$. Поэтому простой тест Ферма ненадёжен - нужен тест Миллера-Рабина, который обнаруживает составные числа с вероятностью >= 3/4 за каждый раунд, включая числа Кармайкла.

**Быстрое возведение в степень по модулю** - операция pow(a, e, n) в Python - использует метод «возведения в квадрат и умножения» (square-and-multiply), сводя вычисление $a^e \bmod n$ к $O(\log e)$ умножениям. Теорема Эйлера позволяет сначала уменьшить показатель: $a^e \bmod n = a^{e \bmod \varphi(n)} \bmod n$ при gcd(a, n) = 1. Это критически важно для RSA, где показатели степеней имеют тысячи бит.

Функция Эйлера

**Функция Эйлера $\varphi(n)$** - количество целых чисел от 1 до n, взаимно простых с n. $\varphi(12) = 4$, потому что только 4 числа из {1, 2, ..., 12} взаимно просты с 12: это {1, 5, 7, 11}. Для простого p: $\varphi(p) = p - 1$, потому что все числа от 1 до p-1 взаимно просты с p. Именно функция Эйлера связывает теорему Эйлера с практикой RSA. Без неё RSA - просто набор операций без объяснения, почему шифрование обратимо.

Почему $\varphi(p \cdot q) = (p-1)(q-1)$? Из n = pq чисел нужно вычесть те, что НЕ взаимно просты с n. Не взаимно просты числа, делящиеся на p (их q штук) или на q (их p штук). Число pq делится на оба - учли дважды. По формуле включений-исключений: $\varphi(n) = n - q - p + 1 = (p-1)(q-1)$. Эта формула **критически важна**: зная факторизацию, вычислить $\varphi(n)$ - просто. Не зная её - так же сложно, как факторизовать n.

**Вычисление phi(n) без факторизации - невозможно?** Зная phi(n) и n, легко найти p и q: - $\varphi(n) = n - p - q + 1$, значит $p + q = n - \varphi(n) + 1$ - Зная сумму и произведение p и q, решаем квадратное уравнение: $x^2 - (p+q) \cdot x + n = 0$ Поэтому вычисление $\varphi(n)$ **эквивалентно по сложности** факторизации n. Если бы существовал быстрый способ найти $\varphi(n)$ без знания p и q, RSA был бы взломан.

**Функция Эйлера - это мост между теорией чисел и RSA.** Без $\varphi(n)$ невозможно вычислить закрытый ключ d (d = e^(-1) mod phi(n)). Знание $\varphi(n)$ требует знания факторизации. Факторизация - вычислительно неосуществима. Эта цепочка зависимостей и есть математический фундамент, на котором стоит безопасность банковских транзакций, электронной почты и медицинских записей.

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

• **Простые числа - атомы арифметики:** основная теорема гарантирует единственность разложения, а теорема о распределении (~n/ln(n)) обеспечивает достаточную плотность даже среди 1024-битных чисел - генерация занимает миллисекунды благодаря тесту Миллера-Рабина
• **Факторизация - вычислительный барьер RSA:** лучший классический алгоритм (GNFS) субэкспоненциален, RSA-2048 потребует ~2^112 операций. Проверка простоты - в классе P, факторизация - предположительно нет. Эта асимметрия - фундамент криптографии с открытым ключом
• **Теоремы Ферма и Эйлера - математический мотор RSA:** $a^{\varphi(n)} \equiv 1 \pmod{n}$ гарантирует, что шифрование обратимо: $m^{e \cdot d} \equiv m \pmod{n}$. Числа Кармайкла - причина, почему для тестирования простоты нужен Миллер-Рабин, а не тест Ферма
• **Функция Эйлера - замковый камень:** $\varphi(pq) = (p-1)(q-1)$ используется для вычисления закрытого ключа $d = e^{-1} \bmod \varphi(n)$, а вычисление $\varphi(n)$ без факторизации эквивалентно взлому RSA

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

Теория чисел - математический фундамент асимметричной криптографии, связывающий абстрактную алгебру с практической безопасностью:

• Математика RSA — Прямое применение всех четырёх концепций: простые числа для генерации ключей, функция Эйлера для вычисления закрытого ключа, теорема Эйлера для доказательства корректности
• Модулярная арифметика — Предыдущий урок заложил основу: операции mod, НОД, мультипликативный обратный. Теория чисел надстраивает свойства простых и функцию Эйлера
• Математика эллиптических кривых — Альтернатива RSA на другой структуре из теории чисел - группе точек на эллиптической кривой. Если RSA опирается на сложность факторизации, ECC - на сложность дискретного логарифма
• Квантовая угроза — Алгоритм Шора разрушает сложность факторизации, сводя её к полиномиальной на квантовом компьютере

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

• Безопасность RSA основана на предположении, что факторизация вычислительно сложна - но это не доказано математически. Как оценивать риск того, что кто-то найдёт полиномиальный алгоритм?
• Тест Миллера-Рабина - вероятностный. Допустимо ли в криптографии использовать вероятностные алгоритмы, или нужен только детерминированный AKS?
• Функция Эйлера phi(n) содержит всю информацию о факторизации n. Если бы существовал оракул, мгновенно вычисляющий phi(n), какие ещё криптосистемы кроме RSA были бы взломаны?

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

• nt-01 — Теория чисел - фундамент модулярной арифметики RSA
• nt-02 — Расширенный алгоритм Евклида вычисляет обратный элемент mod phi(n)
• sec-03 — Аутентификация через JWT опирается на RSA/ECDSA подписи
• bc-03-merkle — Блокчейн использует ту же криптографию на эллиптических кривых
• dm-01 — Дискретная математика - общий язык для теоремы Ферма и теории групп
• alg-01 — Big-O анализ объясняет почему GNFS субэкспоненциален
• qc-01 — Алгоритм Шора на квантовом компьютере ломает факторизацию за полином
• nt-03