Арифметика остатков и шифры

Прошлая глава закончилась загадкой: как двум людям договориться о секретном ключе, если весь их разговор слышат посторонние? Ваш телефон решает её каждый день. Откройте сайт своего банка. Между телефоном и сервером банка — Wi-Fi в кафе, провайдер, десяток маршрутизаторов в разных странах, и любой из них может записать каждый бит, который вы отправили. С банком вы никогда не встречались и пароль для шифрования заранее не обговаривали. И всё же за долю секунды телефон и сервер договариваются о секретном ключе, а тот, кто подслушал их разговор от первого бита до последнего, вычислить этот ключ не может.

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

Эта глава — мастерская шифровальщика. Мы соберём несколько шифров, от колеса Цезаря до RSA, и каждый попробуем взломать. Между шифрами будем точить инструменты: сравнения, обратные элементы, теоремы Ферма и Эйлера, китайскую теорему об остатках. В конце ответим на пятый большой вопрос курса: как работает шифр, который защищает ваш банк.

Колесо Цезаря

Светоний рассказывает, что Юлий Цезарь в секретных письмах заменял каждую букву третьей по счёту после неё: вместо A писал D, вместо B — E. Сделаем такой шифр для русского алфавита. Пронумеруем буквы с нуля: $А = 0$, $Б = 1$, …, $Я = 32$. Зашифровать — прибавить к номеру буквы три. Слово ЦЕЗАРЬ превращается в ЩЗКГУЯ.

Заминка случается в конце алфавита. У буквы Я номер $32$, и $32 + 3 = 35$, а такой буквы нет. Естественно начать алфавит заново, как стрелка часов после двенадцати: $35$ превращается в $35 - 33 = 2$, то есть в В. Алфавит свернулся в колесо из $33$ делений. На этом колесе $32 + 3 = 2$. Ошибки тут нет: это другая арифметика, в которой числа, отличающиеся на $33$, считаются одинаковыми.

Первое число — любое целое, в том числе отрицательное. Второе число. Обычно в роли $b$ выступает остаток — единственное число от $0$ до $n - 1$, сравнимое с $a$. Модуль, «число делений» циферблата. Знак $\mid$ читается «делит». Пример: $35 \equiv 2 \pmod{33}$, потому что $35 - 2 = 33$. Шаг назад от буквы А приводит к Я: $-1 \equiv 32 \pmod{33}$. По модулю $12$ сравнимы $15$ и $3$ — пятнадцать часов это три часа дня.

Два числа сравнимы по модулю $n$ ровно тогда, когда у них одинаковые остатки при делении на $n$. Это мы доказали в главе 4, в лемме об остатках. Знак $\equiv$ и само слово «сравнение» ввёл Гаусс в «Арифметических исследованиях» (1801). До него то же самое писали словами, а с новым значком оказалось, что со сравнениями можно обращаться почти как с равенствами.

Со сложением в $\mathbb Z_n$ мы уже встречались: в главе о группах это был циферблат, циклическая группа. Шифр Цезаря — прибавление ключа $k$ в этой группе, $y = x + k$, а расшифровка — прибавление $-k$. Теперь добавим умножение, и для этого нужна одна теорема: сравнения можно складывать и перемножать почленно, как равенства.

Идея: разность произведений $ab - a'b'$ — Г-образная полоса между двумя прямоугольниками, и её можно разрезать на два куска, у каждого из которых одна сторона кратна $n$.

Раз $a \equiv a'$ и $b \equiv b'$, разности $a - a'$ и $b - b'$ делятся на $n$. На чертеже $n = 3$: обе разности нарезаны на отрезки длины $3$. Произведение $ab$ — площадь большого прямоугольника, $a'b'$ — площадь маленького в его углу. Разность $ab - a'b'$ — Г-образная полоса. Разрежем её на два прямоугольника: верхний $a \times (b - b')$ и правый $(a - a') \times b'$. Отсюда тождество $ab - a'b' = a(b - b') + (a - a')b'$. Раскройте скобки — и оно проверится для любых целых чисел, а не только для положительных, как на картинке. У верхнего куска сторона $b - b'$ кратна $n$, у правого — сторона $a - a'$. Каждый кусок режется на полоски ширины $n$, так что площадь каждого делится на $n$. Значит, $n$ делит и сумму кусков $ab - a'b'$, то есть $ab \equiv a'b' \pmod n$. Со сложением ещё проще: $(a + b) - (a' + b') = (a - a') + (b - b')$ — сумма двух кратных $n$.

Практический вывод: в любом выражении из сложений, вычитаний и умножений числа можно заменять сравнимыми в любой момент, и ответ по модулю не изменится. Числа можно сокращать по дороге, не дожидаясь, пока они вырастут. Последняя цифра числа $7^{2026}$ — это его остаток по модулю $10$. Заметим, что $7^2 = 49 \equiv -1 \pmod{10}$, поэтому $7^4 \equiv (-1)^2 = 1$ и $7^{2026} = (7^4)^{506} \cdot 7^2 \equiv 1 \cdot 49 \equiv 9$. Число из тысячи семисот с лишним цифр оканчивается девяткой, и вычислять его не пришлось.

Признаки делимости из главы 4 на этом языке умещаются в строчку. Так как $10 \equiv 1 \pmod 9$, каждая степень десяти сравнима с единицей, и число сравнимо с суммой своих цифр. Так как $10 \equiv -1 \pmod{11}$, степени десяти по очереди сравнимы с $1$ и $-1$, отсюда знакочередующаяся сумма. «Веса разрядов» той главы — остатки степеней десяти.

Шифр Цезаря ломается за минуту: ключей всего $33$, и можно перепробовать все, пока не проступит осмысленный текст. Шифровальщики давно поняли, что ключей нужно много. Можно, например, шифровать умножением и сдвигом: $y \equiv ax + b \pmod{33}$. Это аффинный шифр, ключ в нём — пара $(a, b)$. Но умножение на циферблате ведёт себя непривычно. Посмотрите, как оно выглядит.

Кривые на круге красивы и сами по себе. При $m = 2$ хорды соединяют угол $\theta$ с углом $2\theta$, и их огибающая — кардиоида. При $m = 3$ получается нефроида: ту же кривую рисует на поверхности кофе солнечный свет, отражённый стенками чашки. Для шифра важнее маленький циферблат. При $n = 10$ и $m = 3$ стрелки переставляют точки: каждая получает ровно одну стрелку. При $m = 4$ половина точек не получает ни одной, зато другие получают по две. Шифр с таким множителем расшифровать нельзя: две разные буквы превращаются в одну.

Обратный ход

Чтобы расшифровать аффинный шифр $y \equiv ax + b$, надо выразить $x$: вычесть $b$ и «разделить на $a$». Делить на циферблате — значит умножать на такое число $a'$, что $a \cdot a' \equiv 1$. Для $a = 5$ по модулю $33$ оно есть: $5 \cdot 20 = 100 = 3 \cdot 33 + 1$. Значит, из $y \equiv 5x + 8$ следует $x \equiv 20(y - 8) \pmod{33}$. Буква Б ($x = 1$) шифруется в $5 + 8 = 13$, то есть в М, а обратно: $20 \cdot (13 - 8) = 100 \equiv 1$ — снова Б.

Доказательство заодно подсказывает, как считать. Обратный элемент находит расширенный алгоритм Евклида. Найдём обратный к $17$ по модулю $43$. Слева — прямой ход алгоритма, справа — обратный, как в задаче про кувшины:

$$\begin{aligned} 43 &= 2 \cdot 17 + 9, &\qquad 1 &= 9 - 8 \\ 17 &= 1 \cdot 9 + 8, & &= 9 - (17 - 9) = 2 \cdot 9 - 17 \\ 9 &= 1 \cdot 8 + 1, & &= 2 \cdot (43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17. \end{aligned}$$

Получилось $17 \cdot (-5) \equiv 1 \pmod{43}$, и обратный к $17$ — это $-5 \equiv 38$. Проверка: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$. По теореме Ламе алгоритм делает не больше пятикратного числа цифр делений, так что обратный элемент по модулю из шестисот цифр компьютер находит мгновенно.

Особенно хорош простой модуль. Если $p$ простое, каждое число от $1$ до $p - 1$ взаимно просто с $p$ и потому обратимо. В $\mathbb Z_p$ можно делить на всё, кроме нуля, как в обычных дробях. Ненулевые остатки по простому модулю образуют группу по умножению, и дальше она будет нашим главным инструментом. Вернитесь к кругу выше: при простом $n$ любой множитель $m$ от $1$ до $n - 1$ переставляет точки.

Сколько решений среди остатков $0, 1, \dots, 9$ у сравнения $6x \equiv 4 \pmod{10}$?

Ни одного: $6$ не обратимо по модулю $10$ Ровно одно Два Десять

$6 \cdot 4 = 24 \equiv 4$ и $6 \cdot 9 = 54 \equiv 4$. Сравнение означает, что $10$ делит $6x - 4$, то есть $5$ делит $3x - 2$: $3x \equiv 2 \pmod 5$. Здесь тройка обратима ($3 \cdot 2 = 6 \equiv 1$), и $x \equiv 2 \cdot 2 = 4 \pmod 5$. По модулю $10$ это два остатка: $4$ и $9$. Если бы справа стояло нечётное число, решений не было бы совсем: $6x - c$ тогда нечётно и на $10$ не делится.

Аффинный шифр для латинского алфавита из $26$ букв умножает номер буквы на $7$. На что умножать при расшифровке? Найдите обратный к $7$ по модулю $26$ (число от $0$ до $25$).

$26 = 3 \cdot 7 + 5$, $7 = 1 \cdot 5 + 2$, $5 = 2 \cdot 2 + 1$. Обратный ход: $1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7$. Значит, $7^{-1} \equiv -11 \equiv 15 \pmod{26}$. Проверка: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$.

Степени ходят по кругу

Сложение по модулю дало шифр Цезаря, умножение — аффинный шифр. Следующая операция — возведение в степень, и с неё начинается настоящая криптография. Сначала посмотрим, как ведут себя степени. Остатки степеней тройки при делении на $7$: $3^1 = 3$, $3^2 = 9 \equiv 2$, $3^3 \equiv 2 \cdot 3 = 6$, $3^4 \equiv 6 \cdot 3 = 18 \equiv 4$, $3^5 \equiv 4 \cdot 3 = 12 \equiv 5$, $3^6 \equiv 5 \cdot 3 = 15 \equiv 1$. На шестом шаге мы вернулись к единице, и дальше всё повторится: $3^7 \equiv 3$, $3^8 \equiv 2$, … Степени ходят по кругу.

Поэтому $3^{100}$ по модулю $7$ считается в уме. Показатель важен только с точностью до шести: $100 = 6 \cdot 16 + 4$, и $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1 \cdot 4 = 4 \pmod 7$. Совпадение ли, что круг замкнулся на шестом шаге, когда модуль равен семи?

При любом простом $n$ последний столбец, $k = n - 1$, целиком состоит из единиц. Разные строки возвращаются к единице в разное время: $2^3 \equiv 1 \pmod 7$, а тройке нужно шесть шагов. Но к шагу $n - 1$ единица наступает во всех строках одновременно. Первым это заметил Пьер Ферма.

Ферма сообщил о ней в письме Френиклю де Бесси от 18 октября 1640 года и, по своему обыкновению, без доказательства: он прислал бы его, «если бы не боялся, что оно выйдет слишком длинным». Первым доказательство опубликовал Эйлер; он изложил его в 1736 году. В конце прошлой главы теорема получилась почти даром из теоремы Лагранжа. Здесь докажем её иначе, без групп, подсчётом бус. Такое доказательство напечатал Соломон Голомб в 1956 году, и оно короче, чем боялся Ферма.

Идея: пересчитать разноцветные бусы двумя способами. Покажем на $a = 2$ цветах и $p = 5$ бусинах; для любого натурального $a$ и простого $p$ рассуждение то же.

Выложим в ряд $p$ бусин, каждую одного из $a$ цветов. Разных рядов $a^p$: для каждой бусины есть $a$ вариантов. Здесь $2^5 = 32$ ряда. Отложим одноцветные ряды, в которых все бусины одинаковые. Их $a$, и осталось $a^p - a$ рядов, здесь $30$. Свяжем каждый оставшийся ряд в кольцо — ожерелье. Одно и то же ожерелье получается из $p$ рядов: разрезать кольцо можно в любом из $p$ мест, а это всё равно что циклически сдвигать ряд. Соберём ряды в группы по ожерельям. В каждой группе ровно $p$ разных рядов. Если бы два сдвига, на $i$ и на $j$ позиций, дали одинаковые ряды, то сдвиг на $s = j - i$ ($0 < s < p$) оставлял бы ряд на месте, а с ним и сдвиги на $2s, 3s, \dots$ Так как $p$ простое, $s$ обратимо по модулю $p$, и среди чисел $s, 2s, 3s, \dots$ есть сравнимое с $1$. Но ряд, который не меняется от сдвига на одну позицию, одноцветный, а одноцветные мы отложили. Неодноцветные ряды разбились на группы по $p$ штук, поэтому $p$ делит $a^p - a$: здесь $30 = 6 \cdot 5$. Это и есть $a^p \equiv a \pmod p$ для натурального $a$; при $a \le 0$ заменим $a$ сравнимым натуральным числом. Если $p$ не делит $a$, то $a$ обратимо по модулю $p$, и сравнение можно умножить на $a^{-1}$: $a^{p-1} \equiv 1$. Любое целое число, которое не делится на $p$. Показатель на единицу меньше модуля. Поэтому в степени $a^k$ по простому модулю показатель можно заменять его остатком от деления на $p - 1$. Простой модуль. Для составного модуля теорема в таком виде неверна: $2^{14} = 16\,384 \equiv 4 \pmod{15}$. Пример: $2^{100} \bmod 13$. Здесь $p - 1 = 12$ и $100 = 12 \cdot 8 + 4$, поэтому $2^{100} \equiv 2^4 = 16 \equiv 3 \pmod{13}$.

Как доказывал сам Эйлер: бином Ньютона

Доказательство Эйлера 1736 года короче бус, но опирается на формулу бинома. По дороге получается равенство, которое в главе 7 мы обещали объяснить: по простому модулю «неправильное» раскрытие скобок оказывается правильным.

Если $p$ простое, то $(a + b)^p \equiv a^p + b^p \pmod p$ для любых целых $a$ и $b$.

По формуле бинома $(a + b)^p = \sum_{k=0}^{p} \binom pk a^k b^{p-k}$. Крайние слагаемые, при $k = 0$ и $k = p$, — это $b^p$ и $a^p$. Покажем, что все остальные коэффициенты $\binom pk$ при $0 < k < p$ делятся на $p$. Они целые, и $\binom pk \cdot k!\,(p - k)! = p!$ делится на $p$. Число $k!\,(p - k)!$ — произведение чисел, меньших $p$, и ни одно из них на простое $p$ не делится, поэтому по лемме Евклида не делится на $p$ и их произведение. Значит, по той же лемме $p$ делит $\binom pk$, и средние слагаемые сравнимы с нулём.

Теперь малая теорема для натуральных $a$ — индукцией по $a$. При $a = 1$ верно: $1^p = 1$. Если $a^p \equiv a$, то по лемме $(a + 1)^p \equiv a^p + 1^p \equiv a + 1 \pmod p$. Значит, $a^p \equiv a$ для всех натуральных $a$, а для остальных целых — через сравнимое натуральное число.

Вернитесь к таблице при $n = 7$. В строке тройки встречаются все шесть ненулевых остатков, в строке двойки — только три: $2, 4, 1$. Наименьшее $k$, при котором $a^k \equiv 1$, называют порядком числа $a$ по модулю $n$; это порядок элемента в группе обратимых остатков из главы 40.

Для шифров нужны показатели в сотни цифр, и тут цикл не выручит: его длина тоже огромна. Выручает другое — степени можно считать очень быстро. Чтобы получить $3^{100}$, не нужно девяносто девять умножений. Возведём тройку в квадрат, результат ещё раз в квадрат и так далее: $3^2, 3^4, 3^8, 3^{16}, 3^{32}, 3^{64}$ — шесть умножений, и после каждого берём остаток, чтобы числа не росли. А так как $100 = 64 + 32 + 4$, то $3^{100} = 3^{64} \cdot 3^{32} \cdot 3^4$ — ещё два умножения.

Показатель, записанный в двоичной системе (глава 1). Единичные разряды двоичной записи. Каждая степень $a^{2^{k+1}}$ — квадрат предыдущей $a^{2^k}$, так что все они получаются цепочкой возведений в квадрат. Пример: $100 = 1100100_2 = 64 + 32 + 4$. По модулю $7$: $3^2 \equiv 2$, $3^4 \equiv 4$, $3^8 \equiv 2$, $3^{16} \equiv 4$, $3^{32} \equiv 2$, $3^{64} \equiv 4$, и $3^{100} \equiv 4 \cdot 2 \cdot 4 = 32 \equiv 4$. Для показателя из $2048$ двоичных разрядов нужно меньше $2 \cdot 2048$ умножений вместо $2^{2048}$.

Какой остаток даёт $5^{2026}$ при делении на $11$?

$11$ — простое и не делит $5$, поэтому $5^{10} \equiv 1 \pmod{11}$. Так как $2026 = 10 \cdot 202 + 6$, получаем $5^{2026} \equiv 5^6$. Дальше: $5^2 = 25 \equiv 3$, $5^4 \equiv 3^2 = 9$, $5^6 = 5^4 \cdot 5^2 \equiv 9 \cdot 3 = 27 \equiv 5$. Ответ: $5$.

Составной циферблат

Теорема Ферма говорит о простых модулях, а шифр, к которому мы идём, считает по модулю произведения двух простых. Посмотрите в таблице степеней на $n = 15$. В последнем столбце единиц почти нет: $2^{14} \equiv 4$. Зато в столбце $k = 8$ единица стоит в каждой строке, где $a$ взаимно просто с $15$. Таких строк восемь: $1, 2, 4, 7, 8, 11, 13, 14$. Строки $3, 5, 6, 9, 10, 12$ единицу не получают никогда: степень числа, кратного трём или пяти, тоже кратна трём или пяти.

Эйлер искал общий смысл малой теоремы Ферма и в 1763 году опубликовал это обобщение; при простом $n = p$ оно превращается в теорему Ферма. Букву $\varphi$ для функции ввёл позже Гаусс. Докажем теорему перестановкой.

Идея: умножение на $a$ только переставляет обратимые остатки, поэтому их произведение не меняется; с другой стороны, оно умножается на $a^{\varphi(n)}$.

Расставим по кругу обратимые остатки по модулю $n$ — числа $r_1, r_2, \dots, r_{\varphi(n)}$ от $1$ до $n - 1$, взаимно простые с $n$. На чертеже $n = 15$, и их восемь. Умножим каждый на $a$ и возьмём остаток. Снова получится обратимый остаток. Во-первых, $ar$ взаимно просто с $n$: общий простой делитель $ar$ и $n$ по лемме Евклида делил бы $a$ или $r$. Во-вторых, остаток от деления на $n$ имеет с $n$ те же общие делители, что и само число, — это главный шаг алгоритма Евклида. Разные остатки переходят в разные: если $ar_i \equiv ar_j$, умножим обе части на $a^{-1}$ и получим $r_i \equiv r_j$. Значит, стрелки переставляют остатки — в каждый приходит ровно одна. Перемножим все остатки до умножения и после. После — те же числа в другом порядке, поэтому $(ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)}$, то есть $a^{\varphi(n)} R \equiv R$, где $R$ — произведение всех $r_i$. Произведение обратимых остатков обратимо, так что на $R$ можно сократить — умножить обе части на $R^{-1}$: $a^{\varphi(n)} \equiv 1 \pmod n$. Выберите другое $a$: стрелки меняются, вывод — нет.

В таблице для $n = 15$ единицы заполняют взаимно простые строки уже в столбце $4$, раньше, чем обещает теорема. Так бывает: теорема Эйлера гарантирует, что порядок делит $\varphi(n)$, но не утверждает, что он с ним совпадает.

Найдите две последние цифры числа $3^{2026}$ — то есть его остаток от деления на $100$.

Сначала $\varphi(100)$: из чисел от $1$ до $100$ на $2$ делятся $50$, на $5$ — $20$, на оба — $10$, так что взаимно простых с $100$ ровно $100 - 50 - 20 + 10 = 40$. По теореме Эйлера $3^{40} \equiv 1 \pmod{100}$, а $2026 = 40 \cdot 50 + 26$, так что $3^{2026} \equiv 3^{26}$. Считаем быстрым возведением: $3^2 = 9$, $3^4 = 81$, $3^8 \equiv 81^2 = 6561 \equiv 61$, $3^{16} \equiv 61^2 = 3721 \equiv 21$. Так как $26 = 16 + 8 + 2$, получаем $3^{26} \equiv 21 \cdot 61 \cdot 9$; $21 \cdot 61 = 1281 \equiv 81$, $81 \cdot 9 = 729 \equiv 29$. Ответ: $29$.

Задача Сунь-цзы

В китайском трактате «Сунь-цзы суань цзин» («Математический канон Сунь-цзы», III–V века) есть задача: «Имеются предметы, число которых неизвестно. Если считать их тройками, остаётся два; если пятёрками — три; если семёрками — два. Сколько предметов?» Ответ там же: $23$. На языке сравнений нужно найти $x$, для которого $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$ и $x \equiv 2 \pmod 7$.

Можно искать перебором, причём с умом. Выпишем числа с остатком $2$ по модулю $7$: $2, 9, 16, 23, \dots$ — и проверим остальные условия. Число $23$ при делении на $5$ даёт остаток $3$, при делении на $3$ — остаток $2$. Найдено. Но всегда ли решение есть? И сколько их?

Колёса на $3$, $5$ и $7$ делений снова встают в начальное положение только через $3 \cdot 5 \cdot 7 = 105$ шагов, и за эти $105$ шагов каждое сочетание остатков встречается ровно один раз. С колёсами на $4$ и $6$ делений иначе: они совпадают уже через $12$ шагов, а сочетаний $24$, и половина из них не появится никогда. Всё решает общий делитель.

Идея: разложить числа от $0$ до $mn - 1$ по таблице, где строка — остаток по модулю $m$, а столбец — остаток по модулю $n$, и увидеть, что каждая клетка занята ровно одним числом.

Возьмём таблицу из $m$ строк и $n$ столбцов. Число $x$ ставим в строку $x \bmod m$ и столбец $x \bmod n$. Переход от $x$ к $x + 1$ — шаг на клетку вниз и вправо, а выйдя за край таблицы, мы возвращаемся с противоположной стороны, как буквы на колесе Цезаря. Два разных числа от $0$ до $mn - 1$ не попадут в одну клетку. Пусть $x \equiv y \pmod m$ и $x \equiv y \pmod n$. Тогда $x - y = mk$ для некоторого целого $k$, и $n$ делит $mk$. Раз $n$ взаимно просто с $m$, по обобщённой лемме Евклида $n$ делит $k$, и $mn$ делит $x - y$. А разность двух чисел от $0$ до $mn - 1$ меньше $mn$ по абсолютной величине, так что $x = y$. Путь впервые возвращается в клетку числа $0$ только на шаге $mn$. Чисел от $0$ до $mn - 1$ ровно $mn$, клеток тоже $mn$, и никакие два числа не делят клетку. Значит, заняты все клетки: для любой пары остатков $(r, s)$ нашлось число $x$. Существование доказано. Единственность — это второй шаг: два решения с одинаковыми остатками по $m$ и по $n$ отличаются на кратное $mn$. Меняйте размеры таблицы: пока $m$ и $n$ взаимно просты, путь обходит все клетки. При общем делителе, скажем $4$ и $6$, он замкнулся бы через $\text{НОК}(4, 6) = 12$ шагов, не заняв и половины таблицы.

Для трёх и более попарно взаимно простых модулей теорема верна так же: сначала объединяем первые два сравнения в одно по модулю $mn$, потом его — с третьим, и так далее. Общий способ решать такие системы изложил Цинь Цзюшао в «Математическом трактате в девяти разделах» (1247). Сам трактат Сунь-цзы обходится без перебора: он собирает ответ из готовых деталей.

Нужный остаток по модулю $m$. Деталь, которая сравнима с $1$ по модулю $m$ и с $0$ по модулю $n$: она кратна $n$, а множитель $n^{-1}$ делает её единицей по модулю $m$. Обратный элемент существует, потому что $m$ и $n$ взаимно просты. Нужный остаток по модулю $n$. Деталь наоборот: сравнима с $0$ по модулю $m$ и с $1$ по модулю $n$. Пример Сунь-цзы с тремя модулями. Деталь $70$ даёт остаток $1$ при делении на $3$ и делится на $5$ и $7$; деталь $21$ сравнима с $1$ по модулю $5$ и делится на $3$ и $7$; деталь $15$ сравнима с $1$ по модулю $7$ и делится на $3$ и $5$. Ответ: $2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 \pmod{105}$. Именно так — $140$, $63$, $30$, в сумме $233$, минус $210$ — и решено в трактате, а позже числа $70$, $21$ и $15$ даже зарифмовали в китайском стишке.

Китайская теорема сразу даёт формулу для функции Эйлера. Число обратимо по модулю $mn$ ровно тогда, когда оно обратимо и по модулю $m$, и по модулю $n$, а в таблице такие числа занимают вполне определённые строки и столбцы.

Идея: в таблице китайской теоремы числа, взаимно простые с $mn$, заполняют прямоугольник $\varphi(m) \times \varphi(n)$.

Снова разложим числа от $0$ до $mn - 1$ по таблице $m \times n$. По китайской теореме каждое стоит в своей клетке, и заняты все клетки. Число $x$ взаимно просто с $m$ тогда и только тогда, когда с $m$ взаимно прост остаток $x \bmod m$: у них одни и те же общие делители с $m$. Отметим строки, номера которых взаимно просты с $m$. Их $\varphi(m)$. Так же отметим столбцы, номера которых взаимно просты с $n$. Их $\varphi(n)$. Число взаимно просто с $mn$ тогда и только тогда, когда оно взаимно просто и с $m$, и с $n$: общий простой делитель с $mn$ по лемме Евклида делит $m$ или $n$. Такие числа стоят ровно на пересечениях отмеченных строк и столбцов. Пересечений $\varphi(m)\,\varphi(n)$, и в каждом ровно одно число. Значит, $\varphi(mn) = \varphi(m)\,\varphi(n)$. Для простых $p \ne q$ отмечены все строки, кроме нулевой, и все столбцы, кроме нулевого: $\varphi(pq) = (p - 1)(q - 1)$.

Осталось посчитать $\varphi$ для степени простого числа. Среди чисел от $1$ до $p^k$ не взаимно просты с $p^k$ только кратные $p$: $p, 2p, \dots, p^{k-1} \cdot p$, их $p^{k-1}$. Поэтому $\varphi(p^k) = p^k - p^{k-1} = p^k\left(1 - \frac1p\right)$. Разложим $n$ на степени различных простых, применим мультипликативность — и получим общую формулу.

Натуральное число с разложением $n = p_1^{k_1} p_2^{k_2} \cdots p_s^{k_s}$ на степени различных простых. По множителю на каждое простое, входящее в $n$: каждое простое отсеивает свою долю $\frac1p$ чисел, и доли не мешают друг другу — это и есть мультипликативность. Показатели $k_i$ в формулу не входят. Пример: $360 = 2^3 \cdot 3^2 \cdot 5$, и $\varphi(360) = 360 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 96$. Проверка по частям: $\varphi(8)\,\varphi(9)\,\varphi(5) = 4 \cdot 6 \cdot 4 = 96$.

Старинная задача. Торговка несёт корзину яиц. Если вынимать их по $2$, по $3$, по $4$, по $5$ или по $6$, каждый раз остаётся одно яйцо, а если по $7$ — не остаётся ни одного. Какое наименьшее число яиц может быть в корзине?

Условия про $2, 3, 4, 5, 6$ означают, что $x - 1$ делится на каждое из этих чисел, то есть на их НОК, равное $60$: $x \equiv 1 \pmod{60}$. Кроме того, $x \equiv 0 \pmod 7$. Числа $60$ и $7$ взаимно просты, поэтому решение единственно по модулю $420$. Перебираем $1, 61, 121, 181, 241, 301$: на $7$ делится только $301 = 7 \cdot 43$. Ответ: $301$ яйцо.

Прежде чем собирать замки, потренируйтесь считать по модулю: остатки, обратные элементы, большие степени и системы. Решатель сравнений разберёт любую такую задачу по шагам.

Секрет, сказанный вслух

Все шифры до сих пор были симметричными: одним ключом шифруют и расшифровывают, и этот ключ обе стороны должны знать заранее. Ключи нужно доставлять, и в XX веке это превратилось в огромное хозяйство: шифроблокноты развозили дипломатической почтой и курьерами. В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали статью «Новые направления в криптографии» и показали, как двоим договориться об общем секрете, переговариваясь только открыто.

Сначала проделаем это с красками. Алиса и Боб публично выбирают общую краску, скажем жёлтую. Каждый подмешивает к своей порции жёлтой тайную краску, которую никому не показывает, и отправляет смесь другому — открыто, её видят все. Получив чужую смесь, каждый добавляет туда свою тайную краску. Теперь у обоих в банке все три краски, жёлтая и две тайные, и цвет получается одинаковым. Ева видела жёлтую и обе смеси, но разделить смесь обратно на составляющие она не умеет. А если слить две смеси вместе, жёлтой окажется вдвое больше, и цвет выйдет другим.

В числах краски смешивает возведение в степень по простому модулю. Открыто выбирают большое простое $p$ и число $g$ — первообразный корень по модулю $p$. Алиса задумывает тайное число $a$ и отправляет $A = g^a \bmod p$. Боб задумывает $b$ и отправляет $B = g^b \bmod p$. Алиса вычисляет $B^a$, Боб — $A^b$, и оба получают одно и то же, потому что $(g^b)^a = g^{ab} = (g^a)^b$.

Тайные показатели Алисы ($a$) и Боба ($b$). Их никто никому не передаёт. Открытые числа $A = g^a \bmod p$ и $B = g^b \bmod p$ — «смеси», которые видит Ева. Общий секрет. Его вычисляют оба, но он ни разу не прозвучал. Пример: $p = 23$, $g = 5$. Алиса берёт $a = 6$ и отправляет $A = 5^6 \bmod 23 = 8$; Боб берёт $b = 15$ и отправляет $B = 5^{15} \bmod 23 = 19$. Алиса считает $19^6 \bmod 23 = 2$, Боб — $8^{15} \bmod 23 = 2$. Общий секрет — $2$.

Ева знает $p$, $g$, $A$ и $B$. Чтобы получить секрет, ей достаточно найти $a$ по $A = g^a \bmod p$.

Возвести в степень по модулю легко — быстрым возведением. Найти показатель по результату, насколько известно, трудно. Для простого модуля из $2048$ двоичных разрядов лучшим известным алгоритмам нужно порядка $2^{112} \approx 5 \cdot 10^{33}$ операций, это работа не по силам всем компьютерам Земли вместе взятым. Функции, которые легко вычислить и трудно обратить, называют односторонними. Никто не доказал, что они вообще существуют: из их существования следовало бы $\mathrm P \ne \mathrm{NP}$, а это одна из главных открытых проблем математики. Вся современная криптография стоит на честном «никто пока не умеет».

Протоколу нужен первообразный корень $g$: тогда $A = g^a$ может оказаться любым ненулевым остатком, и Еве не за что зацепиться. Гаусс в «Арифметических исследованиях» дал два доказательства того, что он есть всегда.

Доказательство: сколько остатков каждого порядка

Идея: подсчитать, сколько ненулевых остатков имеют каждый возможный порядок, и увидеть, что порядок $p - 1$ не может остаться пустым. Нам понадобятся три факта.

Первый: если $a^m \equiv 1$, то порядок $d$ числа $a$ делит $m$. Разделим с остатком: $m = dq + r$, $0 \le r < d$. Тогда $1 \equiv a^m = (a^d)^q a^r \equiv a^r$. Раз $d$ — наименьший положительный показатель, дающий единицу, а $r < d$, то $r = 0$. В частности, по малой теореме Ферма порядок любого ненулевого остатка делит $p - 1$.

Второй: у сравнения $x^d \equiv 1 \pmod p$ не больше $d$ решений среди остатков. Это теорема о числе корней из главы 14, и её доказательство годится для остатков по простому модулю почти дословно. Единственное место, где нужна осторожность, — вывод «$(b - a)Q(b) = 0$ и $b \ne a$, значит, $Q(b) = 0$». По модулю $p$ он верен по лемме Евклида: если $p$ делит $(b - a)Q(b)$ и не делит $b - a$, то $p$ делит $Q(b)$.

Третий: для каждого делителя $d$ числа $p - 1$ остатков порядка $d$ либо нет совсем, либо ровно $\varphi(d)$. Пусть $a$ имеет порядок $d$. Числа $1, a, a^2, \dots, a^{d-1}$ различны (если $a^i \equiv a^j$ при $0 \le i < j < d$, то $a^{j - i} \equiv 1$ раньше срока) и все удовлетворяют $x^d \equiv 1$. По второму факту других решений нет, так что каждый остаток порядка $d$ — одна из степеней $a^j$, $0 \le j < d$. Порядок $a^j$ равен $d$ ровно тогда, когда $\text{НОД}(j, d) = 1$. Действительно, если $\text{НОД}(j, d) = g > 1$, то $(a^j)^{d/g} = (a^d)^{j/g} \equiv 1$ раньше срока. Если же $\text{НОД}(j, d) = 1$ и $(a^j)^k \equiv 1$, то по первому факту $d$ делит $jk$, а значит, по обобщённой лемме Евклида делит $k$. Таких $j$ ровно $\varphi(d)$.

Подсчёт. Обозначим через $\psi(d)$ количество остатков порядка $d$. Каждый из $p - 1$ ненулевых остатков имеет какой-то порядок, делящий $p - 1$, поэтому сумма $\psi(d)$ по всем делителям $d$ числа $p - 1$ равна $p - 1$. С другой стороны, сумма $\varphi(d)$ по всем делителям $d$ любого натурального $N$ равна $N$. Чтобы увидеть это, сократим дроби $\frac1N, \frac2N, \dots, \frac NN$: после сокращения знаменатель $d$ — делитель $N$, и знаменатель $d$ получают ровно $\varphi(d)$ дробей, а именно дроби $\frac kd$ с $1 \le k \le d$ и $\text{НОД}(k, d) = 1$. При $N = p - 1$ две суммы равны, а каждое слагаемое первой по третьему факту не больше соответствующего слагаемого второй. Значит, $\psi(d) = \varphi(d)$ при всех $d$, и в частности $\psi(p - 1) = \varphi(p - 1) \ge 1$. Остаток порядка $p - 1$ есть — это и есть первообразный корень.

Замок, который защёлкнет каждый

Обмен ключами решает половину задачи: Алиса и Боб получают общий секрет, но оба должны быть на связи одновременно. Диффи и Хеллман мечтали о большем — о шифровании с открытым ключом. Представьте почтовый ящик с щелью: бросить письмо может каждый, а достать — только хозяин ключа. Для шифра это значит, что ключ шифрования можно опубликовать и любой зашифрует им письмо, а расшифровать его сможет только владелец второго, закрытого ключа. Через год после статьи Диффи и Хеллмана трое исследователей из Массачусетского технологического института — Рональд Ривест, Ади Шамир и Леонард Адлеман — нашли такой замок. Шифр назвали по их инициалам: RSA.

Рецепт ключей. Алиса выбирает два больших простых числа $p$ и $q$ и держит их в секрете. Публикует она их произведение $n = pq$ и число $e$, взаимно простое с $\varphi(n) = (p - 1)(q - 1)$. Себе оставляет $d$ — обратный к $e$ по модулю $\varphi(n)$; его даёт расширенный алгоритм Евклида. Сообщение — число $m$ от $0$ до $n - 1$.

Сообщение — число от $0$ до $n - 1$. Текст сначала превращают в числа. Открытая экспонента. На практике часто берут $e = 65\,537 = 2^{16} + 1$: это простое число, и возводить в него быстро. Открытый модуль $n = pq$. Знать его может кто угодно; секрет в том, что никто, кроме Алисы, не знает $p$ и $q$. Шифровка. Её можно передавать открыто. Закрытая экспонента. Чтобы её вычислить, нужно знать $\varphi(n) = (p - 1)(q - 1)$, а для этого — разложение $n$ на множители. Пример: $p = 61$, $q = 53$, $n = 3233$, $\varphi(n) = 60 \cdot 52 = 3120$, $e = 17$, $d = 2753$ (проверка: $17 \cdot 2753 = 46\,801 = 15 \cdot 3120 + 1$). Сообщение $m = 65$ шифруется в $c = 65^{17} \bmod 3233 = 2790$, и $2790^{2753} \bmod 3233 = 65$.

Буквы в лаборатории шифруются парами: пара превращается в число $34x + y$, где $x$ и $y$ — номера букв (пробел — ноль, А — один). Если шифровать по одной букве, одинаковые буквы давали бы одинаковые числа, и частотный анализ аль-Кинди сработал бы и против RSA. Настоящий RSA идёт дальше: перед шифрованием к сообщению подмешивают случайные байты, чтобы даже одно и то же письмо, отправленное дважды, давало разные шифровки.

Ева знает $n = 3233$ и $e = 17$. Если она разложит $n$ на множители, то узнает $p$ и $q$, вычислит $\varphi(n)$, а по нему — $d$, тем же расширенным алгоритмом Евклида, что и Алиса. Для $3233$ хватит перебора делителей до $\sqrt{3233} \approx 57$, в лаборатории это одно нажатие кнопки. Вся стойкость RSA держится на том, что с числами из сотен цифр так не выходит.

Игрушечный ключ: $p = 5$, $q = 11$, $e = 3$. Найдите закрытую экспоненту $d$ — число от $1$ до $\varphi(n) - 1$.

$n = 55$, $\varphi(n) = 4 \cdot 10 = 40$. Нужно $3d \equiv 1 \pmod{40}$. Так как $40 = 13 \cdot 3 + 1$, то $3 \cdot (-13) \equiv 1$ и $d \equiv -13 \equiv 27$. Проверка: $3 \cdot 27 = 81 = 2 \cdot 40 + 1$. Сообщение $m = 7$ шифруется в $7^3 = 343 \equiv 13 \pmod{55}$, а $13^{27} \bmod 55$ снова даёт $7$.

С RSA можно не только шифровать, но и подписывать. Алиса возводит сообщение в свою закрытую степень $d$, а любой проверяет подпись, возводя результат в открытую степень $e$: если получилось исходное сообщение, подписать его мог только владелец $d$. Так сервер банка доказывает, что он настоящий.

Взлом

Разложить число на множители — задача, над которой люди бьются больше двух тысяч лет, и быстрого способа для неё до сих пор нет. Перебор делителей до $\sqrt n$ для числа из $617$ цифр (столько их в ключе RSA-2048) потребовал бы порядка $10^{308}$ делений. Лучший известный метод, решето числового поля, гораздо хитрее перебора, но и его время растёт быстрее любой степени числа цифр. Рекорд на сегодня — RSA-250, число из $250$ цифр, или $829$ двоичных разрядов. Его разложили в феврале 2020 года; на вычисления ушло около $2700$ лет работы одного процессорного ядра, распределённых по тысячам машин.

Угроза другого рода появилась в 1994 году: Питер Шор придумал алгоритм для квантового компьютера, который раскладывает числа на множители и находит дискретные логарифмы за время, растущее лишь как степень числа цифр. Квантовая часть алгоритма ищет порядок числа $a$ по модулю $n$ — тот самый период строки в нашей таблице степеней. Дальше работает обычная арифметика остатков. Если порядок $r$ чётный, то $n$ делит $a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1)$, и часто общий делитель $n$ с одной из скобок оказывается нетривиальным. Для $n = 15$ и $a = 7$: порядок семёрки равен $4$, $7^2 = 49 \equiv 4$, и $\text{НОД}(4 - 1, 15) = 3$, $\text{НОД}(4 + 1, 15) = 5$. Квантовых компьютеров, способных разложить настоящий ключ, пока нет, но ждать их никто не хочет: шифровку, записанную сегодня, можно будет прочитать через двадцать лет.

Поэтому в августе 2024 года американский институт стандартов NIST утвердил первые постквантовые стандарты: FIPS 203 (механизм согласования ключей ML-KEM), FIPS 204 и FIPS 205 (цифровые подписи ML-DSA и SLH-DSA). Первые два построены на задачах о решётках — о коротких векторах в многомерных сетках точек, третий — на хеш-функциях. Быстрых квантовых алгоритмов для этих задач не знают. Постквантовое согласование ключей уже работает в браузерах в паре с классическим: если один из двух замков когда-нибудь сломают, второй продолжит держать.

Когда вы открываете сайт банка, браузер и сервер сначала договариваются об общем секрете по схеме Диффи — Хеллмана: обмениваются «смесями» открыто, и подслушивающий не вычислит ключ, пока не научится находить дискретные логарифмы. Сегодня этот обмен чаще делают на эллиптических кривых (о них — глава 44), а всё чаще — вместе с постквантовым ML-KEM. Чтобы вы говорили именно с банком, а не с Евой посередине, сервер подписывает свою часть разговора, и подпись проверяется открытым ключом из его сертификата — это RSA или подпись на тех же кривых. Сами данные дальше шифрует быстрый симметричный шифр, обычно AES, ключом, полученным из общего секрета. Стойкость всей конструкции держится на трудности двух задач теории чисел: разложения на множители и дискретного логарифма.

Куда дальше

Всю главу мы пользовались одним свойством простого модуля: в $\mathbb Z_p$ можно делить на любое ненулевое число. Остатки по простому модулю складываются, вычитаются, умножаются и делятся, как дроби, хотя их всего $p$ штук. В $\mathbb Z_6$ так нельзя: $2 \cdot 3 = 0$, хотя ни $2$, ни $3$ не нули, и делить на них не получится. Какие ещё системы «чисел» умеют все четыре действия? Можно ли построить такую систему ровно из четырёх элементов, если $\mathbb Z_4$ не годится ($2 \cdot 2 = 0$)? Можно, и на таких системах работают коды, которые исправляют ошибки в QR-кодах, на компакт-дисках и в сигналах далёких космических аппаратов, — и шифр AES, который охраняет данные после того, как ключ согласован. Об этом — следующая глава.