# Как математика защищает данные: разбор алгоритмов RSA и CRT

Источник: https://www.youtube.com/watch?v=hRDOmMEZtPo
Канал: MIT OpenCourseWare
Опубликовано: 22.07.2025

---

В Массачусетском технологическом институте (MIT) в рамках фундаментального учебного курса 6.1200 прошла лекция Бринмора Чепмена, посвященная глубокому применению теории чисел в компьютерной безопасности. Преподаватель подробно разобрал эволюцию криптографических методов от простейшего шифра Цезаря до современных асимметричных систем, ежедневно защищающих глобальные информационные сети. Особое внимание было уделено математическим основаниям защиты данных, включая малую теорему Ферма и Китайскую теорему об остатках.

## 🔐 Защита информации в ненадежных каналах
[[JUMP:0:00]]

Теория чисел, включающая в себя изучение наибольшего общего делителя (НОД) и модульной арифметики, лежит в основе всей современной безопасности компьютерных систем. Каждый раз, когда рядовой пользователь совершает онлайн-транзакцию по кредитной карте, запускаются сложные алгоритмы криптографии, защищающие транзакцию от компрометации. Бринмор Чепмен определяет криптографию как науку и искусство защиты информации, передаваемой по открытым и изначально ненадежным каналам связи.

Для наглядной иллюстрации базовой модели взаимодействия на лекции используется классический академический сценарий с вымышленными персонажами: Алисказамом (Alicekazam) и Бобзавром (Bobsaur). В идеальном мире Алисказам отправляет Бобзавру конфиденциальное сообщение (в шуточном примере лектора — праздничный пирог в честь Дня числа Пи) по почте, и получатель успешно извлекает его из конверта. Однако в реальных условиях в процесс коммуникации всегда может вмешаться третья сторона.

Лектор выделяет две ключевые угрозы со стороны гипотетического перехватчика и злоумышленника по имени Иви (Eevee):

* Пассивное подслушивание, при котором Иви незаметно перехватывает чужие письма в пути, полностью копирует их содержимое для себя и отправляет дальше Бобзавру, оставаясь незамеченной.
* Активное деструктивное вмешательство, когда злоумышленник не просто читает, но и полностью подменяет текст перехваченного сообщения до того, как его получит финальный адресат.

Традиционным историческим решением этой проблемы является использование симметричного шифрования. Собеседники должны заранее сгенерировать и разделить между собой общий секретный ключ, который выглядит как абсолютно случайный набор данных и принципиально трудно поддается угадыванию посторонними. В этой схеме секретное сообщение помещается в условный прочный ящик, запереть и отпереть который можно только данным уникальным ключом. Главная фундаментальная сложность классической схемы заключается в необходимости организации абсолютно безопасной первоначальной передачи ключа между участниками без перехвата в пути.

## 📜 Эволюция шифров: от древности до технического краха Enigma
[[JUMP:7:14]]

Исторически первыми криптографическими схемами были исключительно симметричные алгоритмы. Известнейшим примером является древнеримский шифр Цезаря, суть которого заключается в индивидуальном сдвиге каждой буквы исходного сообщения ровно на три позиции вперед по алфавиту. Главным критическим недостатком этого подхода, по мнению Чепмена, является полное отсутствие реального ключа, из-за чего вся безопасность строится исключительно на секретности самого метода. Как только один из легионов или генералов перейдет на сторону врага и раскроет алгоритм, вся переписка империи мгновенно окажется дешифрованной.

Более продвинутой модификацией стал универсальный сдвиг Цезаря, где конкретная величина смещения $k$ уже выступает в роли секретного ключа. Однако такая система легко взламывается прямо на занятии простым перебором всех 26 вариантов алфавита. Наличие в тексте одиночных букв или часто встречающихся коротких слов позволяет криптоаналитику моментально вычислить истинный ключ даже без автоматизированных систем.

Попытки усложнить шифрование в Средние века привели к созданию подстановочных шифров на основе случайных перестановок алфавита. Несмотря на значительное расширение пространства ключей, этот метод без труда компрометируется с помощью частотного анализа. Подсчитав частоту появления символов в зашифрованном массиве, можно сопоставить самые популярные знаки с наиболее употребительными буквами естественного языка.

В ХХ веке вершиной инженерной мысли стала немецкая военная шифровальная машина Enigma, активно использовавшаяся во Второй мировой войне. Она динамически перестраивала внутреннюю перестановку букв при вводе каждого нового символа, что эффективно защищало ее от стандартного частотного анализа. Тем не менее, союзники в Блетчли-парке смогли взломать Enigma, применив атаку на основе известного открытого текста. Зная контекст передаваемых сообщений (например, ежедневные утренние метеосводки) и фиксированные фразы, криптоаналитики успешно сужали пространство поиска и реконструировали секретные ключи, определяемые немцами на каждые сутки.

Бринмор Чепмен классифицирует немецкий подход как «криптографию тщеславия» (cryptography by hubris). Немецкие инженеры исходили из высокомерного допущения, что они умнее всех на планете, и если они сами не могут увидеть изъян в алгоритме, то это не удастся больше никому. Современная наука, напротив, полностью отказалась от этого принципа и стремится доказывать безопасность систем на основе строгих математических предположений.

## 🔑 Асимметричная криптография и создание системы RSA
[[JUMP:18:28]]

Настоящей концептуальной революцией в защите данных стало появление систем с открытым ключом. Математический алгоритм RSA изначально изобрел Клиффорд Кокс (Clifford Cocks), работавший на британскую службу правительственной связи. Из-за специфики ведомства его исследование было глубоко засекречено почти на четверть века. Параллельно и независимо аналогичную схему разработали ученые MIT Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman), получившие в итоге всемирное признание и престижную премию Тюринга. Чепмен иронично резюмирует эту историческую несправедливость шутливым советом никогда не работать на правительственные структуры.

В отличие от приватных систем, асимметричная криптография оперирует парой математически связанных ключей:

* Публичный ключ ($K_P$) — доступен абсолютно любому внешнему наблюдателю и используется исключительно для шифрования сообщений.
* Секретный ключ ($K_S$) — хранится в строгой тайне владельцем и применяется только для операции расшифровки.

Процесс шифрования преобразует исходное сообщение $M$ с помощью публичного ключа в шифротекст $C$, а алгоритм дешифрования восстанавливает $M$, используя секретный ключ. Преподаватель приводит понятную аналогию с электронной почтой Gmail: публичный ключ — это ваш открытый адрес, на который любой желающий может направить письмо, а секретный ключ — это личный секретный пароль, без ввода которого прочесть входящие сообщения технически невозможно.

## 🧮 Математическая модель и доказательство корректности RSA
[[JUMP:22:47]]

В основе корректности RSA лежит Малая теорема Ферма (FLT). Задача разработчиков системы — подобрать такие параметры $e$, $d$ и $n$, чтобы последовательное возведение сообщения сначала в степень шифрования $e$, а затем в степень дешифрования $d$ гарантированно возвращало исходный текст по модулю $n$. Математически это выражается конгруэнцией:

$$(m^e)^d \equiv m \pmod n $$

Согласно Малой теореме Ферма, для любого простого числа $p$ выполняется соотношение $m^{p-1} \equiv 1 \pmod p$, откуда прямо следует, что $m^p \equiv m \pmod p$. Если попытаться построить простейшую модель на одном простом числе $p$, то для выполнения равенства $m^{ed} \equiv m \pmod p$ необходимо выбрать показатели так, чтобы $ed \equiv 1 \pmod{p-1}$. Поскольку $m^{k(p-1)} \equiv 1$, выражение вида $ed = k(p-1) + 1$ гарантирует корректный результат дешифрования. На практике вычисление модульного инверсного значения $d$ для случайно выбранного числа $e$ осуществляется с помощью алгоритма «пульверизатора» (расширенного алгоритма Евклида).

Однако схема с одним простым числом абсолютно ненадежна. Поскольку публичный ключ содержит пару $(p, e)$, любой злоумышленник может точно так же применить «пульверизатор» по модулю $p-1$ и мгновенно вычислить секретный шаг дешифрования $d$. Для устранения этой симметрии создатели RSA предложили использовать составной модуль $n$, равный произведению двух огромных случайных простых чисел $p$ и $q$. В этом случае «пульверизация» выполняется не по модулю $n-1$, а по значению функции Эйлера:

$$n' = (p-1)(q-1)$$

Для обоснования корректности обновленного алгоритма Чепмен развертывает строгое математическое доказательство. Пусть выполнено условие $ed \equiv 1 \pmod{(p-1)(q-1)}$, что означает делимость разности $ed-1$ на произведение $(p-1)(q-1)$. Следовательно, число $p-1$ также является делителем выражения $ed-1$, и мы можем записать $ed \equiv 1 \pmod{p-1}$. На основании Малой теоремы Ферма это дает нам равенство:

$$m^{ed} \equiv m \pmod p$$

В силу симметрии аналогичное утверждение справедливо и для второго простого числа: $m^{ed} \equiv m \pmod q$. Поскольку $p$ и $q$ являются взаимно простыми числами, из их независимого деления разности $m^{ed} - m$ логически следует, что их произведение $pq$ (то есть модуль $n$) также делит эту разность. Таким образом, доказано базовое тождество RSA для вычислений по составному модулю.

## 🛡️ Криптографическая стойкость против математического опыта
[[JUMP:48:43]]

Безопасность RSA строится на фундаментальном асимметричном допущении теории сложности: операция умножения двух простых чисел происходит практически мгновенно, в то время как обратная задача — разложение готового составного числа $n$ на множители $p$ и $q$ — является вычислительно сверхсложной для современных компьютеров. Для генерации реальных ключей выбираются случайные простые числа, содержащие сотни десятичных знаков. Публично публикуются только числа $n$ и $e$, тогда как секретные компоненты $p$, $q$ и $d$ остаются скрытыми от внешнего мира.

В ходе лекции один из студентов озвучил закономерный вопрос: не является ли упование на сложность факторизации очередным проявлением «криптографии тщеславия», аналогичным ошибкам создателей Enigma? Бринмор Чепмен категорически отвергает это сравнение.

По мнению Чепмена, в данном случае индустрия полагается не на самоуверенность отдельного инженера, а на коллективный многовековой опыт всего мирового математического сообщества. Лучшие умы человечества на протяжении сотен лет безуспешно пытались найти эффективный алгоритм разложения чисел на множители. Безусловно, теоретически существует риск, что кто-то уже изобрел быстрый метод факторизации и держит его в секрете, однако базовое консенсусное допущение ученых состоит в том, что задача факторизации действительно трудна для вычисления.

## 🏛️ Китайская теорема об остатках и оптимизация вычислений
[[JUMP:1:02:21]]

В финальной части лекции Чепмен демонстрирует еще одно важнейшее положение теории чисел, позволяющее существенно ускорить криптографические операции. Проводить вычисления по огромному составному модулю $n$ долго и ресурсоемко. Однако Китайская теорема об остатках (CRT) постулирует, что работа по модулю произведения двух взаимно простых чисел $pq$ математически эквивалентна параллельному ведению расчетов по отдельным модулям $p$ и $q$. Производить операции со значительно меньшими числами намного проще и быстрее.

Для иллюстрации лектор предлагает решить систему сравнений для некоторого $x < 55$:

$$x \equiv 4 \pmod 5$$
$$x \equiv 7 \pmod{11}$$

Самый очевидный и медленный путь — перебрать все целые числа от 0 до 55. Чепмен показывает более элегантный метод: сначала выписать все числа, удовлетворяющие второму, более жесткому условию по модулю 11 в заданном диапазоне — это множество $\{7, 18, 29, 40, 51\}$. После этого остается проверить всего пять кандидатов на соответствие первому условию (остаток 4 при делении на 5). Единственным верным и уникальным решением оказывается число 29.

Обобщенная формулировка Китайской теоремы об остатках гласит: если $p$ и $q$ взаимно просты, то для любых целых чисел $a$ и $b$ существует единственное решение системы конгруэнций по модулю $pq$.

Конструктивное доказательство существования решения строится через поиск модульных инверсий. Определим $p^{-1}$ как модульное обратное к $p$ по модулю $q$, и зададим вспомогательное число $e_q = p \cdot p^{-1}$. По определению, $e_q \equiv 0 \pmod p$ (так как кратно $p$) и $e_q \equiv 1 \pmod q$. Если рассмотреть частный случай, где $a=0$, то искомым решением будет $x = b \cdot e_q$, поскольку оно обнуляется по модулю $p$ и дает остаток $b$ по модулю $q$.

Для общего случая аналогично конструируется число $e_p$ (кратное $q$ и дающее 1 по модулю $p$), после чего финальное решение собирается в виде линейной комбинации:

$$x = a \cdot e_p + b \cdot e_q$$

Чепмен завершает лекцию строгим доказательством единственности этого решения. Если предположить наличие двух различных решений $x$ и $x'$, то оба они должны давать одинаковые остатки $a$ и $b$ по соответствующим модулям. Из этого логически следует, что их разность $x - x'$ одновременно делится и на $p$, и на $q$. Поскольку $p$ и $q$ взаимно просты, их произведение $pq$ также обязано делить разность $x - x'$, что математически доказывает конгруэнтность и тождественность двух решений по модулю $pq$.