18
Открытый текст:
с м е н и т е ш и ф р
Ключ:
к с м е н и т е ш и ф
Криптограмма:
Ь Ю Т У Ц Ы Ш Ю Б Э Е
или из получающейся буква за буквой криптограммы:
Открытый текст:
с м е н и т е ш и ф р
Ключ:
к ь й п э ж щ я ш б ц
Криптограмма:
Ь Й П Э Ж Щ Я Ш Б Ц З
Эти
способы генерации ключевого потока предложил в своем
упоминавшемся трактате Виженер.
в) Шифр Вернама.
В 1917 году американский инженер Гилберт Вернам (1890-1960)
осуществил казалось бы несбыточную мечту криптографов: он предложил
шифр, в принципе не раскрываемый. Это
поточный шифр над двоичным
алфавитом с буквами 0 и 1. Открытый текст представляется в двоичном виде
(например, согласно телеграфному коду Бодо, где каждая буква заменяется
двоичной последовательностью длины 5), ключом является случайная
двоичная последовательность той же длины, которая используется только
один раз – для шифрования данного текста. Криптограмма получается
посимвольным сложением открытого текста и ключа по модулю 2. Заметим,
что поскольку по модулю 2 вычитание совпадает со сложением, для
дешифрования криптограмма посимвольно складывается с ключом.
Пусть, например, открытым текстом является
w h i t e (белый)
. В
кодовой таблице Бодо находим:
e – 00001,
h – 10100,
i – 00110,
t – 10000,
w –
10011, так что шифроваться будет двоичная последовательность (длины 25)
1001110100001101000000001. В качестве ключа возьмем двоичную запись
цифр после запятой в числе π=3,1415926536… .Для двоичного представления
любого числа от 0 до 15 достаточно четырех цифр: 0 – 0000, 1 – 0001, 2 –
0010, 3 – 0011, 4 – 0100, 5 – 0101, 6 – 0110, 7 – 0111, 8 – 1000, 9 – 1001, …, 15
–
1111.
Выбирая
первые
25
двоичных
знаков,
кодирующих
последовательность 1415926, находим ключ: 0001010000010101100100100.
19
Для получения криптограммы посимвольно складываем по модулю 2
двоичные коды открытого текста и ключа:
1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1
+
2
0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0
=
1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1
(Обратим внимание на то, что при суммировании (снизу вверх)
криптограммы и ключа в самом деле получается открытый текст).
Почему же шифр Вернама не раскрываем? Дело в том, что, если
известна криптограмма, и ее длина равна
n двоичных разрядов (битов), то,
перебирая все возможные ключи (т.е. все возможные двоичные
поcледовательности длины
n битов) и складывая их посимвольно по модулю
2 с криптограммой, можно получить все возможные двоичные тексты длины
n битов. Какой из них был подлинным сообщением, установить невозможно.
Так,
в
рассмотренном
примере,
зная
криптограмму
1000100100011000100100101 и не зная ключа, взломщик шифра попробует
испытать все 2
25
=33 554 432
возможных ключей, т.е. двоичных
последовательностей длины 25 битов. На каком-то шаге он наткнется на
истинный ключ и получит, складывая с ним криптограмму,
w h i t e. Не зная,
в самом ли деле это подлинный открытый текст, он в процессе дальнейшего
перебора дойдет до ключа 0100010110011110011101010 и, сложив его по
Виженеру с криптограммой, получит 1100110010000110111001111, что по
таблице Бодо дает
b l a c k (черный). Далее ему попадется в
качестве
возможного ключа последовательность 0101101110011010100001001 и в
качестве
возможного
открытого
текста
он
увидит
1101001010000010000101100 –
g r e e n (зеленый).
Найдите ключ, при дешифровании на котором рассматриваемая криптограмма даст
открытый текст
b r o w n (коричневый) (у Бодо буква
O кодируется как
11000).
32 буквы русского алфавита (без ё) закодированы пятибитовыми векторами:
а –
00001,
б – 00010,
в - 00011, …,
ю – 11111,
я – 00000. Проверьте, что при подходящем
подборе ключа любая буква может быть зашифрована как
Я.