Карта → событие
Диффи и Хеллман: ключ, который можно опубликовать
Задача, у которой не было решения
До 1976 года всякий шифр требовал, чтобы отправитель и получатель заранее договорились о ключе. Для армии и дипломатии это решалось курьерами: мешок с кодовыми книгами, дипломатическая почта, расписание смены ключей на месяц вперёд. Для двоих незнакомых людей, которым надо переписаться прямо сейчас, решения не было вовсе.
Хуже того, задача плохо росла. Если связь нужна каждому с каждым, ключей требуется по одному на пару:
$$\frac{n(n-1)}{2}.$$
Для десятерых это сорок пять ключей — терпимо. Для тысячи абонентов — четыреста девяносто девять тысяч пятьсот, и каждый надо доставить, сохранить и вовремя заменить. Никакая сеть на этом не строится. Именно поэтому идея всемирной торговли между незнакомцами упиралась не в законы и не в связь, а в логистику мешков с ключами.
Кто
Уитфилд Диффи учёной карьеры не делал: он несколько лет ездил по стране, собирая по крупицам всё, что можно было узнать о шифрах, — область была закрытой, публикаций почти не было, и знание жило в головах. В сентябре 1974 года его свели с Мартином Хеллманом, молодым профессором Стэнфорда, которого коллеги отговаривали заниматься криптографией: считалось, что против Агентства национальной безопасности с его бюджетом и полувековой форой частному исследователю ловить нечего.
Третьим был Ральф Меркл, студент Беркли. В 1974-м он сдал курсовую с проектом связи между двумя незнакомцами по открытому каналу; преподаватель проект не понял и отверг. Напечатать эту работу удалось только в 1978 году, уже после статьи стэнфордцев. Хеллман потом много раз просил называть протокол Диффи — Хеллмана — Меркла; прижилось короткое имя.
«New Directions in Cryptography»
Статья вышла в ноябре 1976-го и начиналась словами о том, что криптография стоит на пороге революции. В ней две разные вещи, и их стоит различать.
Первое — понятие. Авторы описали, чего хотелось бы: систему, в которой ключ шифрования можно опубликовать, а прочесть сообщение мог бы только владелец второго, секретного ключа. Заодно они заметили, что такая система дала бы и электронную подпись. Ни того, ни другого они построить не сумели — только сформулировали. Через год эту половину закроют в Массачусетсе.
Второе — работающий протокол. Обмен ключами, который не требует ни секретного канала, ни предварительной встречи и работает прямо сейчас.
Как двое договариваются на глазах у всех
Стороны заранее и открыто выбирают простое число $p$ и основание $g$. Дальше:
- Алиса задумывает $a$ и посылает $A = g^{a} \bmod p$;
- Боб задумывает $b$ и посылает $B = g^{b} \bmod p$;
- Алиса считает $B^{a}$, Боб считает $A^{b}$ — и получают одно и то же:
$$B^{a} = (g^{b})^{a} = g^{ab} = (g^{a})^{b} = A^{b} \pmod p.$$
Подслушивающий видит $p$, $g$, $A$ и $B$. Чтобы получить $g^{ab}$, ему нужно из $g^a$ извлечь показатель $a$ — а это дискретное логарифмирование, задача, для которой быстрого способа не известно. Возводить в степень по модулю легко, а извлекать показатель — нет; на этом перепаде всё и держится.
Обратите внимание на устройство хитрости: секрет не передаётся ни в каком виде. Он возникает у обоих сразу, хотя по каналу шли только открытые числа.
Обмен на маленьких числах
Возьмите $p = 23$ и $g = 5$. Алиса задумала $a = 6$, Боб задумал $b = 15$.
Что уйдёт в канал и какой общий секрет получится у обоих?
(Ответ: $A = 5^{6} \bmod 23 = 8$, $B = 5^{15} \bmod 23 = 19$. Алиса считает $19^{6} \bmod 23 = 2$, Боб считает $8^{15} \bmod 23 = 2$ — секрет равен 2. Подслушивающий видит числа 8 и 19 и, чтобы повторить вычисление, должен решить $5^{x} \equiv 8 \pmod{23}$. При двузначном модуле это перебор в двадцать два шага; при модуле длиной в две тысячи двоичных знаков перебора не хватит до конца существования Вселенной. Кстати, пятёрка выбрана не случайно: её степени пробегают все 22 ненулевых остатка по модулю 23, то есть она первообразный корень.)
Приоритет, который был отнят заранее
Всё это уже лежало в столе. В Челтнеме Малькольм Уильямсон нашёл по существу тот же протокол в 1974 году, за два года до статьи, — и рассекретили это только в 1997-м, когда спорить было уже не о чем.
Получается редкая для этой карты конфигурация: не спор о первенстве, а запрет говорить. Обе стороны были правы, обе сделали работу, но одна из них тридцать лет не имела права сказать об этом вслух.
Что было дальше
Протокол не устарел — он победил. Сегодняшний TLS, тот самый замочек в адресной строке, обменивается ключами именно по Диффи — Хеллману, причём заново для каждого соединения: даже если завтра украдут долговременный ключ сервера, вчерашние записанные разговоры прочесть не удастся. От RSA как способа обмена ключами в последней версии протокола отказались вовсе.
Сама же группа, в которой всё происходит, через девять лет сменится на другую — ту, что выросла из геометрической конструкции ДиофантаДиофант АлександрийскийПервым стал решать уравнения в целых числах и первым ввёл сокращённые обозначения вместо слов — и задал вопрос, на который отвечали до 1994 года..
Премию ТьюрингаАлан ТьюрингОпределил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. Диффи и Хеллман получили в 2015 году, через тридцать девять лет после статьи.
Следующая точка: Кембридж в Массачусетсе — где недостающую половину задачи закроют меньше чем за год.