Дешифруйте сообщение зашифрованное методом перестановки
Обновлено: 05.07.2024
Всем привет! Продолжается погружение в увлекательный и местами запутанный мир криптографии. Шифр простой перестановки самый легкий из перестановочных, но даже его взлом занял у меня в два раза больше времени и сил, чем шифр Цезаря. Пришлось попотеть с выбором алгоритма криптоанализа. Сначала я пробовал частотный анализ биграмм, но для этого метода нужен очень большой литературный текст, иначе частоты никогда не совпадут с эталонными. Поэтому окончательный выбор пал на метод запрещенных биграмм. Я расскажу о нем подробнее, но сначала пара слов о самом шифре, поехали!
Прежде чем продолжить чтение, обратите внимание на реализации других шифров
Шифр простой перестановки
Определение перестановки(подстановки, расстановки) приводить не буду, о каком шифре может идти речь, если не знать базовых определений?
Шифр перестановки называется простым, если элементы открытого текста меняют свои позиции только один раз. Существуют шифры множественной перестановки, в которых первым делом меняются символы в каждом блоке, а потом, например, меняются местами сами блоки. Этих крутых ребят мы сейчас трогать не будем и заострим свое внимание исключительно на первой разновидности шифра.
Итак, суть. Дан ключ — перестановка длины N, не большей, чем длина открытого текста. Во время шифрования текст делится на блоки длины N и в каждом блоке символы меняются местами в соответствии с перестановкой. Расшифровка выполняется аналогично.
В шифровании и расшифровании ничего сверхсложного и необычного нет. Все самое интересное сосредоточено во взломе. Поэтому предлагаю перейти сразу к реализации и разобрать метод запрещенных биграмм с ее помощью.
Реализация шифра перестановки на Python
Функция шифрования
Естественно, если текст не делится на длину перестановки, его нужно добить. Иногда добивают нулями, но это визуально просматривается, поэтому я добавлял случайные символы из алфавита.
На вход функция получает текст в виде массива символов и саму перестановку. Объектов для перестановки мы вводить не будем, воспользуемся обычным массивом. Пусть значение каждого индекса будет позицией, в которую перейдет символ. Например, перестановка (012) в виде массива это [1,2,0].
Исходный код функции на Python
Функция расшифровки
Работает аналогично шифрованию, но ничего добивать не нужно.
Исходный код функции на Python
Криптоанализ шифра перестановки методом запрещенных биграмм
Наконец мы добрались до взлома! Естественно, раз используется метод запрещенных биграмм, нам нужен их список. Я его получил с помощь скрипта, о котором писал ранее. Могу с уверенностью сказать, что наиболее полный список получается при анализе набора сочинений Артура Конана Дойля о Шерлоке Холмсе. Единственное, что нужно учитывать — это наличие имен собственных. Для решения этой проблемы можно исключить из текста все слова, содержащие заглавную букву.
Взлом методом запрещенных биграмм можно разделить на два этапа.
— определение длины перестановки;
— нахождение самой перестановки.
На первом этапе мы должны найти все целые делители шифра. Для каждого из них разбить шифр на столбцы.
Что такое столбец. Допустим, что n равно 5, а длина шифра 10. Шифр делится ровно на два блока по пять символов и на пять столбцов по два символа. Нулевой столбец это нулевые символы из каждого блока, первый столбец — первые символы и так далее.
На очереди второй этап. У нас есть длина перестановки, делим текст на столбики. И склеиваем их. При этом заводим массив для верных позиций столбиков. Он формируется следующим образом. Допустим, что мы смогли подставить столбец с индексом 4 справа к столбцу под номером 2 так, чтобы не образовалось запрещенных биграмм. Тогда в массиве появятся такие элементы [2, 4]. Если к этим двум столбцам мы подставили 0-ой слева, массив будет выглядеть так: [0, 2, 4]. Наша задача найти место для каждого столбца. При этом нужно не забыть вести список уже использованных столбиков, чтобы каждый подставить ровно один раз. В итоге у нас получится массив длины n. Для того, чтобы получить открытый текст, достаточно просто вывести символы в соответствии с этой расстановкой.
Описание алгоритма завершено, для того, чтобы лучше его понять, нужно посмотреть и потрогать реализацию. Попробовать выводить столбики на разных итерациях и следить за тем, что происходит. Я постарался максимально подробно комментировать каждый шаг алгоритма.
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.
При использовании шифров перестановки входной поток исходного текста делится на блоки, в каждом из которых выполняется перестановка символов. Перестановки в классической "докомпьютерной" криптографии получались в результате записи исходного текста и чтения шифрованного текста по разным путям геометрической фигуры.
Например, для d=6 в качестве ключа перестановки можно взять 436215 . Это означает, что в каждом блоке из 6 символов четвертый символ становится на первое место , третий – на второе, шестой – на третье и т.д. Пусть необходимо зашифровать такой текст:
Другим примером методов перестановки является перестановка по таблице. В этом методе производится запись исходного текста по строкам некоторой таблицы и чтение его по столбцам этой же таблицы. Последовательность заполнения строк и чтения столбцов может быть любой и задается ключом.
Рассмотрим пример. Пусть в таблице кодирования будет 4 столбца и 3 строки (размер блока равен 3*4=12 символов). Зашифруем такой текст:
Затем будем считывать из таблицы каждый блок последовательно по столбцам:
Можно считывать столбцы не последовательно, а, например, так: третий, второй, первый, четвертый:
В этом случае порядок считывания столбцов и будет ключом.
Затем будем считывать из таблицы последовательно по столбцам:
Для расшифрования на приемной стороне устанавливается другой блок, восстанавливающий порядок цепей.
Аппаратно реализуемая перестановка широко используется на практике как составная часть некоторых современных шифров.
Мы рассмотрели общую схему симметричного шифрования и классификацию простейших методов шифрования с закрытым ключом. В следующей лекции мы познакомимся с принципами построения современных блочных алгоритмов
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
Алгоритм шифра перестановки
Ключ в шифре перестановки имеет следующий вид:
В первой строке таблицы указаны номера символов блока по порядку, а во второй строке указаны номера позиций, которые должны занимать указанные символы в зашифрованном блоке текста.
Кодирование осуществляется перестановкой букв. Таким образом первый символ из исходного блока должен быть переставлен на второе место, второй на четвертое, третий на первое, четвертый на третье.
Если данным ключом зашифровать слово кофе, то получится слово фкео.
Дешифрование производится в обратном порядке. На примере указанного ключа: второй символ из зашифрованного блока ставим на первое место, четвертый на второе, первый на третье, третий на четвертое.
При использовании любого блочного шифра (шифр перестановки не исключение), может возникнуть ситуация, когда текст не делится на равные блоки длины m. То есть остаток от деления длины текста n на длину ключа m не равен нулю.
Читайте также: