Шифр Вернама

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

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

История

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

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

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

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

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

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

Описание

Криптосистема была предложена для шифрования телетайпных сообщений — двоичных текстов, в которых открытый текст представлен в виде пятибитных «кодовых комбинаций» кода Бодо — Мюррея (одной из разновидностей кода Бодо). В этом коде, например, буква А имеет вид ${\displaystyle 11000}$. При записи на перфоленте логической «1» соответствует отверстие, а логическому «0» — его отсутствие.

Для получения шифротекста открытый текст объединяется операцией «исключающее „или“» с секретным ключом, представляющим собой хаотичный набор символов алфавита, используемого для представления открытого текста^[8]. Так, например, при применении ключа ${\displaystyle 11101}$ к букве А (${\displaystyle 11000}$) получается зашифрованное сообщение ${\displaystyle 00101}$: ${\displaystyle 11000\oplus 11101=00101}$. Зная, что для шифрования использовался ключ ${\displaystyle 11101}$, той же операцией легко получить исходное сообщение: ${\displaystyle 00101\oplus 11101=11000}$.

Для абсолютной криптографической стойкости ключ должен обладать тремя критически важными свойствами^[2]:

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

Также хорошо известен так называемый шифр Вернама по модулю m, в котором символы открытого текста, шифротекста и ключа принимают значения из кольца вычетов Z_m. Шифр является обобщением оригинального шифра Вернама, где 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].

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

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

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

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

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

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

${\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}}$

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

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

${\displaystyle P(m=a,c=b)=P(m=a)P(c=b|m=a)}$

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

${\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},}$

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

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

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

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

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

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

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

Также существует квантовый аналог одноразового блокнота, который можно использовать для обмена квантовыми состояниями по одностороннему квантовому каналу с полной секретностью, который иногда используется в квантовых вычислениях. Можно показать, что для обмена квантовым состоянием n-кубитов по одностороннему квантовому каналу требуется общий секрет, состоящий как минимум из 2n битов (по аналогии с классическим обменом сообщениями с полной секретностью, где для шифрования n битов требуется n-битный ключ). Схема, предложенная в 2000 году, достигает этой границы. Один из способов реализовать квантовый одноразовый блокнот — разделить 2n-битный ключ на n пар битов. Чтобы зашифровать квантовое состояние, для каждой пары битов i в ключе нужно применить врата X к кубиту i состояния тогда и только тогда, когда первый бит пары равен 1, и применить врата Z к кубиту i состояния тогда и только тогда, когда второй бит пары равен 1.

Дешифрование предполагает повторное применение этого преобразования, поскольку X и Z являются своими обратными значениями. Можно показать, что в квантовой обстановке это совершенно секретно. Одноразовый блокнот является примером постквантовой криптографии, поскольку идеальная секретность — это определение безопасности, которое не зависит от вычислительных ресурсов противника. Следовательно, противник с квантовым компьютером по-прежнему не сможет получить больше информации о сообщении, зашифрованном с помощью одноразового блокнота, чем противник с классическим компьютером.

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

Особенность

Уникальной особенностью шифра Вернама является возможность подмены исходного текста: для любых двух открытых текстов одинаковой длины T и T' существуют ключи K и K', переводящие их в один и тот же шифротекст C. Действительно, легко видеть, что ${\displaystyle K'=C\oplus T'}$.

Это может быть использовано в разведке. Предположим, некий агент занимается добычей военных секретов и послал цепочку C¡ зашифрованных сообщений. Контрразведка их перехватила, агент провалился. При обыске у него находят несколько экземпляров «использованных» ключей, которые он «случайно не уничтожил». Прочитав с их помощью некоторые донесения, контрразведчики из них узнаю́т, что агент занимался… всего лишь промышленным шпионажем (за что наказание должно быть мягче). На деле же эти «ключи» были заготовлены заранее на случай провала.

Недостатки

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

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

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

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

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

Примечания

1. Симметричные криптосистемы.
2. Фомичёв, 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. S2CID 35541360. Архивировано 4 февраля 2022. Дата обращения: 14 сентября 2022.
6. John Markoff (2011-07-25). "Codebook Shows an Encryption Form Dates Back to Telegraphs". The New York Times. Архивировано 21 мая 2013. Дата обращения: 26 июля 2011.
7. US 1310719 A Patent  (неопр.). Дата обращения: 19 октября 2015. Архивировано 24 сентября 2015 года.
8. Бабаш, et al., 2003.
9. Криптография  (неопр.). Дата обращения: 8 февраля 2014. Архивировано из оригинала 2 ноября 2013 года.
10. Габидулин, Кшевецкий, Колыбельников, 2011, с. 41—43.
11. One-time Pad.
12. One Time Pad FAQ.
13. Киви Бёрд, 2005.

Литература

• Фомичёв В. М. Дискретная математика и криптология: Курс лекций / под ред. Н. Д. Подуфалов — М.: Диалог-МИФИ, 2013. — С. 239—246. — 397 с. — ISBN 978-5-86404-185-7
• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
• Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — С. 255. — 768 с. — ISBN 978-5-8459-0847-6
• Robert L. Benson. The Venona Story (англ.). National Security Agency, Center for Cryptologic History. Дата обращения: 27 августа 2024. Архивировано 7 июня 2024 года.
• Бабаш А. В., Гольев Ю. И., Ларин Д. А., Шанкин Г. П. Криптографические идеи XIX века // Защита информации. Инсайд — СПб.: 2004. — вып. 3.

Ссылки

• Симметричные криптосистемы  (рус.). Архивировано из оригинала 22 января 2021 года.
• Dirk Rijmenants. One-time Pad (англ.). Дата обращения: 27 августа 2024. Архивировано 21 августа 2024 года.
• Marcus J. Ranum. One Time Pad Vernam Cipher FAQ (англ.). Дата обращения: 27 августа 2024. Архивировано 13 июня 2024 года.
• Киви Бёрд. Цена ошибки  (рус.) (17 марта 2005). Архивировано из оригинала 24 сентября 2015 года.