Шифр Вернама

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

История

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

Впервые описан Фрэнком Миллером в 1882[4][5][6].

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

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

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

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

Описание

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

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

  1. Иметь случайное дискретное равномерное распределение: [math]\displaystyle{ P_{k} (k)=1/2^{N} }[/math], где 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

При шифровании преобразование производится по таблице Виженера (сложение индексов символов по модулю длины алфавита даёт эту таблицу).

При этом буква ключа — это столбец, буква открытого текста — строка, а шифротекст — это буква на пересечении.

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

Криптографическая стойкость

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

Приведём доказательство абсолютной криптографической стойкости. Пусть сообщение представлено двоичной последовательностью длины [math]\displaystyle{ N: m = m_{1},m_{2},\ldots,m_{n} }[/math]. Распределение вероятности сообщений [math]\displaystyle{ P_{m} (m) }[/math] может быть любым. Ключ так же представлен двоичной последовательностью [math]\displaystyle{ k=k_{1},k_{2},\ldots,k_{n} }[/math] той же длины, но с равномерным распределением [math]\displaystyle{ P_{k} (k)=1/2^{N} }[/math] для всех ключей.

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

[math]\displaystyle{ C = M \oplus K = (m_{1} \oplus k_{1}, m_{2} \oplus k_{2},\ldots,m_{N} \oplus k_{N}) }[/math]

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

[math]\displaystyle{ M = C \oplus K = (c_{1} \oplus k_{1}, c_{2} \oplus k_{2},\ldots,c_{N} \oplus k_{N}) }[/math]

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

[math]\displaystyle{ P(c=a)=P (m \oplus k = a)=\sum_{m} {P(m)}P(m \oplus k = a|m) = \sum_{m} {P(m)1/2^{N}} =1/2^{N} }[/math]

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

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

[math]\displaystyle{ P(m=a,c=b)=P(m=a)P(c=b|m=a) }[/math]

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

[math]\displaystyle{ P(c=b|m=a)=P(m \oplus k = b|m=a)=P(k=b \oplus a|m=a)=P(k=b \oplus a)=1/2^{N}, }[/math]

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

[math]\displaystyle{ P(c=b|m= a)=1/2^{N} }[/math]

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

[math]\displaystyle{ P(m=a,c=b)=P(m=a)1/2^{N} }[/math]

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

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

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

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

Недостатки

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

Примечания

  1. ↑ Симметричные алгоритмы.
  2. ↑ 2,0 2,1 2,2 2,3 2,4 Фомичёв, 2003.
  3. ↑ Мао, 2005.
  4. ↑ Miller, Frank. Telegraphic code to insure privacy and secrecy in the transmission of telegrams. — C.M. Cornwell, 1882.
  5. ↑ Bellovin, Steven M. (2011). «Frank Miller: Inventor of the One-Time Pad». Cryptologia 35 (3): 203–222. doi:10.1080/01611194.2011.583711. ISSN 0161-1194.
  6. ↑ John Markoff. Codebook Shows an Encryption Form Dates Back to Telegraphs (July 25, 2011).
  7. ↑ US 1310719 A Patent
  8. ↑ 8,0 8,1 8,2 Бабаш, et al., 2003.
  9. ↑ Криптография (недоступная ссылка). Дата обращения: 8 февраля 2014. Архивировано 2 ноября 2013 года.
  10. ↑ Габидулин, Кшевецкий, Колыбельников, 2011, с. 41—43.
  11. ↑ 11,0 11,1 11,2 One-time Pad.
  12. ↑ Frequently Asked Questions.
  13. ↑ Киви, 2005.

Литература

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Шифр_Вернама&oldid=5850389