RSA: теория чисел уходит в каждый смартфон

Задача

До 1976 года всякий шифр требовал, чтобы отправитель и получатель заранее договорились о ключе. Для дипломатии и армии это решалось курьерами; для торговли между незнакомыми людьми — никак.

Уитфилд Диффи и Мартин Хеллман в статье «New Directions in Cryptography» (1976) сформулировали, чего хотелось бы: система, в которой ключ шифрования можно опубликовать, а расшифровать сообщение всё равно мог бы только владелец второго, секретного ключа. Они предложили протокол обмена ключами, но самой системы шифрования у них не было.

Решение

Рональд Ривест, Ади Шамир и Леонард Адлеман, работавшие в Массачусетском технологическом институте, взялись за задачу. Ривест и Шамир предлагали конструкции, Адлеман их ломал — так продолжалось около года и порядка сорока раз.

В апреле 1977 года, после пасхального ужина у знакомого студента, Ривест не мог заснуть, лежал с учебником математики и к утру записал схему, которую Адлеман сломать не сумел. Она и получила имя по первым буквам фамилий: RSA.

Как это работает

Всё держится на теореме Эйлера — обобщении малой теоремы Ферма.

1. Берём два больших простых $p$ и $q$, кладём $n=pq$ и $\varphi(n)=(p-1)(q-1)$.
2. Выбираем $e$, взаимно простое с $\varphi(n)$, и находим $d$ из условия $ed\equiv1\pmod{\varphi(n)}$ — алгоритмом куттака, он же расширенный алгоритм ЕвклидаЕвклидгреческий математик · около 300 года до н. э.Автор книги, которая две тысячи лет была вторым по тиражу текстом после Библии, — и о котором самом не известно почти ничего..
3. Открытый ключ — пара $(n,e)$, её публикуют. Секретный ключ — $d$.
4. Шифрование: $c=m^{e}\bmod n$. Расшифрование: $m=c^{d}\bmod n$.

Почему расшифрование возвращает исходное сообщение:

$$c^{d}=m^{ed}=m^{1+k\varphi(n)}=m\cdot\left(m^{\varphi(n)}\right)^{k}\equiv m\cdot1^{k}=m \pmod n .$$

Пример, который считается вручную. Возьмём $p=11$, $q=13$. Тогда $n=143$, $\varphi(n)=10\cdot12=120$. Выберем $e=7$; из $7d\equiv1\pmod{120}$ находим $d=103$ (проверка: $7\cdot103=721=6\cdot120+1$).

Шифруем $m=9$: $9^{7}\bmod143=48$. Расшифровываем: $48^{103}\bmod143=9$. Сходится.

Настоящие ключи устроены так же, только $p$ и $q$ имеют по несколько сотен десятичных знаков.

Почему это нельзя взломать

Открытый ключ содержит $n$ и $e$. Чтобы вычислить $d$, нужно знать $\varphi(n)=(p-1)(q-1)$, а для этого — разложить $n$ на множители.

Асимметрия здесь фундаментальная и очень наглядная. Перемножить два тысячезначных простых числа — работа на доли секунды. Разложить произведение обратно — задача, для которой лучший известный алгоритм (решето числового поля) работает время порядка

$$\exp\left(c\,(\ln n)^{1/3}(\ln\ln n)^{2/3}\right)$$

— субэкспоненциальное, но для чисел в 2048 бит совершенно недостижимое.

Строго говоря, никто не доказал, что взлом RSA требует разложения на множители, и что разложение трудно. Вся современная защищённая связь опирается на утверждение, которое считается верным и не доказано, — обстоятельство, о котором стоит помнить.

Сорок квадриллионов лет

В августе 1977 года Мартин Гарднер посвятил новому шифру колонку в «Scientific American» и опубликовал вызов: сообщение, зашифрованное ключом из 129 десятичных знаков (RSA-129). Авторы оценили время взлома в 40 квадриллионов лет.

Разложение нашли в 1994 году. Работа заняла восемь месяцев; в ней участвовало около шестисот добровольцев с 1600 компьютерами, связанными через интернет. Расшифрованное сообщение гласило: THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE («волшебные слова — брезгливый ягнятник»).

Ошиблись авторы не в математике, а в прогнозе прогресса: за семнадцать лет и алгоритмы разложения, и вычислительные мощности ушли далеко вперёд. Отсюда практическое правило — ключи регулярно удлинять. Сегодня разложен RSA-250 (829 бит, 2020 год); стандартом считаются 2048 и 4096 бит.

Кто был первым

В 1997 году британский Центр правительственной связи рассекретил документы, из которых следовало, что всё это было придумано раньше и никому не сказано:

• Джеймс Эллис (1970) сформулировал саму идею «несекретного шифрования»;
• Клиффорд Кокс (1973) описал схему, по существу совпадающую с RSA, — на трёх страницах, за четыре года до Ривеста, Шамира и Адлемана;
• Малкольм Уильямсон (1974) — схему обмена ключами, совпадающую с протоколом Диффи — Хеллмана.

Работы были засекречены; Эллис умер за месяц до рассекречивания, так и не получив признания при жизни. Эта история стоит на карте отдельной точкой в дискретной линии, и она — самый чистый пример того, что секретность обходится дорого прежде всего тому, кто её соблюдает.

Что дальше

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

Квантовая угроза. В 1994 году Питер Шор построил алгоритм, которому разложение на множители стоит куба длины ключа, — правда, на машине другого устройства. И RSA, и эллиптические кривые уязвимы перед ним одинаково, поэтому первые постквантовые стандарты, принятые в 2024 году, построены уже на решётках и хеш-функциях, а не на теории чисел.

Премия ТьюрингаАлан Тьюринганглийский математик и криптоаналитик · 1912–1954Определил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. Ривесту, Шамиру и Адлеману — 2002 год.

Стоит вернуться к тому, с чего начиналась вводная этой линии. ХардиГодфри Харолд Хардибританский математик · 1877–1947Гордился тем, что не сделал ничего полезного, — и написал главную формулу популяционной генетики; главным своим вкладом в науку называл открытие Рамануджана. писал в 1940 году, что теория чисел не имеет практических приложений и не может быть использована во вред. Малая теорема ФермаПьер Фермафранцузский юрист и математик · 1607–1665Советник тулузского парламента, не напечатавший при жизни ни одной математической книги — и успевший заложить теорию чисел, аналитическую геометрию, метод касательных и теорию вероятностей., которой в тот момент было ровно триста лет и которая была самым чистым образцом бесполезного знания, сегодня выполняется миллиарды раз в секунду на всей планете.

Задача. Возьмите $p=5$, $q=11$, $e=3$. Найдите $n$, $\varphi(n)$ и $d$; зашифруйте $m=4$ и расшифруйте обратно.
(Ответ: $n=55$, $\varphi=40$, $d=27$ (так как $3\cdot27=81=2\cdot40+1$). $4^{3}=64\equiv9\pmod{55}$; обратно $9^{27}\bmod55=4$.)