Шифр Вернама

Шифр Вернама (другое название: англ. One-time pad — схема одноразовых блокнотов) — в криптографии система симметричного шифрования, изобретённая в 1917 году сотрудниками AT&T Мейджором Джозефом Моборном и Гильбертом Вернамом. Шифр Вернама является системой шифрования, для которой доказана абсолютная криптографическая стойкость.

Описание

Для произведения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с ключом (называемым одноразовым блокнотом или шифроблокнотом). При этом ключ должен обладать тремя критически важными свойствами:

1. быть истинно случайным;
2. совпадать по размеру с заданным открытым текстом;
3. применяться только один раз.

Шифр назван в честь телеграфиста AT&T Гильберта Вернама, который в 1917 году построил телеграфный аппарат, который выполнял эту операцию автоматически — надо было только подать на него ленту с ключом. Не будучи шифровальщиком, тем не менее, Вернам верно заметил важное свойство своего шифра — каждая лента должна использоваться только один раз и после этого уничтожаться. Это трудноприменимо на практике — поэтому аппарат был переделан на несколько закольцованных лент с взаимно простыми периодами.

Свойства

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

Область применения

Примерный вид страницы шифроблокнота

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

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

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

Не является шифром Вернама, но близка к нему схема одноразовых кодов: например, кодовое слово «Альфа» означает «Возвращаюсь».

Недостатки

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

• Проблемой является защищённая передача последовательности и сохранение её в тайне. Если существует надёжно защищённый от перехвата канал передачи сообщений, шифры вообще не нужны: секретные сообщения можно передавать по этому каналу. Если же передавать ключ системы Вернама с помощью другого шифра (например, DES), то полученный шифр окажется защищённым ровно настолько, насколько защищён DES. При этом, поскольку длина ключа та же, что и длина сообщения, передать его не проще, чем сообщение. Шифроблокнот на физическом носителе можно украсть или скопировать.

• Возможны проблемы с надёжным уничтожением использованной страницы. Этому подвержены как бумажные страницы блокнота, так и современные электронные реализации с использованием компакт-дисков или флэш-памяти.

• Если третья сторона каким-нибудь образом узнает сообщение, она легко восстановит ключ и сможет подменить послание на другое такой же длины.

• Шифр Вернама чувствителен к любому нарушению процедуры шифрования. Бывали случаи, когда одна и та же страница блокнота по различным причинам применялась дважды. Например, среди всего объёма советской шифрованной переписки, перехваченной АНБ США в период 40-х годов прошлого века, были обнаружены сообщения, закрытые дважды использованной гаммой. Период этот длился не очень долго, потому что уже после первых успехов американских криптоаналитиков в конце 1940-х годов в спецслужбах СССР узнали о серьёзных проблемах с надёжностью своей шифрпереписки. Такие сообщения были расшифрованы в течение 40 последующих лет в рамках секретного проекта «Venona», документы которого были не так давно рассекречены и выложены на сайте АНБ.

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

Шифр Вернама в искусстве

• В американском кинофильме 2001 года «Пароль „Рыба-меч“» хакер (которого играет Хью Джекман) взламывает именно шифр Вернама.
• В книге «Криптономикон» подобный шифр взламывает немецкий математик Рудольф фон Хакльгебер благодаря «неслучайностям» при создании блокнотов.

См. также

• Одноразовый пароль
• Номерные радиостанции

Ссылки

• http://students.uni-vologda.ac.ru/pages/pm00/kan/symmetric.htm
• offline.computerra.ru/1999/305/3111
• www.agentura.ru/press/about/jointprojects/confident/crypto19end
• А. Синельников Шифры советской разведки
• Шифроблокнот КГБ (англ.)
• Dirk Rijmenants' One-time Pad (англ.)
• Dirk Rijmenants' The Manual One-time Pad (англ.)
• THE VENONA STORY [1]
• Берд Киви. Цена ошибки [2]