Шифр Вернама

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

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

История

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<math>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} </math>

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

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

<math>P(m=a,c=b)=P(m=a)P(c=b|m=a)</math>

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

<math>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>P(c=b|m= a)=1/2^{N} </math>

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

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

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

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

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

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

Недостатки

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

• Недостатком использования шифра Вернама является отсутствие подтверждения подлинности и целостности сообщения. Получатель не может удостовериться в отсутствии повреждений или в подлинности отправителя. Если третья сторона каким-нибудь образом узнает сообщение, она легко восстановит ключ и сможет подменить послание на другое такой же длины. Решением проблемы является применение хэш-функции. От открытого текста вычисляется хэш-функция, и её значение шифруется вместе с сообщением. При каком-либо изменении сообщения значение хэш-функции изменится. Таким образом, даже если злоумышленник заполучил шифроблокнот, не зная алгоритм вычисления хэш-функции, он не сможет использовать его для передачи информации.

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

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

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

См. также

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

Литература

• Robert L. Benson [www.nsa.gov/about/_files/cryptologic_heritage/publications/coldwar/venona_story.pdf The Venona Story] (англ.) // Center for Cryptologic History National Security Agency.

Ссылки

• [students.uni-vologda.ac.ru/pages/pm00/kan/symmetric.htm#vernam Симметричные алгоритмы] (рус.).
• Dirk Rijmenants [users.telenet.be/d.rijmenants/en/onetimepad.htm One-time Pad] (англ.).
• Marcus J. Ranum [www.ranum.com/security/computer_security/papers/otp-faq/index.htm#head_usebook One-Time-Pad (Vernam's Cipher) Frequently Asked Questions] (англ.).
• Берд Киви [web.archive.org/web/20131224102836/www.homepc.ru/offline/print/2005/106/180493/ Цена Ошибки]. — 2005.

Отрывок, характеризующий Шифр Вернама

– Как же звезда то в образе очутилась? – спросил Пьер.
– В генералы и матушку произвели? – сказал князь Aндрей улыбаясь.
Пелагеюшка вдруг побледнела и всплеснула руками.
– Отец, отец, грех тебе, у тебя сын! – заговорила она, из бледности вдруг переходя в яркую краску.
– Отец, что ты сказал такое, Бог тебя прости. – Она перекрестилась. – Господи, прости его. Матушка, что ж это?… – обратилась она к княжне Марье. Она встала и чуть не плача стала собирать свою сумочку. Ей, видно, было и страшно, и стыдно, что она пользовалась благодеяниями в доме, где могли говорить это, и жалко, что надо было теперь лишиться благодеяний этого дома.
– Ну что вам за охота? – сказала княжна Марья. – Зачем вы пришли ко мне?…
– Нет, ведь я шучу, Пелагеюшка, – сказал Пьер. – Princesse, ma parole, je n'ai pas voulu l'offenser, [Княжна, я право, не хотел обидеть ее,] я так только. Ты не думай, я пошутил, – говорил он, робко улыбаясь и желая загладить свою вину. – Ведь это я, а он так, пошутил только.
Пелагеюшка остановилась недоверчиво, но в лице Пьера была такая искренность раскаяния, и князь Андрей так кротко смотрел то на Пелагеюшку, то на Пьера, что она понемногу успокоилась.


Странница успокоилась и, наведенная опять на разговор, долго потом рассказывала про отца Амфилохия, который был такой святой жизни, что от ручки его ладоном пахло, и о том, как знакомые ей монахи в последнее ее странствие в Киев дали ей ключи от пещер, и как она, взяв с собой сухарики, двое суток провела в пещерах с угодниками. «Помолюсь одному, почитаю, пойду к другому. Сосну, опять пойду приложусь; и такая, матушка, тишина, благодать такая, что и на свет Божий выходить не хочется».
Пьер внимательно и серьезно слушал ее. Князь Андрей вышел из комнаты. И вслед за ним, оставив божьих людей допивать чай, княжна Марья повела Пьера в гостиную.
– Вы очень добры, – сказала она ему.
– Ах, я право не думал оскорбить ее, я так понимаю и высоко ценю эти чувства!
Княжна Марья молча посмотрела на него и нежно улыбнулась. – Ведь я вас давно знаю и люблю как брата, – сказала она. – Как вы нашли Андрея? – спросила она поспешно, не давая ему времени сказать что нибудь в ответ на ее ласковые слова. – Он очень беспокоит меня. Здоровье его зимой лучше, но прошлой весной рана открылась, и доктор сказал, что он должен ехать лечиться. И нравственно я очень боюсь за него. Он не такой характер как мы, женщины, чтобы выстрадать и выплакать свое горе. Он внутри себя носит его. Нынче он весел и оживлен; но это ваш приезд так подействовал на него: он редко бывает таким. Ежели бы вы могли уговорить его поехать за границу! Ему нужна деятельность, а эта ровная, тихая жизнь губит его. Другие не замечают, а я вижу.
В 10 м часу официанты бросились к крыльцу, заслышав бубенчики подъезжавшего экипажа старого князя. Князь Андрей с Пьером тоже вышли на крыльцо.
– Это кто? – спросил старый князь, вылезая из кареты и угадав Пьера.
– AI очень рад! целуй, – сказал он, узнав, кто был незнакомый молодой человек.
Старый князь был в хорошем духе и обласкал Пьера.
Перед ужином князь Андрей, вернувшись назад в кабинет отца, застал старого князя в горячем споре с Пьером.
Пьер доказывал, что придет время, когда не будет больше войны. Старый князь, подтрунивая, но не сердясь, оспаривал его.
– Кровь из жил выпусти, воды налей, тогда войны не будет. Бабьи бредни, бабьи бредни, – проговорил он, но всё таки ласково потрепал Пьера по плечу, и подошел к столу, у которого князь Андрей, видимо не желая вступать в разговор, перебирал бумаги, привезенные князем из города. Старый князь подошел к нему и стал говорить о делах.
– Предводитель, Ростов граф, половины людей не доставил. Приехал в город, вздумал на обед звать, – я ему такой обед задал… А вот просмотри эту… Ну, брат, – обратился князь Николай Андреич к сыну, хлопая по плечу Пьера, – молодец твой приятель, я его полюбил! Разжигает меня. Другой и умные речи говорит, а слушать не хочется, а он и врет да разжигает меня старика. Ну идите, идите, – сказал он, – может быть приду, за ужином вашим посижу. Опять поспорю. Мою дуру, княжну Марью полюби, – прокричал он Пьеру из двери.
Пьер теперь только, в свой приезд в Лысые Горы, оценил всю силу и прелесть своей дружбы с князем Андреем. Эта прелесть выразилась не столько в его отношениях с ним самим, сколько в отношениях со всеми родными и домашними. Пьер с старым, суровым князем и с кроткой и робкой княжной Марьей, несмотря на то, что он их почти не знал, чувствовал себя сразу старым другом. Они все уже любили его. Не только княжна Марья, подкупленная его кроткими отношениями к странницам, самым лучистым взглядом смотрела на него; но маленький, годовой князь Николай, как звал дед, улыбнулся Пьеру и пошел к нему на руки. Михаил Иваныч, m lle Bourienne с радостными улыбками смотрели на него, когда он разговаривал с старым князем.
Старый князь вышел ужинать: это было очевидно для Пьера. Он был с ним оба дня его пребывания в Лысых Горах чрезвычайно ласков, и велел ему приезжать к себе.
Когда Пьер уехал и сошлись вместе все члены семьи, его стали судить, как это всегда бывает после отъезда нового человека и, как это редко бывает, все говорили про него одно хорошее.


Возвратившись в этот раз из отпуска, Ростов в первый раз почувствовал и узнал, до какой степени сильна была его связь с Денисовым и со всем полком.
Когда Ростов подъезжал к полку, он испытывал чувство подобное тому, которое он испытывал, подъезжая к Поварскому дому. Когда он увидал первого гусара в расстегнутом мундире своего полка, когда он узнал рыжего Дементьева, увидал коновязи рыжих лошадей, когда Лаврушка радостно закричал своему барину: «Граф приехал!» и лохматый Денисов, спавший на постели, выбежал из землянки, обнял его, и офицеры сошлись к приезжему, – Ростов испытывал такое же чувство, как когда его обнимала мать, отец и сестры, и слезы радости, подступившие ему к горлу, помешали ему говорить. Полк был тоже дом, и дом неизменно милый и дорогой, как и дом родительский.
Явившись к полковому командиру, получив назначение в прежний эскадрон, сходивши на дежурство и на фуражировку, войдя во все маленькие интересы полка и почувствовав себя лишенным свободы и закованным в одну узкую неизменную рамку, Ростов испытал то же успокоение, ту же опору и то же сознание того, что он здесь дома, на своем месте, которые он чувствовал и под родительским кровом. Не было этой всей безурядицы вольного света, в котором он не находил себе места и ошибался в выборах; не было Сони, с которой надо было или не надо было объясняться. Не было возможности ехать туда или не ехать туда; не было этих 24 часов суток, которые столькими различными способами можно было употребить; не было этого бесчисленного множества людей, из которых никто не был ближе, никто не был дальше; не было этих неясных и неопределенных денежных отношений с отцом, не было напоминания об ужасном проигрыше Долохову! Тут в полку всё было ясно и просто. Весь мир был разделен на два неровные отдела. Один – наш Павлоградский полк, и другой – всё остальное. И до этого остального не было никакого дела. В полку всё было известно: кто был поручик, кто ротмистр, кто хороший, кто дурной человек, и главное, – товарищ. Маркитант верит в долг, жалованье получается в треть; выдумывать и выбирать нечего, только не делай ничего такого, что считается дурным в Павлоградском полку; а пошлют, делай то, что ясно и отчетливо, определено и приказано: и всё будет хорошо.
Вступив снова в эти определенные условия полковой жизни, Ростов испытал радость и успокоение, подобные тем, которые чувствует усталый человек, ложась на отдых. Тем отраднее была в эту кампанию эта полковая жизнь Ростову, что он, после проигрыша Долохову (поступка, которого он, несмотря на все утешения родных, не мог простить себе), решился служить не как прежде, а чтобы загладить свою вину, служить хорошо и быть вполне отличным товарищем и офицером, т. е. прекрасным человеком, что представлялось столь трудным в миру, а в полку столь возможным.
Ростов, со времени своего проигрыша, решил, что он в пять лет заплатит этот долг родителям. Ему посылалось по 10 ти тысяч в год, теперь же он решился брать только две, а остальные предоставлять родителям для уплаты долга.

Армия наша после неоднократных отступлений, наступлений и сражений при Пултуске, при Прейсиш Эйлау, сосредоточивалась около Бартенштейна. Ожидали приезда государя к армии и начала новой кампании.
Павлоградский полк, находившийся в той части армии, которая была в походе 1805 года, укомплектовываясь в России, опоздал к первым действиям кампании. Он не был ни под Пултуском, ни под Прейсиш Эйлау и во второй половине кампании, присоединившись к действующей армии, был причислен к отряду Платова.
Отряд Платова действовал независимо от армии. Несколько раз павлоградцы были частями в перестрелках с неприятелем, захватили пленных и однажды отбили даже экипажи маршала Удино. В апреле месяце павлоградцы несколько недель простояли около разоренной до тла немецкой пустой деревни, не трогаясь с места.
Была ростепель, грязь, холод, реки взломало, дороги сделались непроездны; по нескольку дней не выдавали ни лошадям ни людям провианта. Так как подвоз сделался невозможен, то люди рассыпались по заброшенным пустынным деревням отыскивать картофель, но уже и того находили мало. Всё было съедено, и все жители разбежались; те, которые оставались, были хуже нищих, и отнимать у них уж было нечего, и даже мало – жалостливые солдаты часто вместо того, чтобы пользоваться от них, отдавали им свое последнее.
Павлоградский полк в делах потерял только двух раненых; но от голоду и болезней потерял почти половину людей. В госпиталях умирали так верно, что солдаты, больные лихорадкой и опухолью, происходившими от дурной пищи, предпочитали нести службу, через силу волоча ноги во фронте, чем отправляться в больницы. С открытием весны солдаты стали находить показывавшееся из земли растение, похожее на спаржу, которое они называли почему то машкин сладкий корень, и рассыпались по лугам и полям, отыскивая этот машкин сладкий корень (который был очень горек), саблями выкапывали его и ели, несмотря на приказания не есть этого вредного растения.
Весною между солдатами открылась новая болезнь, опухоль рук, ног и лица, причину которой медики полагали в употреблении этого корня. Но несмотря на запрещение, павлоградские солдаты эскадрона Денисова ели преимущественно машкин сладкий корень, потому что уже вторую неделю растягивали последние сухари, выдавали только по полфунта на человека, а картофель в последнюю посылку привезли мерзлый и проросший. Лошади питались тоже вторую неделю соломенными крышами с домов, были безобразно худы и покрыты еще зимнею, клоками сбившеюся шерстью.
Несмотря на такое бедствие, солдаты и офицеры жили точно так же, как и всегда; так же и теперь, хотя и с бледными и опухлыми лицами и в оборванных мундирах, гусары строились к расчетам, ходили на уборку, чистили лошадей, амуницию, таскали вместо корма солому с крыш и ходили обедать к котлам, от которых вставали голодные, подшучивая над своею гадкой пищей и своим голодом. Также как и всегда, в свободное от службы время солдаты жгли костры, парились голые у огней, курили, отбирали и пекли проросший, прелый картофель и рассказывали и слушали рассказы или о Потемкинских и Суворовских походах, или сказки об Алеше пройдохе, и о поповом батраке Миколке.
Офицеры так же, как и обыкновенно, жили по двое, по трое, в раскрытых полуразоренных домах. Старшие заботились о приобретении соломы и картофеля, вообще о средствах пропитания людей, младшие занимались, как всегда, кто картами (денег было много, хотя провианта и не было), кто невинными играми – в свайку и городки. Об общем ходе дел говорили мало, частью оттого, что ничего положительного не знали, частью оттого, что смутно чувствовали, что общее дело войны шло плохо.