Реализация и дешифрование шифров Виженера и Цезаря в Python

IX муниципальный научный форуме для обучающихся 4-11-х классов                                          образовательных организаций г. Владикавказа

«Созвездие Интеллектуалов»

                                                Секция  Информатика

Проектная работа на тему:

«Реализация и дешифрование шифров Виженера и Цезаря в Python»

Автор работы: Черджиев Феликс Ибрагимович

ученик 11«А» класса, МБОУ СОШ №22

им. Коняева Виктора Михайловича,

 МАУ ДО Центр «Интеллект»,

Научный руководитель: Подова Анна Николаевна, педагог ДО МАУ ДО Центр «Интеллект», учитель информатики МБОУ СОШ №22

• Владикавказ

2021г.

Содержание

ВВЕДЕНИЕ        4

Терминология        7

ГЛАВА I. Криптография        9

Понятие о криптографии        9

Определение        9

Математическая модель        9

История криптографии        10

Четыре периода развития криптографии        10

Эволюция криптографии        10

Шифр Цезаря        12

Определение        12

Математическая модель        12

Шифр Виженера        13

Определение        13

История        13

Математическая модель        13

ГЛАВА II. Криптоанализ        14

Принципы криптоанализа        14

Принцип Керкгоффса        14

Шесть требований Керкгоффса        14

Максима Шеннона        14

Частотный анализ        15

Определение        15

История        15

Описание        16

Индекс совпадений        17

Определение        17

История        17

Общий случай        17

Открытый текст        17

Случайная строка        18

Взаимный индекс совпадений        19

Определение        19

Общий случай        19

Строки со сдвигом        19

Дешифрование шифра Цезаря        21

Два случая дешифрования        21

Взлом без знания шифр        21

Взлом без знания ключ        21

Дешифрование шифра Виженера        22

Два этапа дешифрования        22

Нахождение длины ключа        22

Нахождение ключа        22

Практическая часть        24

План работы        24

Внутренняя составляющая программы        24

Программная оболочка        24

Комментарии к написанию программного кода        25

Исходный программный код        25

Внешний вид программы        25

Инструкция к программе        26

ЗАКЛЮЧЕНИЕ        28

СПИСОК ЛИТЕРАТУРЫ        29

ПРИЛОЖЕНИЕ        30

Введение

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

Шифр (от фр. сhiffre “цифра”) — система обратимых преобразований, зависящая от некоторого секретного параметра (ключа) и предназначенная для обеспечения секретности передаваемой информации. Он может представлять собой совокупность условных знаков (условная азбука из цифр, букв или определённых знаков) либо алгоритм преобразования обычных цифр и букв. 

Ключ — секретная информация, используемая криптографическим алгоритмом при шифровании сообщений. Ключ задаёт параметры, согласно которым в исходный текст и вносятся изменения. Полученный текст варьируется от ключа, так что без правильного ключа расшифровать текст не удастся (если идти в лоб, а не использовать методы взлома)

Процесс преобразования информации с помощью шифра называется шифрованием и делится на зашифровывание (засекречивание сообщения) и расшифровывание (рассекречивание). Процесс расшифровки без использования ключа называется дешифрованием.

Существует две общие науки (раздела информатики), связанные с шифрами: 

• Криптография (от др.-греч. κρυπτός “скрытый” + γράφω “пишу”) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта), шифрования. Криптография — одна из старейших наук, её истории больше 4 тыс. лет. 

• Криптоанализ (от др.-греч. κρυπτός “скрытый” + “анализ”) — наука о методах получения исходного значения зашифрованной информации без предназначенного для этого ключа. Молодая наука: термин введён американским криптографом Уильямом Ф. Фридманом в 1920-м году в рамках его книги «Элементы криптоанализа». *

* — Дэвид Кан, «Взломщики кодов» – фундаментальный труд по истории криптографии (см. прил. 1)

Длинная, богатая история криптографии насчитывает более четырёх тысяч лет, ведь всегда была нужда ограничивать доступ к важной информации. Криптоанализ же гораздо моложе, и развивался он довольно медленно; скачок в развитии ему дало появление роторных машин и компьютеров.

В истории с течением времени усложнялись как сами шифры, так и методы их взлома. Кроме того, шифры распространены повсеместно, и наша страна не является исключением: ярким примером тому может служить письмо царя Алексея Михайловича Тишайшего своему двоюродному брату стольнику Афанасию Ивановичу Матюшкину, писанное тайнописью (см. прил. 2).

Современная криптография образует отдельное научное направление на стыке математики и информатики — работы в этой области публикуются в научных журналах, организуются регулярные конференции. Практическое применение криптографии стало неотъемлемой частью жизни современного общества — её используют в таких отраслях, как электронная коммерция, электронный документооборот (включая цифровые подписи), телекоммуникации и других.

На свете множество неразгаданных шифров, непонятых языков, загадочных тайнописей и нерасшифрованных карт, но мы остановимся лишь на 2 из них:

• Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря;

• Шифр Виженера (фр. Chiffre de Vigenère).

Шифр Цезаря называют в честь Гая Юлия Цезаря, который согласно «Жизни двенадцати царей» Светония использовал его со сдвигом 3, чтобы защищать военные сообщения. Цезарь был первым зафиксированным человеком, использующим эту схему, но ещё и до него были зафиксированы случаи использования других, похожих шифров подстановки.

Шифр Виженера, названный в честь Блеза Виженера, объединил подходы Тритемия, Беллазо, Порта к шифрованию открытых текстов, по существу, не внеся в них ничего оригинального. Дэвид Кан в своей книге «Взломщики кодов» (см. прил. 1) отозвался об этом осуждающе, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то что он ничего не сделал для его создания».

Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Известный писатель и математик Чарльз Лютвидж Доджсон назвал шифр Виженера невзламываемым в своей статье «Алфавитный шифр» англ. «The Alphabet Cipher», опубликованной в детском журнале в 1868 году. В 1917 году Scientific American также отозвался о шифре Виженера как о не поддающемся взлому. Это представление было опровергнуто после того, как Фридрих Касиски полностью взломал шифр в XIX веке, хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками ещё в XVI веке. 

Актуальность:

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

Изучив основу их работы, а также самостоятельно воссоздав её своими руками можно понять основы криптографии, необходимые для более трудных шифров. Более того, рассмотрев их криптоаналитические аспекты и принципы их взлома и алгоритмизировав их в виде компьютерного кода можно использовать аналогичные методы на шифрах более высокого порядка. Изучение первых шифров поможет лучше понять, зачем нужна та или иная операция в современных алгоритмах шифрования.

Именно поэтому нужно знать и уметь реализовывать шифрование и дешифрование этих важных исторических шифров.

Цель проектной работы:

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

Задачи работы:

        • Познакомиться с теоретическим описанием устройства и работы шифров Цезаря и Виженера;

        • Познакомиться с методами криптоанализа данных шифров;

        • С помощью методов частотного анализа, расчёта индексов совпадения и лингвистического сравнения научиться взламывать шифры Цезаря и Виженера;

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

Предмет исследования:

Устройство шифров Цезаря и Виженера, методы расчёта индексов совпадения, частотного анализа и лингвистического сравнения

Методы исследования:

Изучение и анализ научной литературы по криптографии, криптоанализу, программированию и информатике;

Исследовательский способ;

Компьютерное моделирование и практическая работа (создание компьютерной программы).

Терминология

• Открытый (исходный) текст — данные (не обязательно текстовые), передаваемые без использования криптографии или, другими словами, незашифрованные данные.
• Шифротекст, шифрованный (закрытый) текст — данные, полученные после применения криптосистемы (обычно — с некоторым указанным ключом). Другое название: криптограмма.
• Шифр, криптосистема — семейство обратимых преобразований открытого текста в шифрованный.
• Ключ — параметр шифра, определяющий выбор конкретного преобразования данного текста. В современных шифрах криптографическая стойкость шифра целиком определяется секретностью ключа (принцип Керкгоффса). Также выделяют ключ шифрования (encryption key) и ключ расшифрования (decryption key)
• Шифрование — процесс нормального применения криптографического преобразования открытого текста на основе алгоритма и ключа, в результате которого возникает шифрованный текст.
• Расшифровывание — процесс нормального применения криптографического преобразования шифрованного текста в открытый.
• Асимметричный шифр, двухключевой шифр, шифр с открытым ключом — шифр, в котором используются два ключа, шифрующий и расшифровывающий. При этом, зная лишь ключ зашифровывания, нельзя расшифровать сообщение, и наоборот.
• Открытый ключ — тот из двух ключей асимметричной системы, который свободно распространяется. Шифрующий для секретной переписки и расшифровывающий — для электронной подписи.
• Секретный ключ, закрытый ключ — тот из двух ключей асимметричной системы, который хранится в секрете.

• Криптоанализ — наука, изучающая математические методы нарушения конфиденциальности и целостности информации.
• Криптоаналитик — учёный, создающий и применяющий методы криптоанализа.
• Криптография и криптоанализ составляют криптологию, как единую науку о создании и взломе шифров (такое деление привнесено с запада, до этого в СССР и России не применялось специального деления).
• Криптографическая атака — попытка криптоаналитика вызвать отклонения в атакуемой защищённой системе обмена информацией. Успешную криптографическую атаку называют взлом или вскрытие.
• Дешифрование (дешифровка) — процесс извлечения открытого текста без знания криптографического ключа на основе известного шифрованного. Термин дешифрование обычно применяют по отношению к процессу криптоанализа шифротекста (криптоанализ сам по себе, вообще говоря, может заключаться и в анализе криптосистемы, а не только зашифрованного ею открытого сообщения).
• Криптографическая стойкость — способность криптографического алгоритма противостоять криптоанализу.

• Имитозащита — защита от навязывания ложной информации. Другими словами, текст остаётся открытым, но появляется возможность проверить, что его не изменяли ни случайно, ни намеренно. Имитозащита достигается обычно за счёт включения в пакет передаваемых данных имитовставки.
• Имитовставка — блок информации, применяемый для имитозащиты, зависящий от ключа и данных.
• Электронная цифровая подпись, или электронная подпись — асимметричная имитовставка (ключ защиты отличается от ключа проверки). Другими словами, такая имитовставка, которую проверяющий не может подделать.
• Центр сертификации — сторона, чья честность неоспорима, а открытый ключ широко известен. Электронная подпись центра сертификации подтверждает подлинность открытого ключа.

• Хеш-функция — функция, которая преобразует сообщение произвольной длины в число («свёртку») фиксированной длины. Для криптографической хеш-функции (в отличие от хеш-функции общего назначения) сложно вычислить обратную и даже найти два сообщения с общей хеш-функцией.
• Гибри́дная криптосисте́ма — это система шифрования, совмещающая преимущества криптосистемы с открытым ключом с производительностью симметричных криптосистем.

Криптография

Понятие о криптографии

Криптография – это наука о методах, алгоритмах, программных и аппаратных средствах преобразования информации в целях сокрытия ее содержания, предотвращения видоизменения или несанкционированного использования.

На сегодняшний день существует масса алгоритмов шифрования, имеющих значительную стойкость перед криптоанализом (криптографическую стойкость). Принято деление алгоритмов шифрования на три группы:

• Симметричные алгоритмы

• Ассиметричные алгоритмы

• Алгоритмы хэш-функций

Математическая модель

Все преобразования в криптографии устроены следующим образом: Отправитель генерирует открытый текст исходного сообщения M, которое должно передаваться по открытому каналу. Отправитель шифрует текст с помощью обратимого преобразования E и ключа K: EK и получает шифротекст C=EK(M), который отправляет получателю. Получатель, приняв шифротекст C, расшифровывает его с помощью обратного преобразования D=EK-1 и получает исходное сообщение в виде открытого текста M: M=D(C)=EK-1(EK(M)).

Преобразование EK выбирается из семейства криптографических преобразований, называемых криптоалгоритмами. Параметр, с помощью которого выбирается конкретное преобразование, называется криптографическим ключом K. Система, в которой осуществляется зашифровывание и расшифровывание сообщений, называется криптосистемой.

Обобщённая схема криптографической системы, обеспечивающей шифрование передаваемой информации, имеет вид (см. прил. 3).

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

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

История криптографии

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

В целом, всю историю можно разделить на четыре основных периода:

• Первый период (приблизительно с 3-го тысячелетия до н. э.) характеризуется господством моноалфавитных шифров (основной принцип — замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами).

• Второй период (хронологические рамки — с IX века на Ближнем Востоке (Ал-Кинди) и с XV века в Европе (Леон Баттиста Альберти) — до начала XX века) ознаменовался введением в обиход полиалфавитных шифров.

• Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров.

• Четвёртый период — с середины до 70-х годов XX века — период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости для различных известных атак —линейного и дифференциального криптоанализа. Однако до 1975 года криптография оставалась «классической» или же, более корректно, криптографией с секретным ключом.

Эволюция криптографии

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

В древние времена шифрование применялось главным образом в военном и торговом деле, шпионаже, среди контрабандистов.

Несколько позже ученые-историки определяют дату появления другой родственной науки – стеганография. Эта наука занимается маскировкой самого факта передачи сообщения. Зародилась она в античности, а примером здесь может служить получение спартанским царем Леонидом перед битвой с персами провощенной дощечки с текстом, покрытой сухим легкосмываемым раствором. При очистке оставленные на воске стилусом знаки становились отчетливо видимыми. Сегодня для сокрытия сообщения служат симпатические чернила, микроточки, микропленки и т.д.

С развитием математики стали появляться математические алгоритмы шифрования, но все эти виды криптографической защиты информации сохраняли в разной объемной степени статистические данные и оставались уязвимыми. Уязвимость стала особенно ощутима с изобретением частотного анализа, который был разработан в IX веке нашей эры предположительно арабским энциклопедистом Ал-Кинди. И только в XV веке, после изобретения полиалфавитных шрифтов Леоном Баттистой Альберти (предположительно), защита перешла на качественно новый уровень. Однако в середине XVII века Чарлз Бэббидж представил убедительные доказательства частичной уязвимости полиалфавитных шрифтов перед частотным анализом.

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

До бурного развития науки в XX веке криптографам приходилось иметь дело только с лингвистическими объектами, а в ХХ веке открылись возможности применения различных математических методов и теорий, статистики, комбинаторики, теории чисел и абстрактной алгебры.

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

Сегодня можно говорить о значительных разработках в квантовой криптографии.

Шифр Цезаря

Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, “А” была бы заменена на “Г”, “Б” станет “Д”, и так далее (см. прил. 4-5).

Этот шифр, известный также как шифр сдвига, код Цезаря или сдвиг Цезаря, является одним из самых простых и наиболее широко известных методов шифрования.

Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и всё ещё имеет современное приложение в системе ROT13. Как и все моноалфавитные шифры, шифр Цезаря легко взламывается и не имеет почти никакого применения на практике. Тем не менее, он является одним из самых ярких и важных примеров в развитии шифров, в том числе и моноалфавитных.

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

Математическая модель

Если сопоставить каждому символу алфавита его порядковый номер (нумеруя с 0), то шифрование можно выразить формулами модульной арифметики:

y=(x+k) mod n, x=(y+k) mod n,

где x — символ исходного текста, y — символ шифрованного текста, n — мощность алфавита, k — ключ.

С точки зрения математики шифр Цезаря является частным случаем афинного шифра.

Шифр Виженера

Шифр Виженера (фр. Chiffre de Vigenère) — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова. Этот метод является простой формой многоалфавитной замены, то есть, по сути, усложнённой формой метода шифра Цезаря.

Шифр Виженера изобретался многократно. Впервые этот метод описал Джовани Баттиста Белласо (итал. Giovan Battista Bellaso) в книге «La cifra del. Sig. Giovan Battista Bellasо» в 1553 году, однако в XIX веке получил имя Блеза Виженера, французского дипломата. Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа. Многие люди пытались реализовать схемы шифрования, которые по сути являлись шифрами Виженера.

Хотя шифр легко понять и реализовать, на протяжении трех столетий он противостоял всем попыткам его сломать; чем и заработал название “le chiffre indéchiffrable” (с французского “неразгаданный шифр”).

Описание

В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например, в шифре Цезаря при сдвиге +3, A стало бы Г, Б стало бы Д и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая “tabula recta” или квадрат (таблица) Виженера (см. прил. 7-8).

Применительно к русскому алфавиту таблица Виженера составляется из строк по 33 символов (26 для латинского), причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 33 (26) различных шифров Цезаря. Иногда также выделяют версию с русским алфавитом без буквы “ё”, что значительно упрощает некоторые процессы шифрования и дешифрования, а также реализацию шифра в виде компьютерной программы.

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

Математическая модель

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

cj=(mj+kj) mod n, mj=(cj+n-kj) mod n,

где n — количество букв в алфавите, mj — буквы исходного текста, kj — буквы ключа

Криптоанализ

Принципы криптоанализа

При́нцип Керкго́ффса – правило разработки криптографических систем, согласно которому в засекреченном виде держится только определённый набор параметров алгоритма, называемый ключом, а сам алгоритм шифрования должен быть открытым. Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей. Широко применяется в криптографии. Впервые данный принцип сформулировал в XIX веке голландский криптограф Огюст Керкгоффс.

Шесть требований Керкгоффса

В 1883 голландский криптограф Огюст Керкгоффс изложил шесть принципов проектирования военных шифров в своей книге «Военная криптография» (см. прил. 6). Шесть основных требований к криптосистеме, все из которых до настоящего времени определяют проектирование криптографически стойких систем, в переводе с французского звучат так:

1. Система должна быть физически, если не математически, невскрываемой;
2. Нужно, чтобы не требовалось сохранение системы в тайне; попадание системы в руки врага не должно причинять неудобств;
3. Хранение и передача ключа должны быть осуществимы без помощи бумажных записей; корреспонденты должны располагать возможностью менять ключ по своему усмотрению;
4. Система должна быть пригодной для сообщения через телеграф;
5. Система должна быть легко переносимой, работа с ней не должна требовать участия нескольких лиц одновременно;
6. Наконец, от системы требуется, учитывая возможные обстоятельства её применения, чтобы она была проста в использовании, не требовала значительного умственного напряжения или соблюдения большого количества правил.

Второе из этих требований и стало известно как «принцип Керкгоффса».

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

Стоит добавить, что это можно трактовать и так, что раз предполагается, что взломщик знает о шифре всё, то необходимо разрабатывать свои криптосистемы отталкиваясь от этого факта (максима Шеннона). 

Частотный анализ

Частотный анализ, частотный криптоанализ — один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей, как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования (см. прил. 9-10).

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

Метод частотного криптоанализа известен с IX века (работы Ал-Кинди), хотя наиболее известным случаем его применения в реальной жизни, возможно, является дешифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году. В художественной литературе наиболее известными упоминаниями являются рассказы «Золотой жук» Эдгара По, «Пляшущие человечки» Конан Дойля, а также роман «Дети капитана Гранта» Жюль Верна.

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

История

Частотный анализ слов не является находкой современности. Научному миру он известен еще с IX века. Его создание связывают с именем Ал-Кинди.

Но известные случаи применения метода частотного анализа относятся к гораздо более позднему периоду. Самым ярким примером здесь можно назвать дешифровку египетских иероглифов, произведенную в 1822 году Ж.-Ф. Шампольоном.

Если мы обратимся к художественной литературе, то можем найти немало любопытных отсылок к подобному методу дешифровки:

• Конан Дойль - "Пляшущие человечки".

• Жюль Верн - "Дети капитана Гранта".

• Эдгар По - "Золотой жук".

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

Описание

Утверждается, что вероятность появления отдельных букв, а также их порядок в словах и фразах естественного языка подчиняются статистическим закономерностям: например, пара стоящих рядом букв “ся” в русском языке более вероятна, чем “цы”, а “оь” в русском языке не встречается вовсе (зато часто встречается, например, в чеченском). Анализируя достаточно длинный текст, зашифрованный методом замены, можно по частотам появления символов произвести обратную замену и восстановить исходный текст.

Как упоминалось выше, важными характеристиками текста являются повторяемость букв (количество различных букв в каждом языке ограничено), пар букв, то есть m (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие особенности. Примечательно, что эти характеристики являются достаточно устойчивыми.

Идея состоит в подсчёте чисел вхождений каждой nm возможных m-грамм в достаточно длинных открытых текстах T=t1t2…tl, составленных из букв алфавита {a1, a2, …, an}. При этом просматриваются подряд идущие m-граммы текста:

t1t2…tm, t2t3… tm+1, …, ti-m+1tl-m+2…tl.

Если L (ai1ai2 … aim) — число появлений m-граммы ai1ai2…aim в тексте T, а L — общее число подсчитанных m-грамм, то при достаточно больших L частоты L (ai1ai2 … aim)/L, для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (ai1ai2…aim) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

В общем случае частоту букв в процентном выражении можно определить следующим образом: подсчитывается, сколько раз она встречается в шифротексте, затем полученное число делится на общее число символов шифротекста; для выражения в процентах, полученный результат умножается на 100.

Частотность существенно зависит, однако, не только от длины текста, но и от его характера. Например, в техническом тексте обычно редкая буква “Ф” может появляться гораздо чаще. Поэтому для надёжного определения средней частоты букв желательно иметь набор различных текстов.

Индекс совпадений

Индекс совпадений — один из методов криптоанализа шифра Виженера. Описание было опубликовано Уильямом Фридманом в 1920 году.

Метод основывается на вычислении вероятности того, что два случайных элемента текста совпадут. Эту вероятность называют индексом совпадений. Уильям Фридман показал, что значения индекса совпадений существенно отличаются для текстов различной природы. Это позволяет сначала определить длину ключа шифра, а затем найти и сам ключ.

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

История

Блез Виженер представил описание простого, но стойкого шифра перед комиссией Генриха III во Франции в 1586 году, и позднее изобретение шифра было присвоено именно ему. Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Первая успешная атака на шифр Виженера была проведена Фридрихом Касиски в 1863 году. Его метод оставался основным методом криптоанализа шифра Виженера вплоть до 1920 года, когда Уильям Фридман опубликовал монографию «Индекс совпадения и его применение в криптоанализе» (англ. «Index of Coincidence and Its Applications in Cryptography»). Новый метод, описанный Фридманом, предлагал более эффективный и устойчивый к ошибкам способ определения длины ключа. Метод индекса совпадений получил широкое применение. Позднее он стал использоваться в криптоанализе с помощью машин.

Общий случай

Рассмотрим текст, написанный на некотором языке. Алфавит данного языка будем полагать состоящим из m символов. Рассмотрим достаточно длинную строку  из n символов. Индексом совпадения называют вероятность совпадения двух произвольных символов в строке. Если fi — количество i-го символа алфавита в строке , то индекс совпадения вычисляется по формуле:

Открытый текст

Допустим, строка  является открытым текстом либо получена из него простой перестановкой. В этом случае индекс совпадений удобно выразить через вероятности появления i-го символа. Обозначим их pi. Тогда получим следующую формулу:

Т.к. величины pi имеют вполне определённые значения, то для открытого текста индекс совпадений не зависит от его содержания, а зависит только от языка, на котором написан текст. Более того, значения pi исследованы и известны, что позволяет рассчитать значения индекса совпадений открытого текста для различных языков (см. табл. 1):

Таблица 1

Случайная строка

Наконец, пусть   — случайная строка. Тогда вероятность появления каждого символа равна:

Используя формулу (2), получим:

Этой формулой можно пользоваться для оценки индекса совпадений полиалфавитного шифра. Для английского языка индекс совпадений полиалфавитного шифра составит 0,03846, для русского — 0,0303, для русского (без буквы “ё”) — 0,03125.

Значения индекса совпадений для открытого текста и для полиалфавитного шифра существенно различаются. Это позволяет, зная индекс совпадений, определить, получен ли текст из открытого простой перестановкой, или является полиалфавитным шифром.

Взаимный индекс совпадений

Взаимный индекс совпадений — ещё один важный метод криптоанализа шифра Виженера. Описание было так же опубликовано Уильямом Фридманом в 1920 году.

Общий случай

Рассмотрим две строки  и  с длинами n и n’ соответственно. Алфавит, как и прежде, состоит из m символов. Взаимным индексом совпадений этих строк называют вероятность того, что символ, случайно выбранный из первой строки, совпадёт со случайно выбранным символом второй строки. Пусть fi, gi — количество i-го символа алфавита в первой и второй строках соответственно. Тогда взаимный индекс совпадений будет равен:

Строки со сдвигом

Практически важным для метода индекса совпадений является частный случай, когда обе строки получены сдвигом алфавита открытого текста. Обозначим pi — вероятности появления i-го символа в строке , s — сдвиг алфавита строки   относительно алфавита строки  (влево). Тогда вероятности появления i-го символа алфавита в строке  равны pi+s (используется нумерация алфавита строки ). Для взаимного индекса совпадений получаем следующую формулу:

Заметим, что т.к. сдвиг циклический, то

и взаимный индекс совпадения s и m-s принимает одно и то же значение.

Ниже приведены значения взаимного индекса совпадений в зависимости от сдвига для русского и английского языков. Значения приведены для сдвигов от 0 до m/2 для русского языка (см. табл. 2) и для английского языка (см. табл. 3). Как упоминалось выше, на основе этих значений взаимный индекс совпадений может быть вычислен для любого сдвига.

Таблица 2

Таблица 3

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

Дешифрование шифра Цезаря

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

Взлом без знания шифра

Итак, взломщик знает (или предполагает), что использовался простой шифр подстановки (исходя из того, что ключ является некоторым целым числом, что сразу отсекает почти все неподстановочные шифры), но не знает, что это — схема Цезаря.

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

Взлом без знания ключа

Это наш основной рассматриваемый случай.

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

Действительно, дешифровать шифротекст можно простым полным перебором, ведь существует всего 33 значения сдвига для русского языка (26 для английского языка), так что метода грубой силы вполне достаточно.

Можно пойти и другим путём для взлома, если, например, процесс необходимо автоматизировать (избавиться от необходимости присутствия человека) — использовать частотный анализ и проверить частоты встречаемости букв. Изобразив диаграммой частоты встречания букв в зашифрованном тексте, и зная ожидаемое распределение букв для обычного текста на рассматриваемом языке, можно легко определить сдвиг, взглянув на смещение некоторых характерных черт на диаграмме.

Однако, стоит учитывать, что этот метод (как и любой другой метод дешифрования) работает тем лучше, чем больше длина шифротекста, и наоборот. То есть, чем короче данный для анализа текст, тем больше вероятность того, что частотный анализ выдаст ошибку.

Дешифрование шифра Виженера

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

• Сначала пытаются определить длину ключа. Длина ключа задаёт количество используемых алфавитов и период шифрования этими алфавитами. Поэтому на этом этапе исследуется периодичность шифротекста;

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

Алгоритм нахождения длины ключа

Разобьём текст x1x2…xn на столбцы размера t:

Если t кратно длине ключа, то каждые два элемента текста, отстоящие друг от друга на  позиций, a ∈ N, зашифрованы одним и тем же алфавитом. А это означает, что каждая строка в выписанной выше таблице получена из открытого текста перестановкой. Если же t не кратно длине ключа, то строки являются полиалфавитным шифром.

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

Алгоритм нахождения ключа

Предположим, мы определили длину ключа t. Найдём теперь сам ключ.

Вновь выпишем текст в столбцы размера t.

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

Поэтому применяется следующий алгоритм: вычисляется взаимный индекс совпадений для различных s, ищется значение s, при котором взаимный индекс совпадений максимален. Тогда начальный относительный сдвиг строк будет равен m-s (m — размер алфавита). Вычисляются относительные сдвиги между всеми парами строк. Т.к. сдвиги строк таблицы соответствуют сдвигам букв ключа, то остаётся перебрать m возможных ключей и выбрать из них наиболее правдоподобный.

Практическая часть

План работы

В самом начале, т.к. я уже определился с нужным оборудованием и языком программирования (PyCharm, Python 3.9), необходимо было разработать поэтапный план написания программы:

I. Внутренняя составляющая программы (логика, вычисления)

1. Реализация алгоритмов банального зашифровывания и расшифровывания для обоих шифров;
2. Реализация алгоритма криптоанализа и дешифрования для шифра Цезаря;
3. Реализация алгоритмов криптоанализа и дешифрования для шифра Виженера:

1. Реализация алгоритма частотного анализа,
2. Реализация алгоритма расчёта индекса совпадения,
3. Реализация алгоритма расчёта взаимного индекса совпадения,
4. Реализация алгоритма перебора индексов совпадения для дальнейшего нахождения длины ключа, используя пункт 3.2,
5. Реализация алгоритма нахождения предполагаемой длины ключа, используя пункт 3.4,
6. Реализация алгоритма расчёта ключа шифрования, используя пункты 3.1, 3.3, 3.4, 3.5;

4. Объединение структуры работы шифров в цельный рабочий алгоритм, способный универсально шифровать и дешифровать тексты для обоих шифров, а также переключаться между ними;
5. Вывод дополнительной информации (дебаг), а также проверка работоспособности алгоритмов и поиск ошибок (багов).

II. Программная оболочка программы (пользовательский графический интерфейс)

1. Создание основного окна, в котором будут располагаться все её элементы, и его настройка;
2. Добавление контекстных меню: главного (в верхней части окна, для конфигурации настроек программы и дополнительной информации) и инструментальных (при нажатии ПКМ на рабочих полях, для ускорения и упрощения работы с программой);
3. Разбиение главного окна на четыре контейнера, как на 4 основные рабочие области программы: «Исходный текст», «Преобразованный текст», «Функции и входные данные», «Параметры и дешифровка»;
4. Добавление в каждый контейнер нужных элементов интерфейса: в первые два — окон ввода и вывода, в третье — поля ввода ключа и кнопок для работы программы, в четвёртое — таблицы выбора языка, шифра и параметра дешифрования;
5. Подключение ко всем элементам соответствующих частей кода из логики программы;
6. Компиляция программы в виде рабочего исполнительного файла

Комментарии к написанию программного кода

Для всех своих нужд чистый язык Python 3.9 и стандартную кроссплатформенную графическую библиотеку Tkinter.

Я реализовывал шифры в виде классов, т.к. текст шифра сам по себе — данные довольно ёмкие: кроме самого текста для удобной работы они должны содержать и многие другие важные аспекты, такие как вид шифра, язык текста, алфавиты и статистическая информация для каждого из языков и многое другое, в том числе и чисто программные данные, необходимые для работы программы с этими шифрами.

Исходный программный код

Исходный код программы находится не в самом чистом состоянии, постольку поскольку в нём много комментариев и опций для дебага, помогающих читающему его понять, кроме того, ввиду зависящего от отступов от начала строки синтаксиса я не смогу выложить открытый исходный код здесь, поэтому приложу его двумя файлами (см. прил. 11, доступно только в цифровой версии данного документа):

• main.py — внутренняя составляющая программы (логика)

• app.py — внешняя оболочка программы (пользовательский графический интерфейс)

Внешний вид программы

Я сделал пару снимков экрана (скриншотов), запечатляющих программу в работе (см. прил. 12)

Инструкция к программе

1. Запуск исполнительного файла программы;
2. Предварительная конфигурация программы в меню настроек (по необходимости);
3. Выбор языка текста, над которым будет производится работа, в соответствующем списке в разделе параметров в правом нижнем углу окна приложения;
4. Выбор шифра, согласно которому нужно произвести работу над текстом, в соответствующем списке в разделе параметров в правом нижнем углу окна приложения;
5. Ввод исходного текста, над которым нужно произвести преобразование, в соответствующее поле в левом верхнем углу окна приложения;
6. Выбор нужной функции, далее действия разнятся в зависимости от функции:

• В случае использования функций шифрования (расшифрование и зашифрование) ввести нужный ключ в соответствующую строку в правом верхнем углу окна приложения, программа сама определит, правильный ли ключ для текущих выбранных параметров (язык, шифр) и если да, выведет преобразованный согласно данному ключу текст, а иначе выведет оригинальный текст (либо ничего не выведет),

• В ином случае использования функции дешифрования программа выведет необходимые для дешифровки данные, из которых нужно выбрать наиболее подходящие, в главный список в разделе параметров в правом нижнем углу окна приложения:

1) Если выбран шифр Цезаря, выведется полный перебор всех возможных вариантов расшифровки текста (т.е. перебор алфавита), в котором легко можно найти верный исходный текст, после этого переходим к пункту 3),

2) Если же выбран шифр Цезаря, программа проверит, пуста ли строка для ввода ключа:

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

б) Если в строке записано некоторое целое число, программа посчитает его предполагаемой длиной ключа, поэтому список параметров обновится, в него будут выведены предполагаемые ключи шифрования, после этого, если среди них есть похожий на осмысленный(ое) текст(слово), скорее всего это и есть ключ, нужно ввести его в строку ввода ключа, иначе нужно поочерёдно вводить каждый из данных ключей (перебирать), и перейти к пункту 3),

в) Наконец, если в строке написан какой-то текст, программа выведет параметры по умолчанию

3) После того, как нужный ключ (или нужное значение поворота) был(о) найден(о) из пункта 2), нужно ввести его в соответствующую строку в правом верхнем углу окна приложения, программа сама определит, правильный ли ключ для текущих выбранных параметров (язык, шифр) и если да, выведет преобразованный согласно данному ключу текст, а иначе выведет оригинальный текст (либо ничего не выведет);

7. Получение выведенного преобразованного текста в соответствующем поле в левом нижнем углу окна приложения;
8. Повторение с пункта 2 по необходимости (программа не является одноразовой, может использоваться неограниченное число раз подряд);
9. В конце работы или в случае критической ошибки (бага) выйти из приложения или закрыть его, посредством кнопки «Выход из приложения» в главном меню в верхней части окна приложения или нажатием красного крестика в самом правом верхнем углу окна приложения.

Заключение

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

Сопоставив полученные результаты работы программы с данными из различных источников, я пришел к выводу, что моя программа прекрасно справляется со своей задачей, позволяя точно расшифровать различные тексты и шифры, а также взламывать их. К тому же я составил несколько выводов о методах криптоанализе различных шифров: не всегда достаточно одного лишь правильного алгоритма для автоматической дешифровки шифров — это очень тонкий и трудоёмкий процесс, требующий внимательности со стороны пользователя; с увеличением длины текста увеличиваются шансы верно произвести его дешифровку; на процесс дешифровки и шифрования влияет лишь сам текст, а никак не посторонние символы (цифры, знаки препинания, пробелы и т.п.); взломать шифр Цезаря проще простого, а вот верно дешифровать шифр Виженера можно далеко не всегда, несмотря на все старания.

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

Список литературы

1. Л. Л. Босова, Информатика: Базовый уровень 10-11 класс;
2. Эла Свейгарт, Криптография и взлом шифров на Python;
3. В. М. Фомичёв, Методы дискретной математики в криптологии;
4. С.Панасенко, Алгоритмы шифрования. Специальный справочник;
5. Википедия:
6. Шифр, Криптография, История криптографии, Криптоанализ, Шифр Цезаря, Шифр Виженера, Принцип Керкгоффса, Частотный анализ, Индекс совпадений;
7. НОУ ИНТУИТ | Криптографические методы защиты информации | Классические шифры: Теория криптоанализа Шифра Виженера

Приложения

Приложение 1

Приложение 2

Приложение 3

Приложение 4

Приложение 5

Приложение 6

Приложение 7

Приложение 8

Приложение 9

Приложение 10

Приложение 11

,

Приложение 12