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

При шифровании перестановкой символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока этого текста.

Простая перестановка

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

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

Шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m.

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

Заполняется новый блок и т.д.

Например, зашифруем текст

ГРУЗИТЕ_АПЕЛЬСИНЫ_БОЧКАХ

блоком размером 8*3 и ключом 5-8-1-3-7-4-6-2.

Таблица простой перестановки будет иметь вид:

Зашифрованное сообщение:

УЕБ_НХЗЛОЕСЛГАЫЕИАИЬЧРП_

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

Из зашифрованного текста выделяется блок символов размером n*m.

Этот блок разбивается на n групп по m символов.

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

Выделяется новый блок символов и т.д.

Перестановка, усложненная по таблице

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

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

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

Перестановка, усложненная по маршрутам

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

Струкрура трехмерного гиперкуба представлена на рисунке 6.

Рисунок 6. Трехмерный гиперкуб

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

Рисунок 7. Маршруты Гамильтона

Последовательность перестановок символов в шифруемом блоке для первой схемы 5-6-2-1-3-4-8-7, а для второй 5-1-3-4-2-6-8-7. Аналогично можно получить последовательность перестановок для других маршрутов: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2-4-3-7-8-6 и т.д.

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

Стойкость простой перестановки однозначно определяется размерами используемой матрицы перестановки. Например, при использовании матрицы 16*16 число возможных перестановок достигает 1.4E26. Такое число вариантов невозможно перебрать даже с использованием ЭВМ. Стойкость усложненных перестановок еще выше. Однако следует иметь в виду, что при шифровании перестановкой полностью сохраняются вероятностные характеристики исходного текста, что облегчает криптоанализ.

Шифрование по методу магических квадратов.

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

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

Зашифруем фразу «МАГИЧЕСКАЯ СИЛА» с помощью магического квадрата размером 4х4. Для этого выберем один из 880 вариантов магических квадратов заданного размера (рисунок 8а). Затем вписываем каждую букву сообщения в отдельную ячейку таблицы с номером, соответствующим порядковому номеру буквы в исходной фразе (рисунок 8б). При считывании заполненной таблицы по строкам получаем шифротекст: «_ГАИАЕССЧЯ_КИАЛМ».

Рисунок 8. Пример шифрования с помощью магических квадратов

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

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

Одноключевые блочные шифры подразделяются на 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. Магический квадрат

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

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки

КЛЮЧ: (3, 1, 4, 2, 5)

КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео

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

Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:

Количество столбцов в таблице фиксируется и определяется длиной ключа;

Маршрут вписывания - строго слева-направо сверху-вниз;

Шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).

Рис.5.5. Пример использования шифра вертикальной перестановки

В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3.

При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ».

Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного ``маршрута"", а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой .

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

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

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

Шифр ``Сцитала"" .

Одним из самых первых шифровальных приспособлений был жезл (``Сцитала""), применявшийся еще во времена войны Спарты против Афин в V веке до н. э.

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

Шифр ``Сцитала"‘ реализует не более n перестановок (n - длина сообщения).

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

Имеются еще и чисто физические ограничения, накладываемые реализацией шифра ``Сцитала"". Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв (10p < 32). Таким образом, число перестановок, реализуемых ``Сциталой"", вряд ли превосходит 32.

Шифр ``Поворотная решетка"".

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

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

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

1. Шифры замены. Математическая модель. Примеры.

Поточные шифры (Цезаря)

Блочные шифры (Порта и Пфейфера)

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

Правило зашифрования:

Буквы биграммы (i ,j ), i ¹ j , находятся в данной таблицк. При зашифровании биграмма (i ,j ) заменяется биграммой (k ,l ), где определяются с правилами:

1. Если i и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда k и l – другая пара вершин, причем k –вершина, лежащая в той же строке, что и i .
2. Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее «правым соседом» является первая буква той же строки.
3. Аналогично если i и j лежат в одном столбце, то они заменяются «соседями снизу.»

Пример шифра Плейфера.

Пусть шифр использует прямоугольник 5х6, в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова «командир».

В качестве «пустышки» будем использовать редкую букву ф .

Представим фразу в виде последовательности биграмм:

АВ ТО РО МФ МЕ ТО ДА ЯВ ЛЯ ЕТ СЯ УИ ТС ТО НФ

Шифртекст:

ВП ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД ОЧ

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

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

1. Шифры перестановки. Математическая модель. Примеры.

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

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

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

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

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

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

то получится КОСВМА.

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

Гамми́рование - симметричный метод шифрования, основанный на «наложении» гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле

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

Сеть Фейстеля:

Сеть Фейстеля - это общий метод преобразования произвольной функции F в перестановку на множестве блоков. Она состоит из циклически повторяющихся ячеек - раундов. Внутри каждого раунда блок открытого текста разделяется на две равные части. Раундовая функция

берет одну половину (на рис. правую), преобразует её с использованием ключа K i и объединяет результат с второй половиной посредством операции исключающее ИЛИ (XOR). Этот ключ задаётся первоначальным ключом K и различен для каждого раунда. Далее половинки меняются местами (иначе будет преобразовываться только одна половина блока) и подаются на следующий раунд. Преобразование сети Фейстеля является обратимой операцией.

Для функции F существуют определенные требования:

· её работа должна приводить к лавинному эффекту

· должна быть нелинейна по отношению к операции XOR

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

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

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

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

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

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

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

Для шифрования нужно нарисовать подходящего размера таблицу, вписать туда построчно шифруемый текст, а затем выписать его по столбцам в одну строку. Для расшифровки нужно лишь будет сообщить ключ шифра в виде размера таблицы. На рисунке ниже из 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 и т.д. таких простых способов их составления не существует, поэтому проще использовать готовые. Например, квадрат Дюрера.