Перестановочные шифры

Подстановочные шифры

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

- простой подстановочный шифр, илимоноалфавитный шифр, - это шифр, который каждый символ открытого текста заменяет соответствующим символом шифротекста. Простыми подстановочными шифрами являются криптограммы в газетах;

- однозвучный подстановочный шифр похож на простую подстановочную криптосистему за исключением того, что один символ открытого текста отображается на несколько символов шифротекста. Например, A может соответствовать 5, 13, 25 или 56, B - 7, 19, 31 или 42 и так далее;

- полиграммный подстановочный шифр - это шифр, который блоки символов шифрует по группам. Например, ABA может соответствовать RTQ, ABB может соответствовать SLL и так далее;

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

Знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящегося тремя символами правее по модулю 26 (A заменяется на D, B - на E, ... W - на Z , X - на A, Y - на B, Z - на C), представляет собой простой подстановочный фильтр. Он действительно очень прост, так как алфавит шифротекста представляет собой смещенный, а не случайно распределенный алфавит открытого текста.

Перестановочные шифры

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

где i1 – номер места шифротекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, i2 – номер места для второй буквы и т. д.

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

Зная подстановку, задающую преобразование, можно осуществить как шифрование, так и расшифрование текста. Например, если для преобразования используется подстановка

1 2 3 4 5 6

5 2 3 1 4 6

и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА.

Попробуйте расшифровать сообщение НЧЕИУК, полученное в результате преобразования с помощью указанной выше подстановки.

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

С увеличением числа n значение n! факториал растет очень быстро:

Таблица 1.1 – Значения N! для первых 10 натуральных чисел

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

Для использования на практике такой шифр неудобен, так как при больших значениях n приходится работать с длинными таблицами.

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

Зашифруем, например, указанным способом фразу:

ПРИМЕРМАРШРУТНОЙПЕРЕСТАНОВКИ

используя прямоугольник размера 47 Зашифрованная фраза выглядит так:

МАСТЕРРЕШРНОЕРМИУПВКЙТРПНОИ

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

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

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

Пример шифрования. Пусть в качестве ключа используется решетка 610, приведенная на рис. 1. 1.

Зашифруем с ее помощью текст

ШИФРРЕШЕТКАЯВЛЯЕТСЯ ЧАСТНЫМЛУЧАЕМШИФРАМАРШРУТНОЙ ПЕРЕСТАНОВКИ

Наложив решетку на лист бумаги, вписываем первые 15 (по числу вырезов) букв сообщения ШИФРРЕШЕТКАЯВЛЯ….. Сняв решетку, мы увидим текст, представленный на рис. 1. 2. Поворачиваем решетку на 180. В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. 1. 3. Затем поворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. 1.4, 1.5).

Получатель сообщения, имеющий точно такую же решетку, без труда прочтет исходный текст, наложив решетку на шифротекст по порядку четырьмя способами. Можно доказать, что число возможных трафаретов, то есть количество ключей шифра решетка, составляет Т = 4^mk. Этот шифр предназначен для сообщений длины n = 4mk. Число всех перестановок в тексте такой длины составит (4mk)!, что во много раз больше числа Т. Однако, уже при размере трафарета 88 число возможных решеток превосходит 4 миллиарда

Шифром вертикальной перестановки (ШВП) называется широко распространенная разновидность шифра маршрутной перестановки. В нем используется прямоугольник, в котором сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,1,4,7,2,6,3), и с его помощью надо зашифровать сообщение:

ВОТПРИМЕРШИФРАВЕРТИКАЛЬНОЙПЕРЕСТАНОВКИ

Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:

Теперь, выбирая столбцы в порядке, заданном ключом и выписывая последовательно буквы каждого из них сверху вниз, получаем такую криптограмму:

ОРЕЬЕРФИЙА-МААЕО-ТШРНСИВЕВЛРВИРКПН-ПИТОТ-

Число ключей ШВП не более m!, где m – число столбцов таблицы. Как правило, m гораздо меньше, чем длина текста n (сообщение укладывается в несколько строк по m букв), а значит, и m! много меньше n!.

В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого либо запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет ПЕРЕСТАНОВКА. Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появление нумеруется последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы Б в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ:

П Е Р Е С Т А Н О В К А

9 4 10 5 11 12 1 7 8 3 6 2