Гилберт Вернам

Гилберт Вернам (англ. Gilbert Sandford Vernam; 3 апреля 1890, Нью-Йорк — 7 февраля 1960, Нью-Йорк) — американский инженер и криптограф, сотрудник компании Bell Labs. Наиболее известен как создатель криптографической системы, впоследствии названной шифром Вернама, который является одной из первых реализаций поточного шифрования и единственным на сегодняшний день криптографическим алгоритмом, обладающим доказанной абсолютной криптостойкостью (при соблюдении определённых условий).

Биография

Гилберт Сэндфорд Вернам родился 3 апреля 1890 года в Нью-Йорке в семье владельца типографии. В 1912 году окончил Вустерский политехнический институт (штат Массачусетс) по специальности «электротехника». После окончания института устроился на работу в компанию Western Union, где занимался разработкой оборудования для телеграфной связи.

В 1917 году, в разгар Первой мировой войны, Вернам был переведён в исследовательское подразделение Western Union, где ему поручили задачу по созданию автоматической системы шифрования телеграфных сообщений. К тому времени телеграфные линии активно использовались для передачи военных и дипломатических депеш, и существовавшие ручные методы шифрования (например, с использованием одноразовых блокнотов) были медленными и ненадёжными.

В 1918 году Вернам совместно с майором Джозефом Моборном (Joseph Mauborgne) и капитаном Паркером Хиттом (Parker Hitt) из Армии США разработал систему, которая впоследствии стала известна как шифр Вернама. В 1919 году он получил патент США № 1,310,719 на «Систему секретной телеграфной связи» (Secret signaling system). В 1920-х годах Вернам продолжил работу в Western Union, занимаясь усовершенствованием телеграфного оборудования. В 1943 году он вышел на пенсию.

Гилберт Вернам скончался 7 февраля 1960 года в Нью-Йорке в возрасте 69 лет.

Шифр Вернама

Принцип работы

Шифр Вернама представляет собой разновидность поточного шифра, в котором открытый текст (в виде последовательности битов) объединяется с ключом (также в виде последовательности битов) с помощью операции «исключающее ИЛИ» (XOR). Формально процесс шифрования и дешифрования описывается следующим образом:

• Шифрование: \( C_i = P_i \oplus K_i \), где \( C_i \) — i-й бит шифротекста, \( P_i \) — i-й бит открытого текста, \( K_i \) — i-й бит ключа.
• Дешифрование: \( P_i = C_i \oplus K_i \).

Ключевой особенностью шифра Вернама является требование, чтобы ключ был:

1. Случайным — каждый бит ключа должен быть сгенерирован истинно случайным образом, а не с помощью псевдослучайного генератора.
2. Длиной не менее длины сообщения — ключ не должен использоваться повторно для разных сообщений.
3. Секретным — ключ должен быть известен только отправителю и получателю.
4. Одноразовым — каждый ключ используется только один раз.

При соблюдении всех этих условий шифр Вернама обладает абсолютной криптостойкостью (теоретически невзламываемостью). Это означает, что перехватчик, имеющий неограниченные вычислительные мощности, не сможет получить никакой информации об открытом тексте из шифротекста, кроме его длины.

История создания

Изначально Вернам разрабатывал систему для автоматического шифрования телеграфных сообщений, передаваемых с помощью пятибитового кода Бодо. В его первой реализации ключ был записан на перфорированной бумажной ленте в виде случайной последовательности битов. Отправитель и получатель должны были иметь идентичные экземпляры ключевой ленты. Шифрование происходило путём объединения битов открытого текста и ключа с помощью электрической схемы, реализующей XOR.

В 1918 году майор Джозеф Моборн из Армии США предложил использовать для ключа именно случайную последовательность, а не осмысленный текст, что и обеспечило системе абсолютную криптостойкость. До этого Вернам использовал в качестве ключа заранее определённые последовательности (например, текст из книги), что делало систему уязвимой.

Доказательство абсолютной криптостойкости

Строгое математическое доказательство абсолютной криптостойкости шифра Вернама было дано Клодом Шенноном в 1949 году в его работе «Теория связи в секретных системах». Шеннон показал, что для шифра, удовлетворяющего условиям Вернама, апостериорная вероятность любого открытого текста равна априорной вероятности, то есть перехват шифротекста не даёт никакой информации о сообщении.

Применение

Историческое применение

Шифр Вернама использовался для защиты особо важных коммуникаций во время Второй мировой войны. В частности, он применялся на «горячей линии» между Москвой и Вашингтоном (1963 год) — ключи передавались дипломатической почтой. Советский Союз использовал шифр Вернама для защиты линий правительственной связи (система «Алтай»), однако в некоторых случаях нарушал правило одноразовости ключа, что привело к уязвимости (проект «Венона»).

Современное применение

В современной криптографии шифр Вернама используется редко из-за практических ограничений:

• Проблема распространения ключей: необходимо передать ключ длиной, равной длине сообщения, по защищённому каналу. Если такой канал уже существует, то шифрование теряет смысл.
• Одноразовость: ключ нельзя использовать повторно, что делает его непригодным для массовых коммуникаций.
• Хранение ключей: для длинных сообщений требуется хранить ключи большого объёма.

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

Критика и ограничения

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

1. Генерация истинно случайных последовательностей: компьютерные генераторы псевдослучайных чисел не подходят, так как они детерминированы. Для генерации ключей требуются аппаратные источники энтропии (например, квантовые шумы).
2. Синхронизация ключей: отправитель и получатель должны иметь точно синхронизированные ключи. Потеря синхронизации (например, из-за сбоя передачи) делает дешифрование невозможным.
3. Аутентификация: шифр Вернама не защищает от подмены сообщения. Если злоумышленник знает структуру открытого текста, он может изменить шифротекст, что приведёт к предсказуемым изменениям в расшифрованном сообщении.

Интересные факты

• Шифр Вернама часто путают с «одноразовым блокнотом» (one-time pad). Термин «одноразовый блокнот» появился позже и относится к методу, при котором ключ записывается на бумажном блокноте, а страницы уничтожаются после использования. Однако технически шифр Вернама и одноразовый блокнот — это один и тот же принцип.
• В 1944 году советский разведчик Игорь Гузенко (впоследствии перебежчик) раскрыл канадским властям информацию о том, что Советский Союз использовал шифр Вернама, но нарушал правило одноразовости ключа. Это привело к расшифровке части советской дипломатической переписки в рамках проекта «Венона».
• В 2019 году группа исследователей из Массачусетского технологического института (MIT) продемонстрировала систему квантового распределения ключей, совместимую с шифром Вернама, на расстоянии более 500 километров.

Источники

• Gilbert S. Vernam. Patent US 1,310,719 «Secret signaling system», 1919.
• Claude E. Shannon. «Communication Theory of Secrecy Systems», Bell System Technical Journal, 1949.
• David Kahn. «The Codebreakers: The Story of Secret Writing», Macmillan, 1967.
• Bruce Schneier. «Applied Cryptography: Protocols, Algorithms, and Source Code in C», John Wiley & Sons, 1996.
• Whitfield Diffie, Susan Landau. «Privacy on the Line: The Politics of Wiretapping and Encryption», MIT Press, 2007.