Некоторое время назад я написал сообщение о реализации шифра сдвига Цезаря в Python. Теперь я расширю тему, реализовав шифр Виженера.
Шифр Виженера
Шифр Виженера был изобретен в 1553 году итальянцем Джован Баттиста Беллазо, но теперь ошибочно назван в честь француза Блеза де Виженера. Он не был сломан до 1863 года, хотя в наши дни он очень небезопасен и теперь полезен только как интересное упражнение по программированию. Если вы хотите прочитать об этом полностью, ознакомьтесь с статьей в Википедии.
Проблема с шифром сдвига Цезаря заключается в том, что каждая буква всегда шифруется одинаково, поэтому, например, если E, самая распространенная буква, всегда зашифровывается как S, тогда простой частотный анализ выявит сдвиг, если у вас есть достаточно длинный фрагмент кода. зашифрованный текст.
Шифр Виженера более сложен в том смысле, что буква может быть зашифрована, как и любая другая буква, в зависимости от ее положения в открытом тексте. Он даже может быть зашифрован сам по себе, чего не могла сделать знаменитая немецкая машина Enigma времен Второй мировой войны, предоставляя союзникам возможность взломать код.
Процессы шифрования и дешифрования включают использование таблицы букв, известной как квадрат Виженера, таблица Виженера из Tabula Recta, которая выглядит следующим образом.
Чтобы зашифровать строку текста, вам нужно ключевое слово. Это может быть что угодно, но в идеале должно быть разумной длины. В этом примере я буду использовать «Воображение важнее знаний» в виде открытого текста и «оркестр» в качестве ключевого слова.
Открытый текст удаляется из всех символов, кроме букв a-z и A-Z, а затем преобразуется в верхний регистр. Затем ключевое слово повторяется для создания строки той же длины, что и открытый текст. Используя упомянутые примеры, мы получаем следующий открытый текст и ключевое слово:
ВООБРАЖЕНИЕ БОЛЬШЕ ВАЖНОГО БЛАГОДАРНОСТИ
ORCHESTRAORCHESTRAORCHESTRAORCHESTRAORC
Каждая буква в открытом тексте теперь имеет соответствующую букву в ключевом слове. Если мы находим букву открытого текста в верхней части Tabula Recta, букву ключевого слова в левой части, буква, где встречаются столбец и строка, используется для шифрования этого конкретного экземпляра буквы открытого текста.
Например, первая буква открытого текста - это I, а его ключевое слово - буква O, и они пересекаются в точке W. Вторая буква I связана с E, поэтому зашифровывается как M. Весь открытый текст зашифровывается как:
WDCNMFTKICEKZQGKVIAGQYXSGKTVRPRRGPCERXG
Чтобы расшифровать текст, мы просто выполняем обратный процесс: переходим к строке с соответствующей буквой ключевого слова, выполняем поиск, чтобы найти зашифрованную букву, а затем берем букву в заголовке этого столбца.
Существует также алгебраический метод шифрования / дешифрования с помощью шифра Виженера, для которого не требуется Tabula Recta. Он использует алфавит с нулевым отсчетом для целочисленных отображений, поэтому A = 0, B = 1 и т. Д., Простая концепция для понимания любого программиста!
Формула шифрования:
enciphered index = (plaintext index + keyword index) mod 26
Для первой буквы примера I = 8 и O = 14, поэтому:
enciphered index = (8 + 14) mod 26 = 22 = W
Алгебраическая дешифровка использует формулу:
deciphered index = (enciphered index — keyword index) mod 26
so:
enciphered index = (22–14) mod 26 = 8 = I
Фактическое шифрование / дешифрование может быть выполнено всего в одной строке кода, независимо от того, используете ли вы таблицу или алгебру, поэтому я реализую оба метода, которые вы можете опробовать, прокомментировав / раскомментировав соответствующие строки.
План проэкта
Я буду реализовывать шифр Виженера как класс с двумя методами: один для шифрования, а другой - для дешифрования. Открытый текст, зашифрованный текст и ключевое слово будут аргументами метода, поэтому класс не будет иметь состояния, за исключением Tabula Recta, который будет создан в __init__.
Помимо методов нам понадобится несколько служебных функций для решения следующих задач:
- Создание Tabula Recta
- Обработка открытого текста путем удаления всего, кроме букв, и преобразования в верхний регистр
- Создание ключевого слова длины открытого текста путем повторения основного ключевого слова
Код
Этот проект состоит из следующих двух файлов Python, которые вы можете получить из репозитория Github.
- vigenerecipher.py
- vigenerecipherdemo.py
Это vigenerecipher.py.
Во-первых, обратите внимание, что мы импортируем re (Regex).
В __init__ мы просто вызываем __create_tabula_recta.
Сама функция __create_tabula_recta немного неудобна, потому что при заполнении строк мы должны каждый раз добавлять смещение, которое затем увеличивается. Каждый раз, когда это делается, нам нужно проверять, не исчерпал ли он конец алфавита. В таком случае мы просто вычитаем 26, чтобы вернуться к началу.
Затем идет метод encipher, который сначала получает обработанную версию открытого текста и повторяющуюся версию ключевого слова, а затем создает пустой список для зашифрованных писем.
Затем мы перебираем буквы открытого текста, вычисляя индексы двух букв в текущей паре, вычитая 65 из кодов ASCII. Существует две реализации фактического шифрования, одна с использованием Tabula Recta, а другая с использованием алгебры. Затем мы добавляем зашифрованную букву и после цикла присоединяемся к списку, чтобы создать и вернуть зашифрованный текст в виде строки.
Метод decipher работает примерно так же, и снова дает вам на выбор Tabula Recta или алгебраическую реализацию.
Функция __process_plaintext использует очень простое регулярное выражение для удаления всего, кроме букв A-Z. (Регулярное выражение заставляет мой мозг болеть, но даже я могу понять это!)
Наконец, функция __get_keyword_repeated повторяет ключевое слово столько раз, сколько необходимо, чтобы создать строку той же длины, что и открытый текст.
Итак, теперь нам просто нужно немного кода, чтобы опробовать его.
Все очень просто, достаточно создать VigenereCipher объект и вызвать его методы. А теперь давайте запустим.
python3.8 main.py
Результат:
Помните, что и шифрование, и дешифрование реализованы двумя способами, поэтому вы можете опробовать оба, немного комментируя / раскомментируя в нужных местах.
