Материал предоставлен https://it.rfei.ru

Поточные шифры

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

Книжный шифр.

В качестве ключа выбирается какая-либо книга с идентификатором некоторого стартового места в тексте (например, «третья буква в пятом абзаце второй главы»). Под открытым текстом подписывается текст книги, начиная с ключевого места. В следующем примере для удобства выставлены номера участвующих букв.

18 13 6 14 9 19 6 25 9 21 17 14 1 18 24 9 19 1 3119
сменитешифрнасчитают
улукоморьядубзеленый
201220111513151729 0 5 20 2 8 6 12 6 142810
6 25262524 0 2110 6 2122 2 3 26302125152729
ЕШЩШЧЯФЙЕФХБВЩЭФШОЪЬ

Во второй строке таблицы записан открытый текст, в третьей – ключ (А.С. Пушкин «Руслан и Людмила», Песнь Первая, с первой буквы), в шестой – криптограмма. В первой строке стоят номера букв открытого текста, в четвертой – номера букв ключа, в пятой – сумма по модулю 32 соответствующих букв открытого текста и ключа, т.е. номер получившейся буквы криптограммы.

Шифры с автоключами.

Первая буква ключа выбирается случайно, а далее он состоит из открытого текста:

Открытыйтекст: с м е н и т е ш и ф р

Ключ: ксменитешиф

Криптограмма: ЬЮТУЦЫШЮБЭЕ

или из получающейся буква за буквой криптограммы:

Открытыйтекст: с м е н и т е ш и ф р

Ключ: кьйпэжщяшбц

Криптограмма: ЬЙПЭЖЩЯШБЦЗ

Эти способы генерации ключевого потока предложил в своем упоминавшемся трактате Виженер.

Шифр Вернама.

В 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.

Для получения криптограммы посимвольно складываем по модулю 2 двоичные коды открытого текста и ключа:

1001110100001101000000001 %%+_2 %%
0001010000010101100100100 =
1000100100011000100100101

Обратим внимание на то, что при суммировании (снизу вверх) криптограммы и ключа в самом деле получается открытый текст.

Почему же шифр Вернама не раскрываем? Дело в том, что, если известна криптограмма, и ее длина равна 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 и в качестве возможного открытого текста он увидит 1101001010000010000101100g r e e n (зеленый).

Абсолютно стойкий шифр Вернама, к сожалению, мало пригоден для повседневной практики: ведь с каждым открытым текстом нужно связать индивидуальную случайную двоичную последовательность той же длины. Где взять столько случайных двоичных последовательностей? Современные компьютеры генерировать их не способны. Поэтому шифр Вернама применяется только в особо важных случаях.

Заметим, что тому, кто не имеет возможности использовать шифр Вернама, вполне доступны другие приемы надежной криптографической защиты информации. Последовательное применение трех разных шифров – один из них.

Модульная арифметика.Проверка знаний. Общие понятия и определения.