Шифр Цезаря и частотный анализ с Python

Классические шифры

Так что же такое классический шифр? Согласно Википедии справедливо следующее определение:

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

Установка цели

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

Общее объяснение шифра

В шифре Цезаря метод шифрования заключается в замене каждой буквы обычного текста другой буквой с использованием числового целочисленного ключа. Я буду использовать букву k для обозначения ключа и букву p для обозначения простого текста. Подстановка выполняется следующим образом: каждая буква в p заменяется буквой, следующей за ней на k букв в алфавите, например, на k= 1буква A будет заменена буквой B, буква E будет заменена буквой F и буква Z будет заменена буквой A. Из этого объяснения мы можем вывести математическую функцию для дешифрования и шифрования шифра Цезаря. для x = буква, которую нужно зашифровать, мы можем использовать формулу E(x) = (x + k) mod 26для шифрования. длярасшифровки мы можем использовать формулуE(x) = (x - k) mod 26.

Примечание. k≥26 эквивалентно k = k mod 26, поскольку размер английского алфавита равен 26.

Шифрование

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

Расшифровка

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

Частотный анализ и взлом шифра

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

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

Бегло взглянув на этот график, мы видим, что некоторые буквы встречаются гораздо чаще, чем другие, например, буквы e,t,a,o,i встречаются чаще всего. Мы можем использовать эту информацию в своих интересах, чтобы атаковать Caser Cipher. В результате метода шифрования, используемого в шифре Кейзера, логично предположить, что если бы мы построили аналогичный график частоты букв в заданном зашифрованном тексте, мы получили бы похожий график, но с другими буквами. самый распространенный. Судя по этому графику, если, например, наиболее распространенной буквой была f, то, скорее всего, k=1, поскольку расстояние от e, самая распространенная буква для f — 1. Важно отметить, что для того, чтобы этот метод был эффективным, требуется прилично большой текст.

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

Теперь, когда у нас есть интуиция для частотного анализа, мы можем разработать метод присвоения балла тексту, указывающего, насколько он близок к английскому языку, так что чем ниже балл, тем больше вероятность того, что это настоящий английский. Способ, которым мы можем достичь этого, состоит в суммировании различий ожидаемой частоты букв и той, которая присутствует в исследуемом тексте. Например, если ожидаемая частота появления буквы e составляет 12,8%, а расчетная частота появления буквы e составляет 11,9%. em> тогда разница составляет 12,8–11,9 = 0,9%. После получения этой суммы мы можем нормализовать ее, разделив на размер английского алфавита, который равен 26. Мы можем выразить это с помощью математической функции следующим образом: