Шифр Вернама

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

Шифр Вернама (англ. Verrnam Cipher, другое название One-time pad — схема одноразовых блокнотов) — система симметричного шифрования, впервые предложенная в 1882 году Ф. Миллером[1][2] и заново изобретённая в 1917 году сотрудником AT&T Гилбертом Вернамом[3]. Шифр Вернама является единственной системой шифрования, для которой доказана абсолютная криптографическая стойкость[4]. При этом он является одной из простейших криптосистем[5].

История[править | править исходный текст]

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

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

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

Описание[править | править исходный текст]

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


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

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

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

Ключ EVTIQWXQVVOPMCXREPYZ
Открытый текст ALLSWELLTHATENDSWELL
Шифротекст EGEAMAIBOCOIQPAJATJK
Шифрограмма EGEAM AIBOC OIQPA JATJK

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

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

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

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

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

C = M \oplus K =  (m_{1} \oplus k_{1},  m_{2} \oplus k_{2},\ldots,m_{N} \oplus k_{N})

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

M = C \oplus K = (c_{1} \oplus k_{1},  c_{2} \oplus k_{2},\ldots,c_{N} \oplus k_{N})

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

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

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

P(m=a,c=b)=P(m=a)P(c=b|m=a)

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

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},

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

P(c=b|m= a)=1/2^{N}

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

P(m=a,c=b)=P(m=a)1/2^{N}

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

Область применения[править | править исходный текст]

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

В настоящее время шифрование Вернама используется достаточно редко. Это связано с тем, что современные методы криптографии развиты достаточно хорошо для того, чтобы удовлетворять потребностям пользователей. Однако с развитием технологий и с увеличением доступных компьютерных мощностей, растёт и вероятность успешной атаки. Современные носители данных могут хранить огромное количество случайных ключей, а современные генераторы случайных чисел позволяют производить случайные ключи достаточного для использования в шифре Вернама качества. Всё это повышает актуальность использования шифра Вернама[9].

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

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

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

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

Недостатки[править | править исходный текст]

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


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

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

Шифр Вернама в искусстве[править | править исходный текст]

См. также[править | править исходный текст]

Примечания[править | править исходный текст]


Литература[править | править исходный текст]

  1. Фомичёв В.М. Дискретная математика и криптология. Курс лекций. (рус.) // Москва ДиалогМИФИ. — 2003. — С. 239 - 246.
  2. Э.М.Габидулин, А.С.Кшевецкий, А.И.Колыбельников Защита Информации (рус.). — 2011. — С. 41 - 43. — ISBN 978-5-7417-0377-9.
  3. Венбо Мао Современная криптография: теория и практика. (рус.) // Вильямс. — 2005. — С. 255. — ISBN 5-8459-0847-7(рус).
  4. Robert L. Benson The Venona Story (англ.) // Center for Cryptologic History National Security Agency.


Ссылки[править | править исходный текст]

  1. Симметричные алгоритмы (Руссикй).
  2. Криптографы научились шифровать сообщения куском стекла (Руссикй).
  3. А. В. Бабаш, д. ф.-м. н., профессор, Ю. И. Гольев, Д. А. Ларин, к. т. н., Г. П. Шанкин, д. т. н., профессор Криптографические идеи XIX века (Руссикй) // журнал "Конфидент". — 2003.
  4. Dirk Rijmenants One-time Pad (англ.).
  5. Marcus J. Ranum One-Time-Pad (Vernam's Cipher) Frequently Asked Questions (англ.).
  6. Берд Киви Цена Ошибки (рус.). — 2005.