Егоров УОП

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

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

1.2 История появления и первые упоминания о шифре

Шифр Виженера является методом полиалфавитного шифрования сообщений, использующий скрытый ключ. Под шифром Виженера понимается шифр гаммирования[14] с использованием периодической гаммы малого периода. Шифр был описан Джовани Баттиста Беллазо, в 1553 году. Однако первые упоминания о шифре были зафиксированы гораздо раньше. В 1518 году Тритемий продвигает новую идею, представляющую из себя многоалфавитные замены, с использованием специальной таблицы, состоящей из символов некоторого алфавита. В шифре Тритемия не используются ключи, сам способ шифрования текста является секретом. Позже в шифре Виженера за основу будет взята похожая таблица, которая будет состоять из нескольких алфавитов.

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

Джовани Батиста Порта предложил отказаться от алфавитного порядка следования букв в первой строке таблицы Тритемия и расположить все символы в произвольном порядке. Это значительно усложнило бы попытки взломать шифр. В 1466 году Леон Альберти представил трактат, в котором он рассматривал способы скрытия сообщения. Результатом работы Леона Альберти, в 1466 году, стал его собственный многоалфавитный шифр, который задействовал несколько замен, использующих для каждого символа исходного текста соответствующие символы ключа. В 1585 году французский дипломат в Риме Блез де Виженер, который изучал труды Тритемия, Белазо, Кардано,

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

Шифр Виженера являлся исключительно стойким к взлому, в следствии чего Чарльз Лютвидж Доджсон назвал его не взламываемым, в статье «The

Alphabet Cipher», которая была опубликована в 1868 году, а в 1917 году

Scientific American также отозвался о шифре Виженера как о шифре, который не поддается взлому.

1.3Принципы работы криптосистемы

Вшифре Цезаря символ алфавита сдвигается на несколько позиций, а

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

При шифровании открытого текста используется специальная таблица,

похожая на таблицу Тритемия, которая изображена на рисунке 1. Иначе говоря,

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

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

зависящие от ключа. Ключом будет являться упорядоченная последовательность символов вида β1,β2,…,βn. Исходный текст будет представлен упорядоченной последовательностью α1,α2,…,αn. Тогда βi

определяет символы ключа, соответствующие символам сообщения αi, при i=1,..,n.

При шифровании сообщения символами латинского алфавита,

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

SAYXXRYXCVPWYYYLSSDZGQILOV

Рисунок 1 - Таблица Виженера

Первый символ нашего текста I будет зашифрован символом ключа K.

Тогда S-это первый символ, который будет находиться на пересечении строки содержащей K и столбца содержащего I в таблице. Так второму символу шифруемого текста W, будет соответствовать второй символ нашего ключа E.

Подобные замены символов исходного текста выполняются до тех пор, пока все символы не будут заменены на соответствующие им символы из таблицы.

Для алфавита, состоящего из 26 символов (Латинского алфавита),

реализация шифра будет выглядеть следующим образом:

Шифруемый текст: IWANTTOTELLYOUABOUTVIGENER

Ключ: KEY

Зашифрованный текст: SAYXXRYXCVPWYYYLSSDZGQILOV

Пусть n - это число символов в алфавите, αi - символы исходного текста, βi - это символы нашего ключа, ci реализация криптосистемы будет выглядеть

следующим образом:

ci = (αi + βi) mod n

И расшифровывание: αi = (ci+ n - βi) mod n

Эта операция реализуема путем сложения индексов соответствущих символов ASCII.

1.4 Область применения алгоритма шифрования

В XIX веке шифр Виженера, в силу своей простоты реализации,

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

1.5 Модификации шифра Виженера

Шифр Виженера является одной из самых известных криптосистем,

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

a. Шифр Бофора

Шифр Бофора (Бьюфорта) назван именем адмирала Френсиса Бофора,

который был изобретателем шкалы для определения скорости ветра. Шифр Бофора представляет из себя шифр Виженера, за одним исключением. В шифре Бофора строки квадрата Виженера записаны в обратном порядке. На рисунке 2

представлен Квадрат Бофора, использующийся при шифровании текста.

Рисунок 2 - Квадрат Бофора

b. Шифр Бегущего ключа

После взлома шифра Виженера многие работали над его улучшением.

Одним из главных недостатков шифра Виженера является повторение ключа.

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

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

Исходный текст: BEINGYOURSLAVEWHATSHOULDIDOBUTTEND

Ключ: WESTMINSTER

Дополнительный ключ: WESTMINSTERBEINGYOURSLAVEWHATSHOUL

Алгоритм шифрования такой же, как и при Виженере.

При расшифровке ключ используется для первых n символов, а результат ис-

пользуется для расшифровки остальных n символов. c. Шифр Гронсфельда

Граф Гронсфельд создал похожую на шифр Виженера криптосистему, ко-

торая использовала всего 10 алфавитов вместо 26 в латинском алфавите. Пре-

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

ния схож с алгоритмом шифрования Виженера. Точно так же составляется таб-

лица, содержащая алфавиты, при этом строки пронумерованы от 0 до 9 и для символов каждой строки применяется сдвиг, каждая n-ая строка содержит ал-

фавит n-1-ой строки со сдвигом на k позиций. Такой шифр был широко известен в Европе. На рисунке 3 показана таблица Гронсфельда.

Рисунок 3 - Таблица Гронсфельда

d. Шифр Вернама

В шифре Вернама используется логическая операция “исключающее

или”.

Свойства ключа:

1.Ключ совпадает по размеру со строкой

2.Ключ уникален

3.Каждый бит ключа имеет равномерное распределение

Ключ и строку складывают побитово при помощи “исключающего или”. При дешифровании строку вновь складывают с ключом при по-

мощи логической операции “исключающего или”

1.6Вывод к главе 1

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

2 Криптоанализ шифров Виженера и Бофора

Над доказательством небезопасности шифра Виженера работало не мало криптоаналитиков, но ответ получили только трое из них.

2.1 Критическая оценка криптостойкости алгоритмов

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

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

употребляются в письменной и устной речи с различной частотой. Например,

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

Кинди. В 1863 году Фридрих Касиски публикует результаты своей работы, в

которой он применил метод частотного анализа к зашифрованному тексту. В

этой работе он описал алгоритм взлома шифра Виженера и показал, что данная криптосистема не безопасна. Однако в 1854 году Чарльз Бэббидж Совершил это же открытие, но публиковать свою работу он не стал. В 1920 году У. Фридман опубликовал результаты своих исследований, направленных на обнаружение исходного текста из шифротекста, зашифрованного алгоритмом Виженера.

Фридман ввел новую величину, которая называется “Индексом совпадений”. С

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

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

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

слова k = 2, иначе наш шифр будет являться Сдвигом Цезаря.

Пусть I - конечный алфавит

Индекс совпадения будет выражаться следующей формулой:

fi - частота появления i-того символа в тексте J = i1,i2,…,iN m - мощность алфавита

Мы предполагаем, что длина ключа равна n, при n = 2.

Индекс совпадения для двух букв русского алфавита равен 0.0552 (ИС = 0.0552) для латинского ИС = от 0.062 до 0.067

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

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

раз, а длина текста N = 402, тогда используя формулу нахождения ИС = 17*16/402/401 = 0.00169, далее находим индекс совпадений для всех символов алфавита и складываем их. Если ΣИСi ≥ 0.0552 для русского, то длина ключа была найдена верно. Иначе продолжаем искать длину ключа.

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

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

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

Дешифруем наш шифротекст.

Таким образом, для нахождения длины ключа необходим рассмотреть

вероятность появления всех символов в тексте.

2.2 Практическое применение алгоритмов Виженера и Бофора в настоя-

щее время

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

2.3 Вывод к главе 2

Вданной главе была сделана оценка криптостойкости шифра Виженера,

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

3 Практическое задание

3.1Высокоуровневый язык программирования Python

Вданной практической работе, я использовал язык с динамической системой типов Python, который был создан Гвидо ван Россумом в 1980 году.

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