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

Шифры перестановки изменяют только порядок следования символов текста, но не изменяют их самих. Поэтому для расшифровывания нужно знать подстановку – биекцию множества символов сообщения, задающую преобразование. Всего существует n! подстановок на n-элементном множестве. С увеличением числа n значение n! растет очень быстро. При больших n для приближенного вычисления n! можно пользоваться следующей известной формулой, названной в честь шотландского математика Джеймса Стирлинга (1692–1770):

, где е = 2,718281828…

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

1. Одним из самых первых шифровальных приспособлений был жезл («Сцитала»), применявшийся еще во времена войны Спарты против Афин в V веке до н.э. и связанный с именем спартанского полководца Лисандра. Жезл имел форму цилиндра, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента разматывалась, и получалось (для непосвященных), что поперек нее в беспорядке написаны какие-то буквы. Затем лента отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение вдоль оси. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения.

Шифр «Сцитала» реализует не более n перестановок, где n – длина сообщения. Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из m столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения. Имеются еще и чисто физические ограничения, накладываемые реализацией шифра «Сцитала». Естественно предположить, что диаметр жезла не должен превосходить 10 см. Тогда при высоте строки в 1 см на одном витке такого жезла уместится не более 32 букв (10p < 32). Таким образом, число перестановок, реализуемых «Сциталой», вряд ли превосходит 32.

2. Шифр «Поворотная решетка». Идея использования «Поворотной решетки» как средства шифрования принадлежит итальянскому математику и философу Джероламо Кардано (1501 или 1506 – 1576). В его честь данный способ шифрования также носит название «Сетки (решетки) Кардано». Для использования шифра, называемого «Поворотной решеткой», изготавливается трафарет из прямоугольного листа клетчатой бумаги размером 2m ´ 2k клеток. В трафарете вырезано mk клеток так, что при наложении его на чистый лист бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа. Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке. Получатель сообщения, имеющий точно такую же решетку, без труда прочтет исходный текст, наложив решетку на шифртекст по порядку четырьмя способами.

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

3. Широко распространена разновидность шифра маршрутной перестановки, называемая «Вертикальной перестановкой». Здесь снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Для получения криптограммы выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом.

Число ключей шифра «Вертикальная перестановка» не более m!, где m – число столбцов таблицы. Как правило, m гораздо меньше, чем длина текста n (сообщение укладывается в несколько строк по m букв), а, значит, и m! много меньше n!. В случае, когда ключ «Вертикальной перестановки» не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения. Наиболее распространенный способ состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет «перестановка». Присутствующая в нем буква «А» получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы «А» получает номер 2. Поскольку буквы «Б» в этом слове нет, то буква «В» получает номер 3 и т.д. Процесс продолжается до тех пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ: