Криптография

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

 

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

 

 

 

 

 

 

 

 

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

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

 

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

 

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

 

 

 

 

 

 

 

 

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

 

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

 

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

 

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

 

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

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

 

Перейдем к вопросу о методах вскрытия шифров перестановки. Проблема, возникающая при восстановлении сообщения, зашифрованного ШП, состоит не только в том, что число возможных ключей велико даже при небольших длинах текста. Если и удастся перебрать все допустимые варианты перестановок, не всегда ясно, какой из этих вариантов истинный. Например, пусть требуется восстановить исходный текст по криптограмме АОГР, и нам ничего не известно, кроме того, что применялся шифр перестановки. Какой вариант “осмысленного” исходного текста признать истинным: ГОРА или РОГА? А может быть АРГО? Приведем пример еще более запутанной ситуации. Пусть требуется восстановить сообщение по криптограмме

 

ААНИНК-ТЕОМЛ,З.ЬЬЗИВТЛП-ЬЯО,

 

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

 

КАЗНИТЬ,-НЕЛЬЗЯ-ПОМИЛОВАТЬ.

и

КАЗНИТЬ-НЕЛЬЗЯ,-ПОМИЛОВАТЬ.

 

У этих вариантов прямо противоположный смысл, и в имеющихся условиях у нас нет возможности определить, какой из вариантов истинный.