Шифры перестановки. Маршрутные перестановки

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

Транспозиция

Допустим, у нас есть фраза: «МОЖНО, НО НЕЛЬЗЯ» . И мы хотим её зашифровать. Самый простой способ - это записать всю фразу задом наперёд: «ЯЗЬЛЕН ОН, ОНЖОМ» . Можно порядок слов в предложении оставить исходным, но каждое слово записать задом наперёд: «ОНЖОМ, ОН ЯЗЬЛЕН» . А можно менять местами каждые две буквы: «ОМНЖ,ООНЕНЬЛЯЗ» . Это называется «транспозиция» или простая перестановка в чистом виде.

Транспонирование

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

Для шифрования нужно нарисовать подходящего размера таблицу, вписать туда построчно шифруемый текст, а затем выписать его по столбцам в одну строку. Для расшифровки нужно лишь будет сообщить ключ шифра в виде размера таблицы. На рисунке ниже из ABCDEFGHIJKL получается ADGJBEHKCFIL . Согласитесь, понять без картинки, что это был алфавит, уже практически невозможно.

Итак, например, нам нужно зашифровать текст «Я памятник себе воздвиг нерукотворный, к нему не зарастёт народная тропа» . В нём 72 символа. 72 - удобное число, оно делится без остатка на 2,4,6,8,12,18,24,36, поэтому можно использовать таблицы 2х36, 3х24, 4х18, 6х12, 8х9, 9х8, 12х6, 18х4, 24х3, 36х2:). Определяемся с ключом (размером таблицы), вписываем текст по строкам, а затем переписываем его по столбцам.

На рисунке выше показаны варианты с таблицами 9×8, 8×9, 4×18 и 18×4. Для третьего варианта (таблица 4×18) получится вот такой текст:

«Ямиеввнкой у атрар якбоиеор,н зс ояопт езгртн енатнд панс д увыкмерёанта (4:18) »

В данном случае я взял текст «как есть», то есть с пропусками между словами и со знаками препинания. Но если текст осмысленный, то знаки препинания и пропуски между словами можно и не использовать.

Штакетник

Упрощённый вариант транспонирования (с двухстрочной таблицей) - «штакетник». Напоминает «по конструкции» забор-шахматку.

Это очень простой способ шифровки, часто применяемый школьниками. Фраза записывается в две строки: в верхней пишутся нечётные буквы, в нижней - чётные. Затем нужно выписать подряд сначала верхнюю строку, затем нижнюю. Такое шифрование легко проделать и в уме, не выписывая сначала две строки.

«Я памятник себе воздвиг нерукотворный» превращается в «ЯАЯНКЕЕОДИНРКТОНЙ ПМТИСБВЗВГЕУОВРЫ».

Скитала

Известно, что в V веке до нашей эры правители Спарты, наиболее воинственного из греческих государств, имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью «скиталы», первого простейшего криптографического устройства, реализующего метод простой перестановки.

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

По сути скитала - это наша обычная плоская таблица, обёрнутая вокруг цилиндра.

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

Сдвиг

Похожий результат можно получить, если буквы сообщения писать через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Ниже пример готовой головоломки, составленной по таким правилам. «Три дробь четыре» - это подсказка, что зашифровано три слова, читать надо каждую четвёртую букву (4-8-12-16-..), по достижению конца переходить снова к началу со сдвигом на 1 букву влево (3-7-11-15-..) и т.д. На рисунке ниже зашифровано «Идите назначенным маршрутом».

Одиночная перестановка по ключу

Более практический метод шифрования, называемый одиночной перестановкой по ключу, очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы не сдвигаются, а переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Кодируемая фраза записывается в подходящую таблицу построчно. Затем над таблицей вставляется пустая строка и в неё вписывается ключевое слово/фраза/последовательность чисел. Затем это ключевое слово/фраза/последовательность сортируется по алфавиту/значению, вместе с ней сортируются столбцы, тем самым перемешивая всю таблицу. Затем зашифрованная фраза выписывается построчно из этой перемешанной таблицы.

Например, можно сделать головоломку на основе судоку. Разгадывающему даётся текст «-УРОМКУЛО ЬУЁЗЕБЯДЛ НЗЯАТЛЫЙА ЦЬБАДНЕПУ ЕММДНИТОЁ ИЧТЮКЬНОО УНЁЙВЫЧЁС ХИЕПОТОДЦ ПРМГОУИК-» и предлагается решить судоку, в которой одна из строк помечена.

Решать эту головоломку придётся так: сначала нужно записать текст в таблицу 9×9, затем разгадать судоку, нарисовать пустую таблицу 9×9, надписать над ней ключевую строку из помеченной строки, и затем в таблицу под номерами вписать столбцы согласно их порядковым номерам в исходной таблице.

Для детей можно использовать этот же метод, но попроще, даже без цифр, а сразу нарисовав порядок перестановки в виде путей.

Двойная перестановка

Для дополнительной скрытности можно повторно шифровать сообщение, которое уже было зашифровано. Этот способ известен под названием «двойная перестановка». Для этого размер второй таблицы подбирают так, чтобы длины её строк и столбцов были не такие, как в первой таблице. Лучше всего, если они будут взаимно простыми. Кроме того, в первой таблице можно переставлять столбцы, а во второй строки.

Маршрутная перестановка

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

На рисунке сверху последовательность символов «АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.,?» вписана построчно в таблицу 6×6, а затем считана по маршруту, указанному линиями. Получаются следующие шифровки:

АЁЛСЧЭБЖМТШЮВЗНУЩЯГИОФЪ.ДЙПХЫ,ЕКРЦЬ?

АЁЛСЧЭЮЯ.,?ЬЦРКЕДГВБЖМТШЩЪЫХПЙИЗНУФО

АБЁЛЖВГЗМСЧТНИДЕЙОУШЭЮЩФПКРХЪЯ.ЫЦЬ,?

АЁЛСЧЭЮШТМЖБВЗНУЩЯ.ЪФОИГДЙПХЫ,?ЬЦРКЕ

НЗВБАЁЖМЛСТШЧЭЮЯЩУФЪ.,?ЬЫХЦРПЙКЕДГИО

А здесь нужно обходить таблицу «ходом коня», причём маршрут уже нарисован, так что это совсем для маленьких:)

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

Зашифровано «Пушкин. Медный всадник».

Перестановка "Волшебный квадрат"

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

В известном ещё в Древнем Китае квадрате Ло-Шу третьего порядка (3×3) константа квадрата 15 повторяется 8 раз:

по трём горизонталям: 2+9+4 = 7+5+3 = 6+1+8 = 15

по трём вертикалям: 2+7+6 = 9+5+1 = 4+3+8 = 15

по двум диагоналям: 2+5+8 = 4+5+6 = 15

Кстати, константу нечетного квадрата легко посчитать, умножив среднее число ряда, из которого составлен квадрат, на порядок квадрата. Для квадрата 3-го порядка (3×3) константа равна 1234 5 6789 *3=15.

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

На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3х3, если не принимать во внимание его повороты и отражения. Счёт волшебным квадратам 4-го порядка уже идёт на сотни, 5-го - на сотни тысяч. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, так как ручной перебор всех вариантов ключа для этого шифра был немыслим.

Есть очень простой метод составления нечётных волшебных квадратов, т.е. размером 3×3, 5×5, 7×7 и т.д. Это метод «террас» или «пирамидок».

Рисуется квадрат нужного размера и к нему пририсовываются ступенчатые «террасы» (обозначены пунктиром). Далее по диагоналям сверху вниз направо квадрат заполняется последовательными числами. После этого «террасы» переносятся внутрь квадрата: правые - налево, левые - направо, верхние - вниз, а нижние - наверх. Получается волшебный квадрат!

На базе этого метода можно составлять разные головоломки. Если использовать метод напрямую, то получится вот такая головоломка:

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

А если использовать метод наоборот, то получится головоломка типа такой.

Чтобы её решить, надо вытащить соответствующие буквы из квадрата в «террасы».

Для квадратов 4×4, 6×6 и т.д. таких простых способов их составления не существует, поэтому проще использовать готовые. Например, квадрат Дюрера.

Блочные шифры

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

Одноключевые блочные шифры подразделяются на 3 группы:

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

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

Составные шифры.

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

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

Пример простейшего шифра перестановки представлен на рис. 5.5.

Рис. 5.5. Простейший шифр перестановки.

Как видно из рис. 5.5, для того чтобы зашифровать сообщение «ЮСТАС АЛЕКСУ ВСТРЕЧАЙТЕ СВЯЗНОГО», последнее необходимо записать в виде таблицы, состоящей, например, их 5 строк и 6 столбцов. Текст сообщения записы­вается по столбцам, исключая пробелы. Если последний стол­бец оказывается неполным, он заполняется произвольно лю­быми буквами. Для получения зашифрованного сообщения ис­ходный текст считывается по­строчно (слева направо) и за­писывается группами, напри­мер, по 5 цифр. Последняя

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

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

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

«ЗАСЕДАНИЕ СОСТОИТСЯ ЗАВТРА ЮСТАС».

Для шифрования этого открытого текста запишем его без пробелов (уча­стие последних в процедуре шифрования, из-за их высокой частоты повто­рения, значительно ослабляет криптостойкость шифра) и выберем ключ шифрования, например, 245 136. Согласно этому ключу, состоящему из 6 цифр, поделим все информационное сообщение на блоки, каждый из кото­рых будет содержать по 6 букв текста. После деления на блоки у нас полу­чилось 4 блока, содержащих по 6 букв в каждом, и 1 блок - по 5 букв. В таких случаях последняя группа букв исходного сообщения произвольно дополняется различными символами до получения полного блока. В на­шем случае не достает только одной буквы, поэтому выбираем любую букву, например Ъ, и добавляем ее в конце пятого блока.

Рис. 5.6. Шифр простой перестановки

Далее, используя ключ 245 136, производится перестановка букв исходно­го открытого текста. Например, первая цифра ключа - 2, указывает на то, что в новом блоке первой буквой зашифрованного текста будет вторая буква бло­ка открытого текста, вторая цифра ключа - 4, показывает, что вторая буква шифротекста - это четвертая буква в блоке открытого текста и т. д.

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

Для упрощения запоминания ключа обычно используется ключевое слово. В данном случае - это слово «КОРЕНЬ». В нем цифре 1 ключа соответ­ствует буква Е, так как она первой из всех букв этого слова встречается в нашем алфавите, цифре 2 - буква К (по той же причине) и т. д.

То же сообщение можно зашифровать с использованием таблицы, состоя­щей, например, из 5 строк и 6 столбцов (по длине ключевого слова). Исход­ный текст записывается по столбцам и образует таблицу (рис. 5.7). Ключевое слово задает правило перестановки столбцов. Если в ключевом слове встре­чаются одинаковые буквы, то они нумеруются по порядку слева направо. По­лученный второй шифротекст, как это видно из рис. 5.7, совершенно не похож на первый.

Рис. 5.7. Шифрование с помощью таблицы

Основным недостатком данного шифра является его невысокая криптостойкость. Разложив зашифрованный текст на множители (не так уж мно­го получается вариантов), можно легко определить вероятную длину кодо­вого слова, которое использовалось при шифровании.

Для повышения криптостойкости полученного выше шифрованного тек­ста можно попробовать зашифровать его еще раз. Этот способ шифрования известен под названием двойная перестановка. Суть этого способа заключа­ется в следующем. Полученный после первого шифрования текст шифрует­ся вторично с использованием таблицы с другой размерностью (длины строк и столбцов подбираются другими). Кроме того, в одной таблице можно пе­реставлять строки, а в другой столбцы. Заполнять таблицу исходным тек­стом можно разными способами: зигзагом, змейкой, по спирали и т. п.

Шифр простой перестановки с использованием свойств таблиц, назы­ваемых магическими квадратами (рис. 5.8), использовался еще в средние века. Магическими квадратами называются равносторонние таблицы, все клетки которых заполнены натуральными числами, начиная от 1. При­чем эти числа в сумме дают по каждому столбцу, по каждой строке и по диагоналям магического квадрата одно и тоже число (в нашем случае - это число 34). Исходный текст - ЖДУ ВСТРЕЧИ ЮСТАС, при заполне­нии магического квадрата, вписывается по порядку следования натураль­ных чисел, например, число 1 заменялось 1 буквой исходного текста (Ж), число 12 - 12 буквой сообщения (С) и т.п. После записи открытого тек­ста содержимое таблицы считывается по строкам в результате чего и получался шифротскст с перестановкой букв.

Рис. 5.8. Магический квадрат

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

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

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

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

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

Шифр перестановки "скитала". Известно, что в Vвеке до нашей эры правители Спарты, наиболее воинственного из греческих государств, имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью скитала, первого простейшего криптографического устройства, реализующего метод простой перестановки.

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

Рис. 1.2. Шифр "Скитала"

Такой же результат можно получить, если буквы сообщения писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Сообщение "НАСТУПАЙТЕ " при размещении его по окружности стержня по три буквы дает шифртекст: "НУТАПЕСА_ТЙ ".

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

Шифрующие таблицы. С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые, в сущности, задают правила перестановки букв в сообщении.

В качестве ключа в шифрующих таблицах используются:

размер таблицы;

слово или фраза, задающие перестановку;

особенности структуры таблицы.

Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение "ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ "записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 1.3.

После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение: "ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ ".

Рис. 1.3. Заполнение шифрующей таблицы из 5 строк и 7 столбцов

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

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

Применим в качестве ключа, например, слово "ПЕЛИКАН ", а текст сообщения возьмем из предыдущего примера. На рис. 1.4 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица – заполнению после перестановки.

Рис. 1.4. Шифрующие таблицы, заполненные ключевым словом и текстом сообщения

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

При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение: "ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ ".

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

Пример выполнения шифрования методом двойной перестановки показан на рис. 1.5. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее: "ТЮАЕ ООГМ РЛИП ОЬСВ ".

Рис. 1.5. Пример выполнения шифрования методом двойной перестановки

Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

для таблицы 3x3 36 вариантов;

для таблицы 4x4 576 вариантов;

для таблицы 5x5 14400 вариантов.

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

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

Пример магического квадрата и его заполнения сообщением "ПРИЛЕТАЮ ВОСЬМОГО " показан на рис. 1.6.

Рис. 1.6. Пример магического квадрата 4х4 и его заполнение сообщением

Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид: "ОИРМ ЕОСЮ ВТАЪ ЛГОП ".

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3x3 (если не учитывать его повороты). Количество магических квадратов 4x4 составляет уже 880, а количество магических квадратов 5x5 – около 250000.

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

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

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

Шифрование простой перестановкой (вертикальной перестановкой) осуществляется следующим образом:

1) выбирается ключевое слово с неповторяющимися символами;

2) шифруемый текст записывается последовательными строками под символами ключевого слова;

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

В качестве иллюстрации приведем пример шифрования способом простой перестановки сообщения: «БУДЬТЕ ОСТОРОЖНЫ С ПРЕДСТАВИТЕЛЕМ ФИРМЫ "ФЕНИКС". При этом применим цифровой ключ 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. В исходном тексте вместо пробелов используется буква а.

Б	У	Д	Ь	Т	Е	а	О
С	Т	О	Р	О	Ж	Н	Ы
А	С	а	П	Р	Е	Д	С
Т	А	В	И	Т	Е	Л	Е
М	а	Ф	И	Р	М	Ы	а
Ф	Е	Н	И	К	С	а	а

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

ДО ВФ НОЫСЕ ЬРП ИИИЕЖ ЕЕМСБ С ТМФ НДЛЫ TOPT РКУТС A E .

Расшифрование выполняется в следующем порядке:

1) подсчитываем число знаков в зашифрованном тексте и делим на число знаков ключа;

2) выписываем ключевое слово и под его знаками в соответствующей последовательности выписываем символы зашифрованного текста в определенном выше количестве;

3) по строкам таблицы читаем исходный текст.

Число ключей не более m!, где m - число столбцов таблицы.

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

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

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

Усложнение перестановки по таблице заключается в том, что для записи символов шифруемого текста используется специальная таблица, в которую введены некоторые усложняющие элементы. Усложнение состоит в том, что определенное число клеток таблицы не используется (на рисунке они пусты). Количество и расположение неиспользуемых элементов является дополнительным ключом шифрования. Шифруемый текст блоками по m х n – s элементов (m х n – размеры таблицы,s – число неиспользуемых элементов) записывается в таблицу. Далее шифрование аналогична простой перестановке.

Б	У	Д		Ь	Т	Е	а	О	С
	Т	О	Р	О	Ж	Н		Ы	а
С	а	О	Р	Е	Д	С	Т		А
В	И		Т	Е	Л	Е	М	а	Ф
И		Р	М	Ы	а	Ф	Е	Н	И
К	С	а	а	а		а	А	а	а

Зашифрованный текст будет выглядеть так: ДОПР БСВИК РРТМ ОЫ Н ЕНСЕФ УТ И СС АФ И ЬОЕ ЕЫ Т МЕ ТЖ ДЛ .

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

Еще один вариант - шифр "Поворотная решетка" . предназначен для сообщений длины 4mk. Берется трафарет размером 2m*2k клеток, вырезается m*k клеток так, что при наложении его на лист бумаги того же размера 4 различными способами (поворачивая на 90°) его вырезы полностью покрывают всю площадь листа. Буквы сообщения последовательно вписываются в вырезы трафарета по строкам, в каждой строке слева направо, при каждом из 4-х его возможных положений в заранее установленном порядке. Число возможных трафаретов, т.е. количество ключей этого шифра составляет 4 mk (при размере трафарета 8*8 число вариантов превосходит 4 миллиарда).

Весьма высокую стойкость шифрования можно обеспечить усложнением перестановок по маршрутам типа гамильтоновских. При этом для записи символов шифруемого текста используются вершины некоторого гиперкуба, а знаки зашифрованного текста считываются по маршрутам Гамильтона, причем используется несколько различных маршрутов. Для примера рассмотрим шифрование по маршругам Гамильтона при n =3. Структура и три маршрута показаны на Рис. 7, а пример шифрования – на Рис. 8.