Челтнем: секретная криптография, запрещённый приоритет

Задача о ключе

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

Для армии и дипломатии это решалось курьерами и таблицами. Но у крупной военной сети распределение ключей — огромная и дорогая логистика: тысячи корреспондентов, у каждого свой ключ с каждым, ключи надо менять, доставлять, уничтожать. Именно с этой стороны — не с математической, а с хозяйственной — задача и стояла перед Центром правительственной связи Великобритании (GCHQ) в Челтнеме.

Эллис: теорема существования без конструкции

Джеймс Эллис, инженер GCHQ, задумался, нельзя ли обойтись без секретного ключа вовсе.

Толчком послужил найденный им отчёт военного времени из Bell Labs (проект C43, 1944, неопубликованный): там описан способ защищённой передачи, в котором получатель добавляет в линию шум, а потом сам же его вычитает. Подслушивающий слышит шум; отправитель ни о чём не договаривался.

Эллис понял: если это возможно в аналоговом виде, значит, задача не абсурдна. В январе 1970 года он написал внутренний доклад «The Possibility of Secure Non-Secret Digital Encryption» — «О возможности защищённого несекретного цифрового шифрования».

Обратите внимание, что именно он сделал. Эллис доказал, что такая система может существовать, и не построил ни одной. Три года никто в GCHQ не мог найти конструкцию.

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

Кокс: один вечер

В сентябре 1973 года в GCHQ пришёл Клиффорд Кокс, двадцати трёх лет, только что из Кембриджа, где занимался теорией чисел. Коллега за чаем пересказал ему задачу Эллиса — без бумаг, просто как курьёз.

Вечером дома, без записей, Кокс её решил.

Пусть $p$ и $q$ — большие простые, $N=pq$. Число $N$ публикуется. Чтобы зашифровать сообщение $M$, отправитель считает

$$C = M^{N} \bmod N .$$

Получатель, знающий $p$ и $q$, вычисляет $d$ из условия

$$N\,d \equiv 1 \pmod{(p-1)(q-1)}$$

и восстанавливает $M = C^{d} \bmod N$ по теореме ЭйлераЛеонард Эйлершвейцарский математик, работавший в Петербурге и Берлине · 1707–1783Самый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя..

Это RSA, у которого открытая экспонента взята равной самому модулю. 20 ноября 1973 года Кокс записал результат на четырёх страницах под названием «A Note on Non-Secret Encryption». До статьи Ривеста, Шамира и Адлемана оставалось три с половиной года.

Уильямсон: обмен ключами

Третьим был Малькольм Уильямсон, школьный друг Кокса, тоже математик. Услышав о схеме, он первым делом попытался её сломать — и, не сумев, в 1974 году нашёл другую конструкцию: протокол, позволяющий двум сторонам выработать общий секрет, обмениваясь открытыми сообщениями. По существу это протокол Диффи — Хеллмана, опубликованный в 1976-м.

К 1974 году в одном учреждении лежали в столе все три главные идеи открытой криптографии.

Почему всё это осталось в столе

Причин было несколько, и ни одна не была заговором.

Не хватало машин. Возведение в степень по модулю большого числа в 1973 году стоило дорого; GCHQ считал схему непрактичной.

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

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

Ирония в том, что оценка оказалась ошибочной ровно в той части, где GCHQ был экспертом: непрактичное изобретение через четыре года стало основой всей электронной торговли.

Декабрь 1997 года

GCHQ разрешил рассказать эту историю в декабре 1997 года — Кокс доложил её открыто, и внутренние документы были рассекречены.

Джеймс Эллис умер 25 ноября 1997 года. До публикации своего приоритета он не дожил трёх недель. Он знал, что рассекречивание готовится.

Ривест, Шамир и Адлеман признали приоритет без возражений; никакой утечки не было — они пришли к тому же независимо и своё сделали сами. Спора о приоритете, собственно, и не было. Была история о человеке, которому двадцать семь лет нельзя было сказать, что он придумал.

Чему это учит

На нашей карте есть похожие случаи, и вместе они складываются в правило.

Бюрги вычислил логарифмы раньше НепераДжон Непершотландский лэрд, богослов и математик · 1550–1617Двадцать лет считал таблицу, превращающую умножение в сложение, — и считал при этом, что главный труд его жизни совсем другой: толкование Апокалипсиса. и не напечатал — приоритет достался Неперу. ГауссКарл Фридрих Гаусснемецкий математик и астроном · 1777–1855«Король математиков», у которого напечатанное было заметно меньше сделанного: половина результатов пролежала в дневнике до самой смерти — включая неевклидову геометрию. записал быстрое преобразование ФурьеЖозеф Фурьефранцузский математик, физик и префект Изера · 1768–1830Утверждал, что любую функцию можно сложить из синусов, — и был не прав ровно настолько, чтобы математике понадобилось сто лет и три новые теории, чтобы разобраться. в 1805 году в тетради, которую издали посмертно, — алгоритм переоткрыли через сто шестьдесят лет. Кокс написал RSA в 1973 году в сейф — мир получил RSA в 1977-м от других людей.

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

Задача. Проверьте схему Кокса на маленьких числах: $p=5$, $q=7$. Найдите $N$, показатель расшифрования $d$, зашифруйте $M=2$ и расшифруйте обратно.
(Ответ: $N=35$, $(p-1)(q-1)=24$. Условие $35d\equiv1\pmod{24}$, то есть $11d\equiv1\pmod{24}$; подходит $d=11$, потому что $121=5\cdot24+1$. Шифрование: $2^{35}\bmod35$. Порядок двойки по модулю 35 равен 12, а $35\equiv11\pmod{12}$, поэтому $2^{35}\equiv2^{11}=2048\equiv18$. Расшифрование: $18^{11}\bmod35 = 2$. Заметьте, что открытым ключом здесь служит сам модуль — у Ривеста, Шамира и Адлемана показатель будет выбираться отдельно, и это удобнее.)

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