Шифр Вернама

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

Шифр Вернама (англ. 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].

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

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

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

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

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

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

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

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