28.07 // Новая дата открытия и имя изобретателя одноразового блокнота

Одноразовый блокнот — самый сильный шифр. При правильном использовании он не может быть взломан даже в теории. До настоящего момента считалось, что одноразовый блокнот был предложен Джильбертом Вернамом (Gilbert S. Vernam — Bell Telephone Labs) и Джозефом Моборном (Joseph O. Mauborgne — U.S. Army Signal Corps) в 1917 году.

Вернам предложил использование операции XOR между телеграфным бодо-кодом букв алфавита и гаммой, реализованной в виде "бесконечной" шифровальной ленты в телеграфных аппаратах. Моборн дополнил требования тем, что гамма должна быть совершенно случайной и неповторяющейся (одноразовой). Вернам не был криптологом, а лишь электроинженером, специализирующимся в области криптооборудования — его идея в основном состоит в практической реализации. Криптологическую базу одноразового блокнота в большей степени заложил Моборн.

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

Недавняя публикация Стивена Беллоуина с кафедры компьютерных наук Колумбийского Университета оспаривает первенство на имя изобретателя одноразого блокнота. Беллоуин приводит серьёзные аргументы в пользу того, что одноразовый блокнот был изобретён на 33 года раньше (и скорее всего был забыт и переизобретён уже позднее). В 1882 году, в Калифорнии, банкир Фрэнк Миллер опубликовал книгу "Телеграфные коды, гарантирующие приватность и секретность при передаче телеграмм".

Согласно публикации, именно Миллера можно считать первооткрывателем одноразового блокнота. Некоторым недостатком его работы видимо являлась чрезмерно сложная кодовая книга-словарь, предназначенная для сжатия текста перед шифрованием — это вероятно затруднило восприятие его работы и практическое внедрение. В остальном, как теоретические, так и практические аспекты одноразового блокнота были изложены на удивление верно, несмотря на неразвитое положение дел в криптографии того времени. Вместо операции XOR использовалась равноправная операция сдвига (сложения) по модулю, в то время достаточно известная.

Миллер явно указал на две основные составляющие одноразового блокнота — случайность и неповторяемость:

Банковский работник на Западе должен подготовить список нерегулярных номеров сдвига
Различия между такими номерами не должны быть регулярными
После того как номера сдвига использованы, они должны быть уничтожены и никогда не должны применяться повторно
Копия списка должна быть доставлена нью-йоркскому банковскому работнику, который должен подготовить другой список и отправить его копию для западного банковского работника

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

Любая криптосистема с повторным использованием одних и тех же значений может быть вскрыта. Этот факт подтвердится после небольшого разговора с телеграфным оператором

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

Примечательно и то, что Фрэнк Миллер правильно описал модель угрозы и указал на важность аутентификации и проверки целостности сообщений:

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

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

Нет ничего легче для оператора на линии — совершить подлог гигантских масштабов

Миллер разработал систему аутентификации и проверки сообщений по кодовым словам на предмет подмены фрагментов шифртекста.

Интересно, что Фрэнк Миллер не был учёным-теоретиком. Он был президентом банка D.O. Mills & Co и попечителем фонда Стэнфордского Университета. По некоторым предположениям, до этой должности он участвовал в расследованиях преступлений, связанных с мошенничеством, что и побудило его к изучению вопросов криптографии и криптоанализа.

Он получил образование в академии Филипс в Эксетере и был зачислен в Йелльский Университет, но спустя год стал добровольцем пехоты. Сохранились сведения о том, что он был ранен в ходе гражданской войны и ушёл в отставку в звании сержанта. Под руководством генерала Генри Олкота проводил серьёзные расследования (на тот момент уже как гражданский служащий), такие как убийство Линкольна и дела о коррупции и мошенничестве в ходе гражданской войны. После смерти своего отца он унаследовал и возглавил его банк, после чего и опубликовал свою кодовую книгу с описанием одноразового шифрования.

Оснований полагать, что Вернам или Моборн были знакомы с его публикацией, по мнению автора этого исторического исследования, нет. Хотя есть вероятность, что он встречался с криптографом Паркером Хиттом — учителем и коллегой Моборна. При встречах он мог изложить ему свои идеи, которые были осмыслены и перевоспроизведены позднее.

Для проведения этого исследования автор привлёк консультантов со стороны библиотекарей, архивных работников многих университетов США, специалистов по генеалогии, а также специалистов центра истории криптологии АНБ, центра военной истории американской армии и специалистов из военно-морского института.

Источник: Steven M. Bellovin. Frank Miller: Inventor of the one-time pad. Technical Report CUCS-009-11, Department of Computer Science, Columbia University, March 2011. A revised version appeared in Cryptologia 35(3), July 2011.