Поточные шифры простой замены

Наибольшее распространение получили поточные шифры простой замены, множества шифрвеличин и шифробозначений которых совпадают с алфавитом открытого текста. Как указывалось в главе 2, ключом такого шифра является подстановка k на множестве А, верхняя строка которой представляет собой естественную последовательность букв алфавита, а нижняя – систематически перемешанную или случайную последовательность букв из А.

Помимо явного задания (в виде двустрочной записи) ключ может быть задан некоторой формулой, как, например, для определяемого ниже шифра Цезаря (который иногда называют также сдвиговым шифром) и аффинного шифра. При использовании этих шифров буквы алфавита А удобно ото­ждествлять с их порядковыми номерами, так что, например, для латинского алфавита

аº0, bº1,..., zº25.

Шифр Цезаря

K=Z₂₆.

Для x=(x₁,..,x_l), y=(y₁,...,y_l),

k Î К полагаем

у = Е_k(х) =(x₁ +k,..., x_l +k),

х = D_k(у) = (у₁ + (26 – k),..., у_l + (26 – k)),

где + и • – операции кольца вычетов Z₂₆.

Аффинный шифр

K=Z*₂₆ x Z_26. Для k=(a,b) ÎK, a¹ 0,

x=(x₁,..,x_l), y=(y₁,...,y_l), полагаем

у = Е_k(х) =(a×x₁ +b,...,a×x_l +b),

х = D_k(у) =((у₁ + (26 – b))×a ^-1,..., (у_l + (26 – b))×a ^-1),

где + и • – операции кольцаZ , аa ^-1– элемент из муль­типликативной группы Z*₂₆ , обратный к а.

Пример

Зашифруем слово CRYPTOGRAPHY с помощью аффин­ного шифра, полагая k=(3,5). Данный ключ индуцирует следующую подстановку на Z :

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

5 8 11 14 17 20 23 0 3 6 9 12 15 18 21 24 1 4 7 10 13 16 19 22 25 2

Если декодировать числа в буквы, то получим следующее соответствие для букв:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

F I L O R U X A D G J M P S V Y B E H K N Q T W Z C

Слову CRYPTOGRAPHY соответствует числовая последовательность х=(2,17,24,15,19,14,9,17,0,15,7,24). Зашифровать открытый текст мы можем двумя способами. Во-первых, можно воспользоваться полученной подстановкой, заменяя каждую букву слова (найденную в верхней строке) ее образом в нижней строке: LEZYKVXEFYAZ. Во-вторых, можно вычислить значение функции зашифрования Е_k(х), исходя из ее определения:

у= Е_k(х)=(3×2+5, 3×17+5, 3×24+5, 3×15+5, 3×19+5, 3×14+5, 3×9+5, 3×17+5, 3×0+5, 3×15+5, 3×7+5, 3×24+5)=(11,4,25,24,10,21,23,4,5,24,0,25).

В буквенном эквиваленте у совпадает с полученным ранее шифрованным текстом.

Для расшифрования у следует вычислить 3^-1 в группе Z*₂₆. Очевидно, что 3^-1 =9. Теперь расшифруем у в соответствии с определением правила расшифрования:

х = D_k(у) =((11+21)•9, (4+21)•9, (25+21)•9, (24+21)•9, (10+21)×9, (21+21)×9, (23+21)× 9, (4+21)× 9,(5+21)× 9, (24 + 21)•9, (0 + 21)•9, (25 + 21)•9)= =(2,17,24,15,19,14,6,17,0,15,7,24).

Здесь мы воспользовались определением операций сло­жения и умножения в кольце Z₂₆, заменяя результат обычных целочисленных вычислений остатком от деления на 26.

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

Теорема. Отображение f : Z_n—> Z_n определяемое для фиксированных a,bÎZ_n формулой f(x) = а x + b(mod n), является биективным тогда и только тогда, когда (а,п)=1.

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

Пример (шифра простой неравнозначной замены)

Рассматривается прямоугольник размером 4 х 7, в кото­рый записан систематически перемешанный английский ал­фавит (расширенный символами "." и знаком раздела "/"), построенный на основе ключевого слова INCITATUS:

Шифры замены

Нумерация букв алфавита произведена по столбцам (сверху вниз), при этом восемь самых частых букв (A,E,I,N,0,R,S,T) занумерованы числами от 0 до 7, а осталь­ные – двузначными числами от 80 до 99. Такую таблицу легко запомнить. Работать же удобнее с эквивалентной таб­лицей:

0 1 2 3 4 5 6 7 8 9

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