Криптография: Шифр Вернама и его программная реализация

В криптографии шифр Вернама известен также как «схема одноразовых блокнотов». Решение является системой симметричного шифрования, которая была изобретена в 1917 году сотрудниками AT&T Мейджором Джозефом Моборном и Гильбертом Вернамом.

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

1. Ключ для шифрования выбирается случайным образом.

2. Длина ключа должна быть равна длине открытого текста.

3. Ключ должен использоваться ТОЛЬКО один раз.

А теперь поподробней о самом шифре и процессе шифрования. Так как этот шифр был придуман для компьютерных систем, то следует заметить, что базируется он на двоичной арифметике. Надеюсь что вы знакомы с ней ;). Основным объектом рассмотрения в данном методе шифрования является логическая операция XOR (взаимоисключающее ИЛИ). Таким образом, так как у нас двоичная арифметика, то все операции будут осуществляется над нулем (0) и единицей (1). Логическая операция XOR, в отличие от операции OR, при логическом сравнении 0 и 1 дает 1, при сравнении 1 с 1 дает 0, а при 0 с 0 дает 0. Следовательно, если мы выполним операцию XOR над числами 10110 и 11010, то получим: 10110 xor11010 = 01100. Надеюсь что принцип работы операцииXOR понятен.

Далее, так как шифр работает с двоичной системой исчисления, необходимо понимать, что буквы — это всего лишь некоторая интерпретация числа, то есть число является кодом символа некоторой таблицы кодировок. К примеру, наиболее популярные таблицы кодировок это: ANSI, ASCII и UTF(unicode). Естественно, что в каждой таблице один и тот же символ может иметь разный код, поэтому, во избежании путаницы, имейте это ввиду и используйте одну и ту же кодировку при шифровании и дешифровании. Замечу, что использовать можно и свою (придуманную) кодировку. Кроме того, данный шифр может использоваться не только на компьютерах. Его можно применить и к тексту написанному на бумаге. Только перед применением надо сделать некие преобразования.

Таким образом, перед тем, как осуществить шифрование, необходимо перевести все символы в их однозначную числовую интерпретацию. Если Вы решили применить шифр в компьютерных системах, то для вас уже существуют соответствующие кодировки и язык программирования, выбранный Вами, скорее всего поддерживает явное или неявное преобразование. И вам остается только произвести над каждой парой операцию XOR. В различных языках это операция определяется по разному, приведу пример: для pasсal/Delphi/Assembler — xor, C/C++ — ^. Однако, если же Вы решили применить шифр Вернама к письменному тексту, то, к примеру, дайте каждой букве используемого вами алфавита, соответствующий ей порядковый номер в двоичной системе исчисления. Например, если вы используете русский алфавит (без учета буквы Ё) то это будет выглядеть так: а -> 00000, б -> 00001, в -> 00010, г -> 00011, … я -> 111111. Тем самым мы определили свою таблицу кодировки. После этого, написав сообщение и придумав ключ, преобразуйте каждый символ в их числовое значение, соответствующее вашей таблице кодировки, и после этого осуществляйте операцию XOR над каждой соответствующей парой. Так как данный метод шифрования является симметричным, следовательно, применив операцию XORк каждой паре символов шифр-текста (шифрограммы) и ключа, мы получим открытый текст.

Потоковые шифры на базе сдвиговых регистров активно использовались в годы войны, ещё задолго до появления электроники. Они были просты в проектировании и реализации.

В 1965 году Эрнст Селмер, главный криптограф норвежского правительства, разработал теорию последовательности сдвиговыхрегистров. Позже Соломон Голомб, математик Агентства Национальной Безопасности США, написал книгу под названием «Shift Register Sequences»(« Последовательности сдвиговых регистров»), в которой изложил свои основные достижения в этой области, а также достижения Селмера.

Большую популярность потоковым шифрам принесла работа Клода Шеннона, опубликованная в 1949 году, в которой Шеннон доказал абсолютную стойкость шифра Вернама (также известного, как одноразовый блокнот). В шифре Вернама ключ имеет длину, равную длине самого передаваемого сообщения. Ключ используется в качестве гаммы, и если каждый бит ключа выбирается случайно, то вскрыть шифр невозможно (т.к. все возможные открытые тексты будут равновероятны). До настоящего времени было придумано немало алгоритмов потокового шифрования. Такие как: A3, A5, A8, RC4,PIKE, SEAL, eSTREAM.

Режим гаммирования для поточных шифров

Простейшая реализация поточного шифра изображена на рисунке. Генератор гаммы выдаёт ключевой поток (гамму): . Обозначим поток битов открытого текста . Тогда поток битов шифротекста получается с помощью применения операции XOR: , где .

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: .

Очевидно, что если последовательность битов гаммы не имеет периода и выбирается случайно, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательные особенности. Так ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность ( она должна удовлетворять постулатам Голомба). Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр