Высокоуровневые методы информатики и программирования

Высокоуровневые методы информатики и программирования

Содержание

Введение

. Полиалфавитные шифры

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

.1 История

.2 Описание

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

.3.1 Метод Касиски

2.3.2 Тест Фридмана

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

.5 Варианты

.6 Экспериментальная проверка работы программы

. Взлом полиалфавитных шифров

Заключение

Список использованной литературы

Приложения

Приложение А. Шифр Виженера

Приложение Б. Скриншоты программы

Приложение В. Квадрат Виженера (tabula recta)

Введение

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

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

Благодаря работе Абу аль - Кинди оказалось, что шифры типа «Шифра Цезаря» (то есть моноалфавитные шифры, в которых каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква) довольно-таки легко поддаются частотному криптоанализу. Возникла потребность в разработке таких шифров, ручная расшифровка которых может потребовать очень значительных усилий. И на смену моноалфавитным шифрам пришли полиалфавитные шифры. Абу аль - Кинди первым предложил использовать многоалфавитный шифр. В европейских странах это произошло в эпоху Возрождения, когда развитие торговли потребовало надежные способы защиты информации. Одним из первых предложил полиалфавитный шифр итальянский архитектор Батисте Альберти. Впоследствии данный шифр получил имя дипломата XVI века Блеза де Виженера. Также вклад в развитие полиалфавитных шифров внес немецкий аббат XVI века Иоганн Трисемус. Простым, но стойким способом полиалфавитной замены является шифр Плейфера, открытый в начале XIX века Чарльзом Уитстоном.

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

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

1.  Полиалфавитные шифры

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

Суть полиалфавитного шифра заключается в циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Например, пусть у нас имеется некоторое сообщение x1 , x2 , x3 , ….. xn , …… x2n , ….., которое надо зашифровать. При использовании полиалфавитного шифра имеется несколько моноалфавитных шифров (например, n штук). И в нашем случае к первой букве применяется первый моноалфавитный шифр, ко второй букве - второй, к третьей - третий….. к n-ой букве - n-й, а к n+1 опять первый, ну и так далее. Таким образом, получаётся довольно-таки сложная последовательность, которую уже не так просто вскрыть, как один моноалфавитный шифр. Самым важным эффектом, достигаемым при использовании полиалфавитного шифра, является маскировка частот появления тех или иных букв в тексте, на основании которой обычно очень легко вскрываются моноалфавитные шифры.

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

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

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

.1 История

Первое точное документированное описание многоалфавитного шифра было сформулировано  Леоном Баттиста Альберти <#"564538.files/image001.gif">

Расшифровка:

Допустим, что нам надо зашифровать некий текст, первым словом которого является слово DANCE. Зашифруем первые две буквы, а все остальные делаются аналогично. В графе «ключ» многократно повторяем слово ABC, в графе «открытый текст» приводим открытый текст, в графе «шифрованный текст» приводим зашифрованный текст:

Берём первую букву и смотрим, какая буква ключа находится над ней, а затем полученную букву ключа находим в первом столбце квадрата Виженера, а шифруемую букву в первой строке, затем смотрим, какая буква находится на пересечении полученной строки и столбца - она и будет зашифрованной буквой:

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

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

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

1.       Поиск длины ключа. Можно анализировать распределение частот в зашифрованном тексте с различным прореживанием. То есть брать текст, включающий каждую 2-ю букву зашифрованного текста, потом каждую 3-ю и т. д. Как только распределение частот букв будет сильно отличаться от равномерного (например, по энтропии), то можно говорить о найденной длине ключа.

2.      Криптоанализ. Совокупность l-шифров Цезаря (где l - найденная длина ключа), которые по отдельности легко взламываются.

Тесты Фридмана и Касиски могут помочь определить длину ключа.

.3.1Метод Касиски

В 1863 году Фридрих Касиски был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя  Чарльз Беббидж <#"564538.files/image006.gif">

Из наблюдения за частотой совпадения следует:

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

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

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

.5 Варианты

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

Виженер фактически изобрел более стойкий шифр -  шифр  <#"564538.files/image008.gif">

Приложение В

Квадрат Виженера (tabula recta)