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

Введение

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

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

Благодаря работе Абу  аль - Кинди оказалось, что шифры типа «Шифра Цезаря» (то есть моноалфавитные шифры, в которых каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква) довольно-таки легко поддаются частотному криптоанализу. Возникла потребность в разработке таких шифров, ручная расшифровка которых может потребовать очень значительных усилий. И на смену моноалфавитным шифрам пришли полиалфавитные шифры. Абу аль - Кинди первым предложил использовать многоалфавитный шифр. В европейских странах это произошло в эпоху Возрождения, когда развитие торговли потребовало надежные способы защиты информации. Одним из первых предложил полиалфавитный шифр итальянский архитектор Батисте Альберти. Впоследствии данный шифр получил имя дипломата 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 История

Первое точное документированное  описание многоалфавитного шифра было сформулировано Леоном Баттиста Альберти <#"justify">.2 Описание

В шифре Цезаря <#"justify">ATTACKATDAWN

Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его  длина не будет соответствовать  длине исходного текста:

Первый символ исходного  текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста

шифруется подобным способом.

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

Ключ:LEMONLEMONLE

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

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

Если буквы A-Z соответствуют  числам 0-25, то шифрование Виженера можно записать в виде формулы:

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

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

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

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

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

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

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

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

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

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

В 1863 году Фридрих  Касиски был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя Чарльз Беббидж <#"justify">Ключ:ABCDEF AB CDEFA BCD EFABCDEFABCD

Исходныйтекст:CRYPTO IS SHORT FOR CRYPTOGRAPHY

Шифрованныйтекст: CSASXT IT UKSWT GQU GWYQVRKWAQJB

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

Ключ:ABCDAB CD ABCDA BCD ABCDABCDABCDИсходный текст:CRYPTO IS SHORT FOR CRYPTOGRAPHYШифрованный текст:CSASTP KV SIQUT GQU CSASTPIUAQJB

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

Шифрованный текст:

Расстояние между  повторяющимися DYDUXRMH равно 18, это позволяет  сделать вывод, что длина ключа  равна одному из значений: 18, 9, 6, 3 или 2. Расстояние между повторяющимися NQD равно 20. Из этого следует, что длина ключа равна 20 или 10, или 5, или 4 или 2. Сравнивая возможные длины ключей, можно сделать вывод, что длина ключа (почти наверняка) равна 2.

.3.2 Тест Фридмана

Тест Фридмана (иногда называемый каппа-тест) был изобретен  Вильямом Фридманом в 1920 году. Фридман  использовал индекс совпадени <#"justify">

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

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

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

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

.5 Варианты

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

Виженер фактически изобрел более стойкий шифр - шифр <#"justify">.6 Экспериментальная проверка работы программы

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

После шифрования был  получен следующий зашифрованный  текст:

«СРМДЕЦУТЖКЕ»

Для проверки работы программы дешифрования по таблице  Виженера возьмем этот же зашифрованный текст «СРМДЕЦУТЖКЕ». При этом ключевым символом должно являться слово «два». При расшифровке текста получим первоначальный текст «приветствие».

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

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

Заключение

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

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

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

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

1.А.В. Яковлев,  А.А. Безбогов, В.В. Родин, В.Н. Шамкин. Криптографическая защита информации. - Тамбов: Издательство ТГТУ, 2006

2.David, Kahn. On the Origin of a Species. The Codebreakers: The Story of Secret Writing. Simon & Schuster, 1999

3.Henk C.A. van Tilborg, ed. Encyclopedia of Cryptography and Security (First ed.). Springer. pp. 115, 2005

4.Э. М. Габидулин. Курс лекций по Защите Информации. - Москва: Издательство МФТИ, 2007

.А. П. Алферов,  А. Ю. Зубов, А. С. Кузьмин,  А. В. Черемушкин. Основы криптографии. - Москва: Издательство Гелиос АРВ, 2005 
 
Читать полностью:http://www.km.ru/referats/333100-vysokourovnevye-metody-informatiki-i-programmirovaniya