Шифры перестановки
Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется .
Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью таблицы
|
(6) |
где - номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, - номер места для второй буквы и т.д. В верхней строке таблицы выписаны по порядку числа от 1 до , а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени .
Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка
и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА. Попробуйте расшифровать сообщение НЧЕИУК, полученное в результате преобразования с помощью указанной выше подстановки.
В качестве упражнения читателю предлагается самостоятельно выписать подстановки, задающие преобразования в описанных ниже трех примерах шифров перестановки. помещены в конце раздела.
Читатель, знакомый с методом математической индукции, может легко убедиться в том, что существует
(обозначается , читается `` факториал'') вариантов заполнения нижней строки таблицы (). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины , меньше либо равно (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!).
С увеличением числа значение растет очень быстро. Приведем таблицу значений для первых 10 натуральных чисел:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
| 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40320 | 362880 | 3628800 |
При больших для приближенного вычисления можно пользоваться известной формулой Стирлинга
где .
Примером ШП, предназначенного для зашифрования сообщений длины , является шифр, в котором в качестве множества ключей взято множество всех подстановок степени , а соответствующие им преобразования шифра задаются, как было описано выше. Число ключей такого шифра равно .
Для использования на практике такой шифр не удобен, так как при больших значениях приходится работать с длинными таблицами.
Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного ``маршрута'', а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.
Зашифруем, например, указанным способом фразу:
используя прямоугольник размера :
| П | Р | И | М | Е | Р | М |
| Н | Т | У | Р | Ш | Р | А |
| О | Й | П | Е | Р | Е | С |
| И | К | В | О | Н | А | Т |
Теоретически маршруты могут быть значительно более изощренными, однако запутанность маршрутов усложняет использование таких шифров.
Ниже приводятся описания трех разновидностей шифров перестановки, встречавшихся в задачах олимпиад.
. Одним из самых первых шифровальных приспособлений был жезл (``Сцитала''), применявшийся еще во времена войны Спарты против Афин в V веке до н. э. Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения.
Шифр ``Сцитала'', как видно из решения задачи , реализует не более перестановок (, по прежнему, - длина сообщения). Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения.
Имеются еще и чисто физические ограничения, накладываемые реализацией шифра ``Сцитала''. Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв (
Шифр ``Поворотная решетка''. Для использования шифра, называемого поворотной решеткой, изготавливается трафарет из прямоугольного листа клетчатой бумаги размера клеток. В трафарете вырезано клеток так, что при наложении его на чистый лист бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.
Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке.
Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка , приведенная на рис. .
ШИФРРЕШЕТКАЯВЛЯЕТСЯЧАСТНЫМСЛУЧАЕМШИФРАМАРШРУТНОЙПЕРЕСТАНОВКИ
Наложив решетку на лист бумаги, вписываем первые 15 (по числу вырезов) букв сообщения: ШИФРРЕШЕТКАЯВЛЯ.... Сняв решетку, мы увидим текст, представленный на рис. . Поворачиваем решетку на . В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. . Затем переворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. , ).
Можно доказать, что число возможных трафаретов, то есть количество ключей шифра ``решетка'', составляет (см. задачу ). Этот шифр предназначен для сообщений длины . Число всех перестановок в тексте такой длины составит , что во много раз больше числа . Однако, уже при размере трафарета число возможных решеток превосходит 4 миллиарда.
Широко распространена разновидность шифра маршрутной перестановки, называемая ``шифром вертикальной перестановки'' (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,4,1,7,2,6,3), и с его помощью надо зашифровать сообщение:
Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:
| 5 | 1 | 4 | 7 | 2 | 6 | 3 |
| В | О | Т | П | Р | И | М |
| Е | Р | Ш | И | Ф | Р | А |
| В | Е | Р | Т | И | К | А |
| Л | Ь | Н | О | Й | П | Е |
| Р | Е | С | Т | А | Н | О |
| В | К | И | - | - | - | - |
| ОРЕЬЕКРФИЙА-МААЕО-ТШРНСИВЕВЛРВИРКПН-ПИТОТ- |
Пользуясь приведенной выше
при больших и , попытайтесь оценить, во сколько раз число возможных перестановок ШВП с столбцами меньше числа всех перестановок на тексте длины , кратном .
В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет ПЕРЕСТАНОВКА. Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы Б в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ:
| П | Е | Р | Е | С | Т | А | Н | О | В | К | А |
| 9 | 4 | 10 | 5 | 11 | 12 | 1 | 7 | 8 | 3 | 6 | 2 |
полученной шифром перестановки. Возможны, как минимум, два варианта исходного сообщения:
|
КАЗНИТЬ,-НЕЛЬЗЯ-ПОМИЛОВАТЬ. и КАЗНИТЬ-НЕЛЬЗЯ,-ПОМИЛОВАТЬ. |
Иногда, за счет особенностей реализации шифра, удается получить информацию об использованном преобразовании (перестановке). Рассмотрим шифр ``Сцитала'' из задачи . Выше уже рассматривался вопрос о количестве перестановок, реализуемых ``Сциталой''. Их оказалось не более 32. Это число невелико, поэтому можно осуществить перебор всех вариантов. При достаточной длине сообщения, мы, скорее всего, получим единственный читаемый вариант текста. Однако, используя информацию о расположении линий, оставленных шифровальщиком, удается определить диаметр стержня, а значит, и возникающую перестановку букв (см. задачу ).
В рассмотренном примере шифровальщик по неосторожности оставил на папирусе следы, позволяющие нам легко прочитать сообщение. Возможны и другие ситуации, когда не очень ``грамотное'' использование шифра облегчает вскрытие переписки.
В задаче содержится пример текста, зашифрованного ШВП. По условию пробелы между словами при записи текста в таблицу опускались. Поэтому заключаем, что все столбцы, содержащие пробел в последней строке, должны стоять в конце текста. Таким образом, возникает разбиение столбцов на две группы (содержащие 6 букв, и содержащие 5 букв). Для завершения восстановления исходного текста достаточно найти порядок следования столбцов в каждой из групп в отдельности, что гораздо проще.
Аналогичная ситуация возникает и при ``неполном'' использовании шифра ``решетка'' (см. задачу ). Пусть имеется решетка размера , и зашифрованное с ее помощью сообщение длины , не содержащее пробелов. Незаполненные мест в решетке при условии, что , соответствуют вырезам в четвертом положении решетки. На основе такой информации, происходит резкое уменьшение числа допустимых решеток (их будет ). Читателю предлагается самостоятельно подсчитать число допустимых решеток при mr/4$" width="72" height="31" >.
На примере решения задачи продемонстрируем еще один подход к вскрытию шифров вертикальной перестановки - лингвистический. Он основан на том, что в естественных языках некоторые комбинации букв встречаются очень часто, другие - гораздо реже, а многие вообще не встречаются (например - ``ыьъ'').
Будем подбирать порядок следования столбцов друг за другом так, чтобы во всех строках этих столбцов получались ``читаемые'' отрезки текста. В приведенном решении задачи восстановление текста начинается с подбора цепочки из трех столбцов первой группы, содержащей в последней строке сочетание ТЧК, так как естественно предположить, что сообщение заканчивается точкой. Далее подбираются столбцы, продолжающие участки текста в других строках, и т.д.
Сочетание лингвистического метода с учетом дополнительной информации довольно быстро может привести к вскрытию сообщения.
В заключение рассказа о шифрах перестановки приведем историю с зашифрованным автографом А. С. Пушкина, описанную в романе В. Каверина ``Исполнение желаний''.
Главный герой романа - студент-историк Н. Трубачевский, - занимавшийся работой в архиве своего учителя - академика Бауэра С. И., - нашел в одном из секретных ящиков пушкинского бюро фрагмент недописанной Х главы ``Евгения Онегина''. Это был перегнутый вдвое полулист плотной голубоватой бумаги с водяным знаком 1829 года. На листе было написано следующее.
| 1. Властитель слабый и лукавый | 1. Нечаянно пригретый славой |
| 2. Его мы очень смирным знали | 2. Орла двуглавого щипали |
| 3. Гроза двенадцатого года | 3. Остервенение народа |
| 4. Но Бог помог - стал ропот ниже | 4. Мы очутилися в Париже |
| 5. И чем жирнее, тем тяжеле | 5. Скажи, зачем ты в самом деле |
| 6. Авось, о Шиболет народный | 6. Но стихоплет великородный |
| 7. Авось, аренды забывая | 7. Авось по манью Николая |
| 8. Сей муж судьбы, сей странник бранный | 8. Сей всадник, папою венчанный |
| 9. Тряслися грозно Пиринеи | 9. Безрукий князь друзьям Мореи |
| 10. Я всех уйму с моим народом | 10. А про себя и в ус не дует |
| 11. Потешный полк Петра Титана | 11. Предавших некогда тирана |
| 12. Россия присмирела снова | 12. Но искра пламени иного |
| 13. У них свои бывали сходки | 13. Они за рюмкой русской водки |
| 14. Витийством резким знамениты | 14. У беспокойного Никиты |
| 15. Друг Марса, Вакха и Венеры | 15. Свои решительные меры |
| 16. Так было над Невою льдистой | 16. Блестит над каменкой тенистой |
| 17. Плешивый щеголь, враг труда | 17. Над нами царствовал тогда |
| 18. Когда не наши повара | 18. У Бонапартова шатра |
| 19. Настала - кто тут нам помог? | 19. Барклай, зима иль русский бог? |
| 20. И скоро силою вещей | 20. А русский царь главой царей |
| 21. О русский глупый наш народ | 21. ... |
| 22. Тебе б я оду посвятил | 22. Меня уже предупредил |
| 23. Ханжа запрется в монастырь | 23. Семействам возвратит Сибирь |
| 24. Пред кем унизились цари | 24. Исчезнувший как тень зари |
| 25. Волкан Неаполя пылал | 25. Из Кишинева уж мигал |
| 26. Наш царь в конгрессе говорил | 26. Ты александровский холоп (?) |
| 27. Дружина старых усачей | 27. Свирепой шайке палачей |
| 28. И пуще царь пошел кутить | 28. Уже издавна, может быть |
| 29. Они за чашею вина | 29. ... |
| 30. Сбирались члены сей семьи | 30. У осторожного Ильи |
| 31. Тут Лунин дерзко предлагал | 31. И вдохновенно бормотал |
| 32. Но там, где ранее весна | 32. И над холмами Тульчина |
Трубачевский с азартом взялся за рукопись, пытался читать ее, пропуская по одной строке, потом по две, по три, надеясь случайно угадать тайную последовательность, в которой были записаны строки. У него ничего не получалось. Тогда он стал читать третью строку вслед за первой, пятую за третьей, восьмую за пятой, предположив, что пропуски должны увеличиваться в арифметической прогрессии. Все то же! Отчаявшись, он бросил эту затею. Однако, она не давала ему покоя ни на лекции, ни в трамвае... Как шахматист, играющий в уме, он не только знал наизусть каждую строчку, он видел ее в десяти комбинациях сразу.
Прошло время. Однажды, когда он смотрел на светлые пятна окон подходящего к перрону поезда, каким-то внутренним зрением он увидел перед собой всю рукопись - и с такой необыкновенной отчетливостью, как это бывает только во сне.
Сможете ли вы прочитать эти стихи? Ответ вы найдете в романе В. Каверина.
Next: Ответы к упражнению.
Up: 7. Олимпиады по криптографии
Previous: Ж. Верн, ``Путешествие к центру
Contents:
