Обнаружение и скрытие данных Тема-3. Шифр Вернама. Идеальная секретность, Генераторы случайных и псевдослучайных чисел

Одноразовый блокнот Шифр Вернама Шифр Вернама (англ. Verrnam Cipher) система симметричного шифрования, изобретённая в 1917 году сотрудником AT&T Гилбертом Вернамом[1]. Шифр является разновидностью криптосистемы одноразовых блокнотов. В нём используется булева функция «Исключающее ИЛИ». Шифр Вернама является примером системы с абсолютной криптографической стойкостью[2]. При этом он считается одной из простейших криптосистем

Описание Для произведения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с ключом(называемым одноразовым блокнотом или шифроблокнотом). При этом ключ должен обладать тремя критически важными свойствами: быть истинно случайным; совпадать по размеру с заданным открытым текстом; применяться только один раз. Шифр назван в честь телеграфиста AT&T Гильберта Вернама, который в году построил телеграфный аппарат, который выполнял эту операцию автоматически надо было только подать на него ленту с ключом. Не будучи шифровальщик ом, тем не менее, Вернам верно заметил важное свойство свое го шифра каждая лента должна использоваться только один раз и после этого уничтожать с я. Это трудно применимо на практике поэтому аппарат был переделан на несколько закольцованных лент с взаимно простыми периодами.

История Шифр назван в честь телеграфиста AT&T Гильберта Вернама, который в 1917 году изобрел, а в 1919 запатентовал систему автоматического шифрования телеграфных сообщений. Вернам не использовал понятие «Исключающее ИЛИ» в патенте, но реализовал именно эту операцию в релейной логике. Каждый символ в сообщении преобразовывался побитовым XOR (исключающее ИЛИ) с ключом бумажной ленты[4]. Вернам создал устройство, производящее указанные операции автоматически, без участия шифровальщика. Тем самым было положено начало так называемому «линейному шифрованию», когда процессы шифрования и передачи сообщения происходят одновременно. До той поры шифрование было предварительным, поэтому линейное шифрование существенно повышало оперативность связи. Не будучи шифровальщиком, тем не менее, Вернам верно заметил важное свойство своего шифра каждая лента должна использоваться только один раз и после этого уничтожаться. Это трудно применимо на практике поэтому аппарат был переделан на несколько закольцованных лент с взаимно простыми периодами[5]. В 1949 году Клод Шеннон опубликовал работу, в которой доказал абсолютную стойкость шифра Вернама. Других шифров с этим свойством не существует. Это по сути означает, что шифр Вернама является самой безопасной криптосистемой из всех возможных. При этом условия, которым должен удовлетворять ключ, настолько сильны, что практическое использование шифра Вернама становится трудно осуществимым. Поэтому он используется только для передачи сообщений наивысшей секретности.

Описание Криптосистема была предложена для шифрования телеграфных сообщений, которые представляли собой бинарные тексты, в которых открытый текст представляется в коде Бодо (в виде пятизначных «импульсных комбинаций»). В этом коде, например, буква «А» имела вид ( ). На бумажной ленте цифре «1» соответствовало отверстие, а цифре «0» его отсутствие. Секретный ключ должен был представлять собой хаотичный набор букв того же самого алфавита [5].коде Бодо [5] Для получения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с секретным ключом. Так, например, при применении ключа ( ) на букву «А» ( ) получаем зашифрованное сообщение ( ): {\displaystyle (11000)\oplus (11101)=(00101)} Зная, что для принимаемого сообщения имеем ключ ( ), легко получить исходное сообщение той же операцией: {\displaystyle (00101)\oplus (11101)=(11000)} Для абсолютной криптографической стойкости ключ должен обладать тремя критически важными свойствами [2] :исключающее ИЛИключом [2] Иметь случайное равномерное распределение: {\displaystyle P_{k}(k)=1/2^{N}}, где k ключ, а N количество бинарных символов в ключе;

Совпадать по размеру с заданным открытым текстом; Применяться только один раз. Также хорошо известен так называемый шифр Вернама по модулю m, в котором знаки открытого текста, шифрованного текста и ключа принимают значения из кольца вычетов Z m. Шифр является обобщением оригинального шифра Вернама, где m = 2 [2]. [2] Например, кодирование шифром Вернама по модулю m = 26 (A=0,B=1,…, Z=25): Ключ: EVTIQWXQVVOPMCXREPYZ Открытый текст: ALLSWELLTHATENDSWELL (All's well that ends well) Шифротекст: EGEAMAIBOCOIQPAJATJK Без знания ключа такое сообщение не поддаётся анализу. Даже если бы можно было перепробовать все ключи, в качестве результата мы получили бы все возможные сообщения данной длины плюс колоссальное количество бессмысленных дешифровок, выглядящих как беспорядочное нагромождение букв. Но и среди осмысленных дешифровок не было бы никакой возможности выбрать искомую. Когда случайная последовательность (ключ) сочетается с неслучайной (открытым текстом), результат этого (шифротекст) оказывается совершенно случайным и, следовательно, лишённым тех статистических особенностей, которые могли бы быть использованы для анализа шифра.дешифровокшифротекст

Криптографическая стойкость В 1945 году Клод Шеннон написал работу «Математическая теория криптографии» (рассекреченную только после Второй мировой войны в 1949 г. как «Теория связи в секретных системах»), в которой доказал абсолютную стойкость шифра Вернама. То есть перехват шифротекста не даёт никакой информации о сообщении. С точки зрения криптографии, невозможно придумать систему безопаснее шифра Вернама [2]. Требования к реализации подобной схемы достаточно нетривиальны, поскольку необходимо обеспечить наложение уникальной гаммы, равной длине сообщения, с последующим её гарантированным уничтожением. В связи с этим коммерческое применение шифра Вернама не так распространено в отличие от схем с открытым ключом и он используется, в основном, для передачи сообщений особой важности государственными структурами [5].Клод Шеннон Теория связи в секретных системах [2]гаммы [5] Приведём доказательство абсолютной криптографической стойкости. Пусть сообщение представлено двоичной последовательностью длины {\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)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}}Что доказывает независимость шифротекстов и открытых текстов в этой системе. Это и означает абсолютную криптографическую стойкость

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