2.1. Шифры перестановки

Р ассмотрим шифр перестановки, предназначенный для зашифрования сообщения длиной n символов. Его можно представить с помощью таблицы

где - номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, - номер места для второй буквы и т.д. В верхней строке таблицы выписаны по порядку числа от 1 до n, а в нижней - те же числа, но в произвольном порядке. Такая таблица называется перестановкой степени n.

Н апример, если для преобразования используется подстановка типа:

то слово ПРИКАЗ зашифровывается в ИКЗРПА.

2.2. Шифры подстановки (замены)

В криптографии рассматриваются следующие типы подстановки: моноалфавитная, полиалфавитная и полиграммная.

При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифротекста из этого же алфавита. Простым и самым древним из известных подстановочных шифров является шифр, который использовал Гай Юлий Цезарь. В шифре Цезаря каждая буква алфавита заменяется буквой, находящейся на три позиции дальше в этом же алфавите, т.е. k = 3.

Таблица 1.1.

Буква	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л
Код	01	02	03	04	05	06	07	08	09	10	11	12
Буква	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч
Код	13	14	15	16	17	18	19	20	21	22	23	24
Буква	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я	пробел
Код	25	26	27	28	29	30	31	32	33

Данный алгоритм зашифрования можно выразить следующими формулами, где каждая буква открытого текста M заменяется буквой шифрованного текста. В общем виде при любом сдвиге

C = E(M) = (M + k) mod(N), где k = 1,…,32 для русского алфавита.

Алгоритм расшифрования имеет вид

M = D(C) = (C – k) mod (N).

Если русский текст зашифрован с помощью шифра Цезаря, то с помощью простого перебора 32 возможных вариантов ключей можно легко раскрыть шифр.

Полиграммные шифры, базируются на методе многобуквенного шифрования. В шифре Плейфейера комбинации, состоящие из двух букв (биграммы), открытого текста M рассматриваются как самостоятельные единицы, преобразуемые в биграммы шифрованного текста. Поскольку в алфавите 32 буквы, а биграмм 32 x 32 =1024, то идентифицировать биграммы сложнее, чем отдельные буквы. Поэтому шифр Плейфейера надёжнее простых моноалфавитных шифров.

В основу многобуквенных шифров (шифр Хилла) положен принцип замены каждых M_i - последовательных букв открытого текста C_i - буквами шифрованного текста. Подстановка определяется m линейными уравнениями, в которых каждому символу присваивается определенное числовое значение. Пусть m = 3, тогда в векторной форме система уравнений выглядит следующим образом:

где C и M – векторы размерности 3, представляющие шифрованный и открытый текст соответственно; K – матрица размерности 3 x 3, является ключом шифрования по mod N. Преимущество шифра Хилла состоит в том, что он полностью маскирует частоту вхождения отдельных букв; чем больше размер матрицы, тем больше в шифрованном тексте скрывается информации о различиях в значениях частоты появления других комбинаций символов. Например, шифр с матрицей 3 х 3 скрывает частоту появления не только отдельных букв, но и двухбуквенных комбинаций.

Шифры, использующие несколько моноалфавитных подстановок, применяемых в ходе шифрования открытого текста в зависимости от определённых условий, называются полиалфавитными шифрами.

Примером полиалфавитного шифра замены является система Виженера. Шифрование происходит по таблице, которая представляет собой квадратную матрицу размерностью n x n, где n – число букв используемого алфавита.

На рис. 1.3 показана таблица Виженера для русского языка (32 буквы и пробел). Первая строка содержит все буквы алфавита. Каждая следующая строка получается из предыдущей циклическим сдвигом последней на одну букву влево.

На первом этапе шифрования выбирается ключ (ключевая фраза). На втором этапе под каждой буквой исходного сообщения последовательно записываются буквы ключа (если ключ оказался короче сообщения, то его используют несколько раз). Каждая буква шифртекста находится на пересечении столбца таблицы, определяемого буквой открытого текста, и строки, определяемой буквой ключа. Пусть, например, требуется зашифровать сообщение ШИФРЫ ЗАМЕНЫ с помощью ключа Х А К Е Р. Запишем строку исходного текста с расположенной под ней строкой с циклически повторяемым ключом:

Ш И Ф Р Ы З А М Е Н Ы

Х А К Е Р Х А К Е Р Х

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

М И Ю Х Л Ы А Ц К Э Р

Расшифрование полученной криптограммы производится следующим образом. Под буквами шифртекста последовательно записываются буквы ключа; в строке таблицы, соответствующей очередной букве ключа, производят поиск соответствующей буквы шифртекста. Находящаяся над ней в первой строке таблицы буква является соответствующей буквой исходного текста, то есть первая буква текста определяется по схеме

по строке по столбцу

(Х → М → Ш).

Рис. 1.3. Таблица Виженера