Шифрование методом Виженера

КАМЧАТСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

Факультет заочный

 

Кафедра информационных технологий

 

 

 

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Информационная безопасность»

Тема: Шифрование методом Виженера

 

 

 

 

Выполнила: студентка       Проверил: К.т.н,

гр. 08 ПИ, шифр 080210      профессор

Гоняева Е.С.         Проценко И.Г

 

Дата сдачи: _____________      Дата проверки: ________

Подпись: _______________      Подпись: _____________

 

 

 

 

 

 

 

 

Петропавловск-Камчатский, 2013

Метод Виженера

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

История его появления такова: первое точное документированное описание многоалфавитного шифра было сформулированно Леоном Баттиста Альберти в 1467 году, для переключения между алфавитами использовался металлический шифровальный диск. Система Альберти переключает алфавиты после нескольких зашифрованных слов. Позднее, в 1518 году, Иоганн Трисемус в своей работе «Полиграфия» изобрел tabula recta -- центральный компонент шифра Виженера.

То, что сейчас известно под шифром Виженера, впервые описал Джованни Батиста Беллазо в своей книге La cifra del. Sig. Giovan Battista Bellasо. Он использовал идею tabula recta Трисемуса, но добавил ключ для переключения алфавитов шифра через каждую букву. Блез Виженер представил своё описание простого, но стойкого шифра перед комиссией Генриха III во Франции в 1586 году, и позднее изобретение шифра было присвоено именно ему. Давид Кан в своей книге «Взломщики кодов» отозвался об этом осуждающе, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания».

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

Шифр Виженера достаточно прост для использования в  полевых условиях, особенно если применяются  шифровальные диски. Например, «конфедераты»  использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Во время войны командование Конфедерации полагалось на три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и -- так как война подходила к концу -- «Come Retribution».

Гилберт Вернам попытался  улучшить взломанный шифр (он получил  название шифр Вернама-Виженера в 1918 году), но, несмотря на его усовершенствования, шифр так и остался уязвимым к криптоанализу. Однако работа Вернама в конечном итоге всё же привела к получению шифра, который по-настоящему трудно взломать.

Описание

Квадрат Виженера, или  таблица Виженера, также известная  как tabula recta, может быть использована для шифрования и расшифрования. В шифре Цезаря каждая буква алфавита сдвигается на несколько строк; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На разных этапах кодировки шифр Виженера использует различные алфавиты из этой таблицы. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова.

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

1) символы исходного алфавита нумеруются, начиная с нуля, например:

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ь	Ы	Э	Ю	Я
15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30

Получают таблицу соответствия;

2) задаются ключом кодирования – словом в исходном алфавите, например, АСУ;

3) выписывают сообщение, подлежащее кодированию, например, пусть это будет сообщение ИНФОРМАТИКА, и выполняют следующие шаги:

а) под каждым его символом записывают порядковый номер из таблицы соответствия:

И  Н  Ф  О  Р  М  А  Т  И  К А

8  13 20 14 16 12  0  18 8   10  0

б) под сообщением выписывают ключевое слово, а под символами ключа выписывают их порядковые номера из таблицы соответствия:

А  С  У  А  С  У  А  С  У  А С

0  17 19   0 17 19  0  17 19 0 17

в) порядковые номера символов складываются по модулю, равному числу символов исходного алфавита (в нашем случае – 31):

8  30  8  14  2  1  0  4  27 10 17

Напомним, что сложение по модулю (обозначается ⊕) выполняется без переноса единицы переноса в старший разряд. Так мы получили при сложении по модулю 31, например, чисел 17 и 16 (сумма равна 33, что на 2 превышает модуль 31) значение 2;

4) полученный числовой ряд преобразуется в символы исходного алфавита по таблице соответствия. Так имеем:

И  Я И  О  В  Б  А  Д Ы К С.

Очевидно, что статистика не поможет декодировать это сообщение, поскольку повторяются совсем не те символы, что в исходном сообщении.

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

Чтобы декодировать сообщение И Я И О В Б А Д Ы К С, задавшись ключом АСУ и зная таблицу соответствия.

Решение:

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

И  Я  И  О  В  Б  А  Д Ы К С

8  30   8  14  2  1  0   4 27  10 17

б) выписываем под сообщением ключ с порядковыми номерами символов:

А  С  У   А  С  У  А С  У А  С                

0  16 18   0 16 18  0 16 18 0  16                

в) вычитаем с учетом модуля 31 из чисел в закодированном сообщении числа для ключа:

8  12 19 13 15 11  0 17  8  9   0        

г) преобразуем числа в символы по таблице соответствия:

И Н  Ф  О  Р  М  А Т  И  К  А        

При декодировании возникла сложность в получении кодов символов Т, Ф, Р. В самом деле, при вычитании из 2 числа 16 получалось –14. Тогда к 2 прибавили модуль 31, получили 33 и уже из 33 вычли 16. Получили 17 – порядковый номер символа Т. Аналогично поступили и с символами Ф и Р.

В шифре Цезаря каждая буква алфавита сдвигается на несколько строк; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря.

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

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

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

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

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

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

В 1863 году Фридрих Касиски  был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя Чарльз Беббидж разработал этот алгоритм уже в 1854 году. В то время когда  Беббидж занимался взломом шифра  Виженера, John Hall Brock Thwaites представил новый шифр в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Thwaites'а является лишь частным случаем шифра Виженера, Thwaites предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily -- именем жены поэта.

Тест Касиски опирается  на то, что некоторые слова, такие  как «the» могут быть зашифрованы  одинаковыми символами, что приводит к повторению групп символов в зашифрованном тексте. Например: сообщение, зашифрованное ключом ABCDEF , не всегда одинаково зашифрует слово «crypto»:

Ключ: 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

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

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

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

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

Тест Фридмана (иногда называемый каппа-тест) был изобретен  Вильямом Фридманом в 1920 году. Фридман  использовал индекс совпадения, который  измеряет частоты повторения символов, чтобы взломать шифр. Зная вероятность к_р того, что два случайно выбранных символа текста совпадают (примерно 0,067 для англ. языка) и вероятность совпадения двух случайно выбранных символов алфавита к_r(примерно 0,0385 для англ. языка), можно оценить длину ключа как:

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

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

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

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