Простая перестановка шифрование python

Реализация и криптоанализ шифра простой перестановки

Всем привет! Продолжается погружение в увлекательный и местами запутанный мир криптографии. Шифр простой перестановки самый легкий из перестановочных, но даже его взлом занял у меня в два раза больше времени и сил, чем шифр Цезаря. Пришлось попотеть с выбором алгоритма криптоанализа. Сначала я пробовал частотный анализ биграмм, но для этого метода нужен очень большой литературный текст, иначе частоты никогда не совпадут с эталонными. Поэтому окончательный выбор пал на метод запрещенных биграмм. Я расскажу о нем подробнее, но сначала пара слов о самом шифре, поехали!

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

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

Определение перестановки(подстановки, расстановки) приводить не буду, о каком шифре может идти речь, если не знать базовых определений?

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

Итак, суть. Дан ключ — перестановка длины N, не большей, чем длина открытого текста. Во время шифрования текст делится на блоки длины N и в каждом блоке символы меняются местами в соответствии с перестановкой. Расшифровка выполняется аналогично.

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

Реализация шифра перестановки на Python

Функция шифрования

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

На вход функция получает текст в виде массива символов и саму перестановку. Объектов для перестановки мы вводить не будем, воспользуемся обычным массивом. Пусть значение каждого индекса будет позицией, в которую перейдет символ. Например, перестановка (012) в виде массива это [1,2,0].

Исходный код функции на Python

Функция расшифровки

Работает аналогично шифрованию, но ничего добивать не нужно.

Исходный код функции на Python

Криптоанализ шифра перестановки методом запрещенных биграмм

Наконец мы добрались до взлома! Естественно, раз используется метод запрещенных биграмм, нам нужен их список. Я его получил с помощь скрипта, о котором писал ранее. Могу с уверенностью сказать, что наиболее полный список получается при анализе набора сочинений Артура Конана Дойля о Шерлоке Холмсе. Единственное, что нужно учитывать — это наличие имен собственных. Для решения этой проблемы можно исключить из текста все слова, содержащие заглавную букву.

Взлом методом запрещенных биграмм можно разделить на два этапа.

— определение длины перестановки;
— нахождение самой перестановки.

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

Что такое столбец. Допустим, что n равно 5, а длина шифра 10. Шифр делится ровно на два блока по пять символов и на пять столбцов по два символа. Нулевой столбец это нулевые символы из каждого блока, первый столбец — первые символы и так далее.

Разбили, теперь нужно «склеивать» столбики, то есть подставлять новый столбец справа и слева к текущему и смотреть на образующиеся биграммы. Попробовать совместить нужно все столбцы. Нам подойдет такая длина n, при которой найдется хотя бы одна склейка столбцов, не образующая запрещенных биграмм. Важная особенность, кроме такой n подойдут так же все длины, кратные ей. Это происходит потому что биграммы сохраняются, просто становится больше столбиков. Так вот, мы должны взять наименьшую такую n. На этом первый этап подошел к концу.

На очереди второй этап. У нас есть длина перестановки, делим текст на столбики. И склеиваем их. При этом заводим массив для верных позиций столбиков. Он формируется следующим образом. Допустим, что мы смогли подставить столбец с индексом 4 справа к столбцу под номером 2 так, чтобы не образовалось запрещенных биграмм. Тогда в массиве появятся такие элементы [2, 4]. Если к этим двум столбцам мы подставили 0-ой слева, массив будет выглядеть так: [0, 2, 4]. Наша задача найти место для каждого столбца. При этом нужно не забыть вести список уже использованных столбиков, чтобы каждый подставить ровно один раз. В итоге у нас получится массив длины n. Для того, чтобы получить открытый текст, достаточно просто вывести символы в соответствии с этой расстановкой.

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

Источник

Реализация и криптоанализ шифра простой замены

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

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

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр простой замены

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

Пример шифрования

Пусть ключ задан следующим образом: (b, a, c, y, v, f, g, u, i, j, k, l, w, n, o, p, q, r, s, t, h, e, m, x, d, z). Алфавит, в котором далеко не все символы стоят на своих законных местах. Дан открытый текст: «hellomynameiskirill». После применения шифра простой замены, мы получим шифротекст: «uvllowdnbwviskirill». Остатки открытого текста прослеживаются потому что мне было лень придумывать хороший ключ, но в идеале шифротекст будет совершенно неузнаваем.

Реализация шифра простой замены

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

alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'] #Функция шифрования по ключу #text - list символов текста #key - list с перестановкой на алфавите def encrypt(text, key): result = [] for i in range(len(text)): result.append(key[alphabet.index(text[i])]) return result

Криптоанализ шифра простой замены

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

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

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

Замечание 1. Для того, чтобы не расшифровывать текст по новой после каждой перестановки на ключе, мы просто меняем в словаре частоты соответствующих биграмм(строки 80-88).

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

Источник