Эта статья входит в число добротных статей

Шифр Вернама

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Шифр Вернама (англ. Verrnam Cipher) — система симметричного шифрования, изобретённая в 1917 году сотрудником AT&T Гилбертом Вернамом[1].

Шифр является разновидностью криптосистемы одноразовых блокнотов. В нём используется булева функция «Исключающее ИЛИ». Шифр Вернама является примером системы с абсолютной криптографической стойкостью[2]. При этом он считается одной из простейших криптосистем[3].

История[править | править вики-текст]

Патент на систему Гилберта Вернама

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

Вернам не использовал понятие «Исключающее ИЛИ» в патенте, но реализовал именно эту операцию в релейной логике. Каждый символ в сообщении преобразовывался побитовым XOR (исключающее ИЛИ) с ключом бумажной ленты[4].

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

Не будучи шифровальщиком, тем не менее, Вернам верно заметил важное свойство своего шифра — каждая лента должна использоваться только один раз и после этого уничтожаться. Это трудноприменимо на практике — поэтому аппарат был переделан на несколько закольцованных лент с взаимно простыми периодами[5].

Описание[править | править вики-текст]

Криптосистема была предложена для шифрования телеграфных сообщений, которые представляли собой бинарные тексты, в которых открытый текст представляется в коде Бодо (в виде пятизначных «импульсных комбинаций»). В этом коде, например, буква «А» имела вид (1 1 0 0 0). На бумажной ленте цифре «1» соответствовало отверстие, а цифре «0» — его отсутствие. Секретный ключ должен был представлять собой хаотичный набор букв того же самого алфавита[5].

Для получения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с секретным ключом. Так, например, при применении ключа (1 1 1 0 1) на букву «А» (1 1 0 0 0) получаем зашифрованное сообщение (0 0 1 0 1): Зная, что для принимаемого сообщения имеем ключ (1 1 1 0 1), легко получить исходное сообщение той же операцией: Для абсолютной криптографической стойкости ключ должен обладать тремя критически важными свойствами[2]:

  1. Иметь случайное равномерное распределение: , где k — ключ, а N — количество бинарных символов в ключе;
  2. Совпадать по размеру с заданным открытым текстом;
  3. Применяться только один раз.

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

Например, кодирование шифром Вернама по модулю m = 26 (A=0,B=1,…, Z=25):

Ключ:           EVTIQWXQVVOPMCXREPYZ 
Открытый текст: ALLSWELLTHATENDSWELL (All's well that ends well)
Шифротекст:     EGEAMAIBOCOIQPAJATJK

Без знания ключа такое сообщение не поддаётся анализу. Даже если бы можно было перепробовать все ключи, в качестве результата мы получили бы все возможные сообщения данной длины плюс колоссальное количество бессмысленных дешифровок, выглядящих как беспорядочное нагромождение букв. Но и среди осмысленных дешифровок не было бы никакой возможности выбрать искомую. Когда случайная последовательность (ключ) сочетается с неслучайной (открытым текстом), результат этого (шифротекст) оказывается совершенно случайным и, следовательно, лишённым тех статистических особенностей, которые могли бы быть использованы для анализа шифра.[6].

Криптографическая стойкость[править | править вики-текст]

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

Приведём доказательство абсолютной криптографической стойкости. Пусть сообщение представлено двоичной последовательностью длины . Распределение вероятности сообщений может быть любым. Ключ так же представлен двоичной последовательностью той же длины но с равномерным распределением для всех ключей.

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

Легальный пользователь знает ключ и осуществляет расшифрование:

Найдём вероятностное распределение N-блоков шифротекстов, используя формулу:

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

Запишем совместное распределение открытых текстов и шифротекстов:

Найдём условное распределение

так как ключ и открытый текст являются независимыми случайными величинами. Итого:

Подстановка правой части этой формулы в формулу для совместного распределения даёт

Что доказывает независимость шифротекстов и открытых текстов в этой системе. Это и означает абсолютную криптографическую стойкость[7].

Область применения[править | править вики-текст]

В настоящее время шифрование Вернама используется достаточно редко. В большой степени из-за существенного размера ключа, длина которого должна совпадать с длиной сообщения. То есть, использование таких шифров требует огромных затрат на производство, хранение, уничтожение ключевых материалов. Тем не менее, совершенно стойкие шифры типа Вернама все же нашли практическое применение для защиты особо важных линий связи с относительно небольшим объёмом информации. Так, например, англичане и американцы использовали шифры типа Вернама во время Второй мировой войны. Шифр Вернама по модулю 2 использовался на правительственной «горячей линии» между Вашингтоном и Москвой, где ключевые материалы представляли собой бумажные ленты, на которые знаки ключевой последовательности наносились с помощью перфорации[2].

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

Недостатки[править | править вики-текст]

  • Для работы шифра Вернама необходима истинно случайная последовательность (ключ). По определению, последовательность, полученная с использованием любого алгоритма, является не истинно случайной, а псевдослучайной. То есть, нужно получить случайную последовательность не алгоритмически (а, например, используя радиоактивный распад, создаваемый электронным генератором белого шума, или другие достаточно случайные события). Чтобы сделать распределение предельно близким к равномерному, случайная последовательность обычно пропускается через хэш-функцию наподобие MD5[9].
  • Недостатком использования шифра Вернама является отсутствие подтверждения подлинности и целостности сообщения. Получатель не может удостовериться в отсутствии повреждений или в подлинности отправителя. Если третья сторона каким-нибудь образом узнает сообщение, она легко восстановит ключ и сможет подменить послание на другое такой же длины. Решением проблемы является применение хэш-функции. От открытого текста вычисляется хэш-функция, и её значение шифруется вместе с сообщением. При каком-либо изменении сообщения значение хэш-функции изменится. Таким образом, даже если злоумышленник заполучил шифроблокнот, не зная алгоритм вычисления хэш-функции, он не сможет использовать его для передачи информации[8].
  • Под рукой всегда необходимо иметь достаточное количество ключей, которые могут понадобиться в дальнейшем для шифрования больших объёмов открытого текста. Реальный же объём текста зачастую трудно оценить заранее, в особенности это касается дипломатической и военной сферы, где ситуация способна меняться быстро и непредсказуемо. Это может приводить к нехватке ключей, что может заставить шифровальщика либо использовать ключ(и) повторно, либо полностью прервать шифрованную связь.
  • Проблемой является защищённая передача последовательности и сохранение её в тайне. Если существует надёжно защищённый от перехвата канал передачи сообщений, шифры вообще не нужны: секретные сообщения можно передавать по этому каналу. Если же передавать ключ системы Вернама с помощью другого шифра (например, DES), то полученный шифр окажется защищённым ровно настолько, насколько защищён DES. При этом, поскольку длина ключа та же, что и длина сообщения, передать его не проще, чем сообщение. Шифроблокнот на физическом носителе можно украсть или скопировать[8].
  • Шифр Вернама чувствителен к любому нарушению процедуры шифрования. Бывали случаи, когда одна и та же страница блокнота по различным причинам применялась дважды. Например, среди всего объёма советской шифрованной переписки, перехваченной разведкой США в 40-х годах прошлого века, были обнаружены сообщения, закрытые дважды использованной гаммой. Период этот длился не очень долго, потому что уже после первых успехов американских криптоаналитиков в конце 1940-х годов в спецслужбах СССР узнали о серьёзных проблемах с надёжностью своей шифропереписки. Такие сообщения были расшифрованы в течение 40 последующих лет в рамках секретного проекта «Venona», документы которого были не так давно рассекречены и выложены на сайте АНБ[10].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]