Зашифровать сообщение используя шифр перестановки по маршрутам
Обновлено: 30.06.2024
Наибольшее распространение получили шифры маршрутной перестановки, основанные на таблицах.
Шифр вертикальной перестановки.Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:
- количество столбцов в таблице фиксируется и определяется длиной ключа;
- маршрут вписывания строго соответствует маршруту, показанному на рис.12;
- шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).
Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо.
В примере первая буква Д получает номер 2, вторая Д – 3.
Задание из области информационно-криптографических технологий. Нужно зашифровать текст, используя метод усложненной перестановки по маршрутам Гамильтона, а потом полученную криптограмму расшифровать.
Гиперкуб Гамильтона представлен на рисунке
Ключ нужно сформировать самостоятельно.
Исходный текст ВЕРХОВНЫЙ СУД РФ.
Допустим, началом маршрута будет 5.
В исходном тексте 16 символов. Они составят один блок.
На блок формируем свой ключ. Ключом является набор вершин графа, которые соединены своим маршрутом Гамильтона (движения из начальной вершины ключа в конечную). При построении маршрута Гамильтона никакую вершину нельзя пройти более одного раза и никакую нельзя пропустить.
Сформируем ключ (маршрут) для этого блока:
К=5,13,14,6,2,1,9,10,12,4,3,11,15,16,8,7
Результаты действий по алгоритму зашифрования блока исходного текста шифром усложненной перестановки сведем в таблицу.
Структура этой таблицы такова.В первой строке таблицы записаны номера вершин гиперкуба в естественном порядке их следования.
На блок отводится по три строки, которые заполняются так. В первой строке записывают символы блока исходного текста в естественном порядке их следования. Во вторую строку записывают номера вершин гиперкуба в том порядке, который определен маршрутом Гамильтона (ключом) для этого блока. Содержимое третьей строки формируется из символов первой строки так: число в данной ячейке второй строки определяет номер того символа из первой строки, который будет записан в ячейку третьей строки под этим же номером. Так в третьей строке формируется блок зашифрованного текста.
Полученные три блока зашифрованного текста объединяем в одну криптограмму: ОДЭВЕВЙЭУХРСРФЫН.
Расшифруем полученную криптограмму.
Создаем таблицу и заполняем ее так:
В третью строку записываем символы блока зашифрованного текста в том порядке, как они следуют в криптограмме. Во вторую строку заносим номера вершин гиперкуба, заданные ключом для данного блока.
Первую строку заполняем так. В третьей строке отыскиваем символ, у которого номер 1 во второй строке, и записываем его в ячейку номер 1 первой строки (у нас это символ Э). Аналогично заполняем ячейку номер 2 первой строки (символ К) и все остальные ее ячейки. В результате в первой строке получаем текущий блок расшифрованного текста.
Полученные блоки расшифрованного текста объединяем в один исходный текст: ВЕРХОВНЫЙ СУД РФ.
Это описание перестановочных шифров для начинающих составителей головоломок.
Простая перестановка
Простая перестановка без ключа — один из самых простых методов шифрования. Буквы перемешиваются по каким-либо правилам, но эти правила могут быть разными — и простыми и сложными.
Транспозиция
Транспонирование
Для шифрования нужно нарисовать подходящего размера таблицу, вписать туда построчно шифруемый текст, а затем выписать его по столбцам в одну строку. Для расшифровки нужно лишь будет сообщить ключ шифра в виде размера таблицы. На рисунке ниже из ABCDEFGHIJKL получается ADGJBEHKCFIL. Согласитесь, понять без картинки, что это был алфавит, уже практически невозможно.
На рисунке выше показаны варианты с таблицами 9×8, 8×9, 4×18 и 18×4. Для третьего варианта (таблица 4×18) получится вот такой текст:
Штакетник
Это очень простой способ шифровки, часто применяемый школьниками. Фраза записывается в две строки: в верхней пишутся нечётные буквы, в нижней - чётные. Затем нужно выписать подряд сначала верхнюю строку, затем нижнюю. Такое шифрование легко проделать и в уме, не выписывая сначала две строки.
Скитала
По сути скитала - это наша обычная плоская таблица, обёрнутая вокруг цилиндра.
Считается, что автором способа взлома шифра скиталы является Аристотель, который наматывал ленту на конусообразную палку до тех пор, пока не появлялись читаемые куски текста. Изначально древний аппарат использовался в качестве сохранения секретных рецептов. Сейчас вместо узкой полоски пергамента можно использовать серпантин, а роль скиталы выполнит карандаш.
Сдвиг
Одиночная перестановка по ключу
Более практический метод шифрования, называемый одиночной перестановкой по ключу, очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы не сдвигаются, а переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Кодируемая фраза записывается в подходящую таблицу построчно. Затем над таблицей вставляется пустая строка и в неё вписывается ключевое слово/фраза/последовательность чисел. Затем это ключевое слово/фраза/последовательность сортируется по алфавиту/значению, вместе с ней сортируются столбцы, тем самым перемешивая всю таблицу. Затем зашифрованная фраза выписывается построчно из этой перемешанной таблицы.
Решать эту головоломку придётся так: сначала нужно записать текст в таблицу 9×9, затем разгадать судоку, нарисовать пустую таблицу 9×9, надписать над ней ключевую строку из помеченной строки, и затем в таблицу под номерами вписать столбцы согласно их порядковым номерам в исходной таблице.
Для детей можно использовать этот же метод, но попроще, даже без цифр, а сразу нарисовав порядок перестановки в виде путей.
Двойная перестановка
Маршрутная перестановка
Обычное транспонирование таблицы (заполняем по строкам, читаем по столбцам) можно усложнить и считывать не по столбцам, а змейкой, зигзагом, по спирали или каким-то другим способом, т.е. задавать маршрут обхода таблицы. Такие способы заполнения таблицы если и не усиливают стойкость шифра, то делают процесс шифрования гораздо более занимательным. Правда, процесс расшифровки при этом усложняется, особенно, если маршрут неизвестен, и его ещё надо узнать.
А вот загадать этот маршрут можно, например, вот таким стихотворением:
Перестановка "Волшебный квадрат"
Волшебными (или магическими) квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1 до n 2 (где n - размерность квадрата), которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.
В известном ещё в Древнем Китае квадрате Ло-Шу третьего порядка (3×3) константа квадрата 15 повторяется 8 раз:
Кстати, константу нечетного квадрата легко посчитать, умножив среднее число ряда, из которого составлен квадрат, на порядок квадрата. Для квадрата 3-го порядка (3×3) константа равна 123456789*3=15.
Чтобы зашифровать какое-то послание, нужно сначала подобрать или составить подходящий по размеру волшебный квадрат, затем нарисовать пустую таблицу такого же размера, и вписать буквы текста по очереди в таблицу в соответствии с номерами в волшебном квадрате. Затем выписывают построчно буквы из таблицы в одну длинную строку. Порядок квадрата должен быть равен округлённому в большую сторону корню из длины шифруемой строки, чтобы строка полностью вошла в квадрат. Если строка короче, то остаток можно заполнить произвольными буквами или цифрами.
На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3х3, если не принимать во внимание его повороты и отражения. Счёт волшебным квадратам 4-го порядка уже идёт на сотни, 5-го - на сотни тысяч. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени (в Древнем Китае), так как ручной перебор всех вариантов ключа для этого шифра был немыслим.
На базе этого метода можно составлять разные головоломки. Если использовать метод напрямую, то получится вот такая головоломка:
А если использовать метод наоборот, то получится головоломка типа такой.
Для квадратов 4×4, 6×6 и т.д. таких простых способов их составления не существует, поэтому проще использовать готовые. Например, квадрат Дюрера.
Вращающаяся решётка
Классическая решётка Кардано позволяет скрыть шифровку внутри мусорного текста и является хорошим примером стеганографии . Но если решётку Кардано использовать в качестве ключа для перестановочного шифра, то получим новый метод шифрования — вращающуюся решётку или сетку.
Решётка — это квадрат размером NxN клеток, некоторые из которых вырезаны. Вырезанные клетки могут касаться друг друга, в том числе вершинами, и даже сторонами. В одной клетке — одна буква. Вырезанные клетки должны располагаться таким образом, чтобы никакие две из них не оказывались в одном и том же месте при поворотах решётки.
При помощи конструктора, изображённого ниже, можно изготовить 4 16 (4 294 967 296) таких решёток. Для этого нужно вырезать строго одно из четырёх повторяющихся чисел. Для шифрования без мусора нужно вырезать все номера от 1 до 16, всего 16 клеток. Для шифрования с мусором некоторые числа можно не вырезать, оставшиеся места после шифрования заполнить любыми произвольными буквами, это и будет мусор.
Использовать полученную решётку надо следующим образом. Положить решётку на бумагу и в вырезанные клетки по одной букве начать вписывать шифруемый текст. Как только 16 букв будет вписано, решётка поворачивается на 90°, и вписываются следующие 16 букв, и так ещё два раза. В результате будет вписано 64 буквы. Если текст был короче, то в оставшиеся на бумаге пустые места нужно вписать произвольные буквы. Более длинный текст можно разбить на части по 64, и шифровать каждую отдельно. А можно вписывать в окошки и по две буквы.
Есть второй способ перекладывания решётки во время шифрования — не поворачивать решётку на 90° три раза, а в первый раз повернуть её на 180°, второй раз перевернуть обратной стороной относительно горизонтальной оси, в третий раз - снова повернуть на 180°.
Это были перестановочные шифры. А теперь можно почитать про Шифры замены .
4. ШИФРЫ ПЕРЕСТАНОВКИ
4.1. Основы шифрования
Доподлинно не известно, когда появился шифр перестановки, но вполне возможно, что писцы в древности переставляли буквы в имени своего царя ради того, чтобы скрыть его подлинное имя или в ритуальных целях [43].
Все шифры перестановки делятся на два подкласса:
- шифры одинарной (простой) перестановки. При шифровании символы перемещаются с исходных позиций в новые один раз;
- шифры множественной (сложной) перестановки. При шифровании символы перемещаются с исходных позиций в новые несколько раз.
4.2. Шифры одинарной перестановки
В общем случае для данного класса шифров при шифровании и дешифровании используется таблица перестановок.
Рис.4.1. Таблица перестановок
С увеличением числа n значение n! растет очень быстро (1! = 1, 5! = 120, 10! = 3628800, 15! = 1307674368000). При больших n для приближенного вычисления n! можно воспользоваться формулой Стирлинга
Шифр простой одинарной перестановки. Для шифрования и дешифрования используется таблица перестановок, аналогичная показанной на рис.4.2.
Рис.4.2. Таблица перестановок
Рис.4.3. Таблица перестановок
Количество ключей для данного шифра при фиксированном размере блока равно m!, где m – размер блока.
Рис.4.4. Пример использования шифра маршрутной перестановки
Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:
- количество столбцов в таблице фиксируется и определяется длиной ключа;
- маршрут вписывания - строго слева-направо сверху-вниз;
- шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).
| Ключ | Д | Я | Д | И | Н | А |
| 2 | 6 | 3 | 4 | 5 | 1 | |
| Текст | А | Б | Р | А | М | О |
| В | _ | И | Л | Ь | Я | |
| _ | С | Е | Р | Г | Е | |
| Е | В | И | Ч | _ | _ |
Рис.4.5. Пример использования шифра вертикальной перестановки
| А | ||||||||||
| Б | Р | |||||||||
| А | М | О | ||||||||
| В | _ | И | Л | |||||||
| Ь | Я | _ | С | Е | ||||||
| Р | Г | Е | Е | В | И | |||||
| Д | Я | Д | И | Н | А | Д | Я | Д | И | Н |
| 2 | 10 | 3 | 6 | 8 | 1 | 4 | 11 | 5 | 7 | 9 |
Рис.4.7. Пример использования шифра перестановки при вписывании в треугольник
Для шифрования и дешифрования с помощью данного шифра изготовляется прямоугольный трафарет с четным количеством строк и столбцов. В трафарете вырезаются клетки таким образом, чтобы при наложении его на таблицу того же размера четырьмя возможными способами, его вырезы полностью покрывали все ячейки таблицы ровно по одному разу.
При шифровании трафарет накладывается на таблицу. В видимые ячейки таблицы выписываются буквы исходного текста слева-направо сверху-вниз. Далее трафарет поворачивается и вписывается следующая часть букв. Эта операция повторяется еще два раза. Шифрограмму выписывают из итоговой таблицы по определенному маршруту.
Таким образом, ключом при шифровании является трафарет, порядок его поворотов и маршрут выписывания.
Данный метод шифрования применялся нидерландскими правителями для секретных посланий в 1740-x гr. Он также использовался в армии кайзера Вильгельма в Первую мировую войну. Для шифрования немцы использовали решетки разных размеров, которым французские криптоаналитики дали собственные кодовые имена: Анна (25 букв), Берта (36 букв), Дора (64 буквы) и Эмиль (81 буква). Однако использовались решетки очень недолго (всего четыре месяца) к огромному разочарованию французов, которые только-только начали подбирать к ним ключи.
Магические квадраты. Магическими [нормальными] квадратами называются квадратные таблицы со вписанными в их ячейки последовательными натуральными числами начиная с 1, которые в сумме по каждому столбцу, каждой строке и главным диагоналям дают одно и то же число.
Рис.4.9. Магический квадрат Ло Шу
Рассмотрим квадрат размером 4х4. В него вписываются числа от 1 до 16. Его магия состоит в том, что сумма чисел по строкам, столбцам и полным диагоналям равняется одному и тому же числу - 34.
Рис.4.10. Магический квадрат 4х4
| 16 . | 3 Р | 2 Б | 13 Н |
| 5 М | 10 Я | 11 Д | 8 + |
| 9 Д | 6 О | 7 В | 12 И |
| 4 А | 15 . | 14 А | 1 А |
Рис.4.11. Пример шифрования с помощью магического квадрата
2 Джелорамо Кардано (1501 – 1576 гг.) - итальянский математик, инженер, философ, медик и астролог. В его честь названы открытые Сципионом дель Ферро формулы решения кубического уравнения (Кардано первым их опубликовал) и карданный вал (известного ещё Леонардо да Винчи). Написал около 240 книг (131 из них была опубликована, 111 остались в виде рукописей) [43].
4.3. Шифры множественной перестановки
Рис.4.12. Пример использования шифра двойной перестановки
Ключом к шифру являются размеры таблицы, маршруты вписывания и выписывания, а также порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно n!*m!, n и m – количество столбцов и строк в таблице.
Несмотря на многоступенчатую процедуру шифрования, включая двойную перестановку, данный шифр может быть эквивалентно заменен шифром простой одинарной перестановки. На следующем рисунке приведена таблица эквивалентных одинарных перестановок для примера шифрования, приведенного на рис. 4.12.
Читайте также: