Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
100
Глава 5
Шифры замены
Мы будем рассматривать лишь однозначные замены (см. главу 3), для которых правило зашифрования является обычной однозначной функцией. Одноалфавитные однозначные замены обычно называют шифрами простой замены.
§ 5.1. Поточные шифры простой замены
Наибольшее распространение получили поточные шифры простой замены, множества шифрвеличин и шифробозначе-ний которых совпадают с алфавитом открытого текста^. Как указывалось в главе 2, ключом такого шифра является подстановка к на множестве А, верхняя строка которой представляет собой естественную последовательность букв алфавита, а нижняя — систематически перемешанную или случайную последовательность букв из А (см. Приложение 1).
Помимо явного задания (в виде двустрочной записи) ключ может быть задан некоторой формулой, как, например, для определяемого ниже шифра Цезаря (который иногда называют также сдвиговым шифром) и аффинного шифра. При использовании этих шифров буквы алфавита А удобно отождествлять с их порядковыми номерами, так что, например, для латинского алфавита
а = 0, b = 1,..., z = 25 .
Шифр Цезаря
L
X = Y = \JZ26,K = Z26. Для х = (х1,..,х1),у = (у1,...,у1),
I = 1
к є К полагаем
у = Ек(х) = (х, +к,..., X1'+ к),
101
Гпава 5
X = Dk (у) = (yt + (26 - к),..., у, + (26 - к)), где + и • — операции кольца вычетов Z26.
Аффинный шифр
X = Y = [}Z'26,K = Z'26xZ26. Для к = (а,Р)єК, а* О,
/=1
X = (X1,...,X1), у = .,у,), полагаем
У = Ek(x) = (axl + р,...,ах,+ р),
X = Dk (у) = (Cv1 + (26- P)) (у, + (26- P)) • яГ1),
где + и • — операции кольца Z , а а~х — элемент из мультипликативной группы Z26, обратный к а .
Пример
Зашифруем слово CRYPTOGRAPITVr с помощью аффинного шифра, полагая к = (3,5). Данный ключ индуцирует
следующую подстановку на Z :
О 1 23456789 10 11 12
5 8 11 14 17 20 23 0 3 6 9 12 15
13 14 15 16 17 18 19 20 21 22 23 24 25
18 21 24 1 4 7 10 13 16 19 22 25 2
Если декодировать числа в буквы, то получим следующее соответствие для букв:
102
Шифры замены
ABCDEFGH I JKLM F I LORUXADGJMP N OPQRSTUVWXYZ SVYBEHKNQTWZC
Слову CRYPTOGRAPHY соответствует числовая последовательность х = (2,17,24,15,19,14,9,17,0,15,7,24). Зашифровать открытый текст мы можем двумя способами. Во-первых, можно воспользоваться полученной подстановкой, заменяя каждую букву слова (найденную в верхней строке) ее образом в нижней строке: LEZYKVXEFYAZ. Во-вторых, можно вычислить значение функции зашифрования Ek (х), исходя из ее определения:
у = Ек(х) = (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 в группе Z26. Очевидно, что 3-1 =9. Теперь расшифруем у в соответствии с определением правила расшифрования:
X = Dk 0>) = ((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).
103
І лава 5
Здесь мы воспользовались определением операций сложения и умножения в кольце Z26, заменяя результат обычных
целочисленных вычислений остатком от деления на 26.
В связи с рассмотрением аффинного шифра полезно напомнить один хорошо известный алгебраический результат.
Теорема. Отображение f : Zn —>Zn, определяемое для фиксированных а, Ъ є Zn формулой
/ (а) = аа + b(modn),
является биективным тогда и только тогда, когда (а,п) = \.
До сих пор мы предполагали, что шифробозначениями являются отдельные знаки алфавита. Однако это вовсе не обязательное условие. Как отмечалось в гл. 3, имеются шифры равнозначной замены и шифры разнозначной замены. В первом случае все шифробозначения имеют одинаковые значности, например один, два и т. д. Во втором — разные значности, например, некоторые шифробозначения могут быть отдельными знаками, другие — состоять из пары или большего числа знаков. По соображениям экономии и скорости шифрования значность шифробозначений не должна быть большой. В большинстве известных примеров разнозначных шифров значность шифробозначений не превосходит двух. Приведем один из таких примеров [Вес97].
Пример (шифра простой неравнозначной замены)
Рассматривается прямоугольник размером 4x7, в который записан систематически перемешанный английский алфавит (расширенный символами “ ” и знаком раздела построенный на основе ключевого слова INCITATUS:
104
Шифры замены
1 N С T А U S
0 1 86 3 5 94 6
в D E F G H J
80 83 2 89 91 95 98
К L M О P Q R
81 84 87 4 92 96 7
V W X Y Z /
82 85 88 90 93 97 99
Нумерация букв алфавита произведена по столбцам (сверху вниз), при этом восемь самых частых букв (A,E,I,N,0,R,S,T) занумерованы числами от 0 до 7, а остальные — двузначными числами от 80 до 99. Такую таблицу легко запомнить. Работать же удобнее с эквивалентной таблицей:
0 1 2 3 4 5 6 7 8 9
