Модулярная арифметика

Цели урока

• Понимать операции по модулю и алгоритм square-and-multiply
• Применять алгоритм Евклида для нахождения GCD и обратных элементов
• Использовать мультипликативный обратный для понимания RSA
• Применять CRT для оптимизации криптографических вычислений

RSA-2048 стоит на одной теореме Эйлера 1736 года. Тысячи HTTPS-соединений в секунду - модульная арифметика. Bitcoin-кошелёк - эллиптическая кривая над конечным полем. Вся современная криптография - модульная арифметика со сложными числами.

• **RSA шифрование** - каждое HTTPS-соединение: браузер вычисляет m^e mod n с 2048-битными числами за миллисекунды благодаря square-and-multiply
• **TLS handshake** - 10-50 мс включают несколько модулярных возведений в степень с 2048-битными числами
• **RSA-CRT в OpenSSL** - расшифровка в 4 раза быстрее: сервер с 10K TLS-соединений/сек без CRT просто не справился бы с нагрузкой
• **Генерация ключей** - при создании RSA-ключа расширенный Евклид находит d = e^(-1) mod phi(n): без обратного элемента расшифровка невозможна
• **Bitcoin ECDSA** - подпись транзакции: скалярное умножение точки на кривой mod p_secp256k1 (256-битное простое число)
• **AES в GF(2^8)** - SBox и MixColumns работают в поле Галуа mod неприводимого многочлена - та же модульная арифметика, другая структура

Леонард Эйлер и теорема, на которой стоит RSA

В 1736 году Эйлер публикует «Theorema arithmeticum» - обобщение малой теоремы Ферма на составные числа. Теорема Эйлера: для любого a взаимно простого с n, a^phi(n) = 1 (mod n), где phi(n) - функция Эйлера (количество взаимно простых с n чисел от 1 до n). В 1977 году Ривест, Шамир и Адлеман показали: теорема 1736 года превращается в систему шифрования RSA. Ни Эйлер, ни тем более современники не могли представить, что «чистая математика» через 240 лет защитит триллионы долларов транзакций ежедневно.

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

• Введение в криптографию

Операции по модулю

RSA-2048 стоит на одной теореме Эйлера 1736 года. Тысячи HTTPS-соединений в секунду - модульная арифметика. Bitcoin-кошелёк - эллиптическая кривая над конечным полем. Вся современная криптография - числа, которые сбрасываются по кругу. **a mod n** - остаток от деления a на n. 15 mod 12 = 3: число обернулось, как стрелка на циферблате. Модуль в криптографии - не 12, а 2048-битное простое число.

Ключевое свойство: **остаток можно брать на каждом шаге**. (a + b) mod n = ((a mod n) + (b mod n)) mod n. То же для умножения. Это означает: промежуточные результаты никогда не вырастают до гигантских размеров. RSA работает с 2048-битными числами - без этого свойства арифметика была бы вычислительно невозможной.

**Свойства mod-арифметики:** - Ассоциативность, коммутативность, дистрибутивность - как в обычной - Замкнутость: результат всегда в [0, n-1] - Деление - НЕ как в обычной: нельзя просто разделить, нужен мультипликативный обратный

**Модулярное возведение в степень** - операция, на которой держится RSA. Шифрование: c = m^e mod n. Наивный подход (сначала m^e, потом mod n) невозможен: m^e при e = 65537 - число с миллионами цифр. Алгоритм **square-and-multiply** берёт остаток на каждом шаге, держа числа маленькими. O(log e) умножений вместо O(e).

`pow(base, exp, mod)` - рабочая лошадка криптографии. O(log exp) вместо O(exp). Разница: pow(2, 10^6, n) - 20 итераций, мгновенно. 2^(10^6) - число с 301030 цифрами, только хранение требует сотни килобайт. Каждая операция RSA, Diffie-Hellman, DSA сводится к одному вызову этой функции.

GCD и алгоритм Евклида

300 год до нашей эры. Евклид записывает алгоритм нахождения наибольшего общего делителя. 2300 лет спустя этот же алгоритм запускается в каждой криптографической библиотеке при генерации RSA-ключей. Не потому что нет ничего лучше - а потому что GCD(a, b) = GCD(b, a mod b) безупречен. **GCD(a, n) = 1** означает: числа взаимно просты - и обратный элемент существует.

Гениальность алгоритма - в рекурсии: GCD не уменьшает числа линейно, а сжимает их геометрически через mod. Два числа по 2048 бит - 2048 шагов. Полный перебор делителей был бы 2^2048 шагов - то есть никогда.

**Расширенный алгоритм Евклида и тождество Безу:** Для любых a и b существуют x и y: **a * x + b * y = GCD(a, b)** Если GCD(a, n) = 1, то a * x + n * y = 1, значит a * x = 1 (mod n). Иными словами, x - **мультипликативный обратный** к a. Расширенный Евклид - главный инструмент нахождения обратных элементов.

**Взаимная простота** (coprimality) - центральное понятие для криптографии. GCD(8, 15) = 1 - взаимно просты, хотя ни 8, ни 15 не простые. В RSA: открытая экспонента e обязана быть взаимно простой с phi(n). Если нет - обратный элемент не существует, расшифровка невозможна.

Мультипликативный обратный

В обычной арифметике обратный к 5 - это 1/5. В модулярной дробей нет. Но идея та же: **мультипликативный обратный** a^(-1) mod n - это число, при умножении на которое a даёт 1. 3 * 5 = 15 mod 7 = 1: обратный к 3 по модулю 7 - это 5. Без этого понятия нет расшифровки RSA.

Два метода нахождения обратного: **расширенный Евклид** (для любого модуля) и **малая теорема Ферма** (только для простого p). Теорема Ферма: если p - простое, то a^(p-1) = 1 (mod p), значит a^(-1) = a^(p-2) mod p. Коротко и лаконично.

**Малая теорема Ферма (Fermat's Little Theorem):** Если p - простое и p не делит a, то: a^(p-1) = 1 (mod p) Следствие: a^(-1) = a^(p-2) (mod p) Пример: обратный к 3 по модулю 7 3^5 = 243, 243 mod 7 = 5 Проверка: 3 * 5 = 15 mod 7 = 1 Работает ТОЛЬКО когда модуль - простое число.

В RSA мультипликативный обратный - сердце алгоритма. Открытый ключ: e. Закрытый ключ d = e^(-1) mod phi(n). Шифрование: c = m^e mod n. Расшифровка: m = c^d mod n. Это работает именно потому, что e*d = 1 (mod phi(n)). Без обратного элемента расшифровка была бы математически невозможна.

Китайская теорема об остатках (CRT)

III век н.э. Китайский математик Сунь Цзы задаёт задачу: число при делении на 3 даёт остаток 2, на 5 - остаток 3, на 7 - остаток 2. Найти число. Решение - 23. Этот результат вырос в **Китайскую теорему об остатках**: при попарно взаимно простых модулях система сравнений имеет единственное решение. В XXI веке - это оптимизация RSA в 4 раза.

Алгоритм CRT: M = произведение всех модулей. Для каждого m_i вычислить M_i = M / m_i и обратный y_i = M_i^(-1) mod m_i. Решение: x = (sum r_i * M_i * y_i) mod M. Обратные всегда существуют - модули взаимно просты по условию.

**CRT в RSA: расшифровка в 4 раза быстрее** RSA: m = c^d mod n, где n = p * q (2048 бит). Прямое возведение в степень - медленно. RSA-CRT: 1. m_p = c^(d mod (p-1)) mod p (вычисление mod 1024-битного p) 2. m_q = c^(d mod (q-1)) mod q (вычисление mod 1024-битного q) 3. Собрать через CRT Почему 4x? Стоимость возведения в степень пропорциональна квадрату длины: 2 * (k/2)^2 = k^2/2 вместо k^2. Плюс экспоненты вдвое короче. Итого ~4x. Все реальные TLS-реализации используют RSA-CRT.

На сервере с тысячами TLS-соединений в секунду RSA-CRT - не оптимизация, а условие выживания. OpenSSL, BoringSSL, LibreSSL - все реализуют CRT по умолчанию. Алгоритм Гарнера (инкрементальное восстановление через один предвычисленный обратный элемент) - индустриальный стандарт.

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

• **Операции по модулю:** числа оборачиваются после модуля - как стрелка на циферблате. pow(base, exp, mod) - O(log exp), держит промежуточные числа маленькими. Без этого RSA вычислительно невозможен
• **Алгоритм Евклида 300 г. до н.э.:** GCD(a, b) = GCD(b, a mod b) - O(log n) шагов. Расширенная версия даёт коэффициенты Безу и напрямую находит мультипликативный обратный
• **Мультипликативный обратный:** a^(-1) mod n существует тогда и только тогда, когда GCD(a, n) = 1. Закрытый ключ RSA d = e^(-1) mod phi(n) - обратный к открытому e
• **CRT:** система с попарно взаимно простыми модулями имеет единственное решение. RSA-CRT ускоряет расшифровку в 4 раза - это алгебра III века н.э. в каждом OpenSSL
• **Теорема Эйлера 1736** - математический фундамент RSA. «Чистая математика» 240-летней давности защищает интернет-транзакции ежедневно

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

Модулярная арифметика - фундамент всей криптографической математики:

• Теория чисел — Теорема Эйлера обобщает малую теорему Ферма на составные модули - критично для RSA
• RSA: математические основы — RSA напрямую использует все четыре концепции: mod-возведение, Евклид, обратный элемент, CRT
• Алгебраические структуры — Остатки по модулю образуют кольцо, при простом n - поле: обратный существует для всех ненулевых
• Эллиптические кривые: математика — ECC: координаты точек и операции над кривой - всё по модулю большого простого числа

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

• Почему деление в модулярной арифметике требует обратного элемента вместо прямого деления? Что именно 'ломается' при делении остатков?
• Алгоритм Евклида существует 2300 лет и не изменился. Какие свойства делают его оптимальным для криптографических библиотек?
• Если CRT даёт 4x ускорение для RSA-2048, почему нельзя разбить на больше множителей и получить 8x? Какие ограничения безопасности это создаёт?

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

• crypto-03-number-theory — Теорема Эйлера и квадратичные вычеты строятся поверх mod-арифметики
• crypto-24-rsa-math — RSA - прямое применение всех четырех концепций урока
• crypto-26-ecc-math — ECC работает в полях mod p - та же арифметика, другая структура
• ar-28-modular — Модулярная арифметика в общем контексте теории чисел
• alg-01-big-o — O(log n) сложность алгоритмов - base для понимания быстроты square-and-multiply
• bc-02-hashing — Хеш-функции и mod-операции - оба инструмента односторонности в криптографии
• dm-14