Шифр Виженера () — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.
Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джованни Баттиста Беллазо в книге La cifra del. Sig. Giovan Battista Bellaso в 1553 году, однако в XIX веке получил имя Блеза Виженера, французского дипломата. Метод прост для понимания и реализации, но является недоступным для простых методов криптоанализа.
Хотя шифр легко понять и реализовать, на протяжении трёх столетий он противостоял всем попыткам его взломать, благодаря чему его называли «неразгаданным шифром» (). Многие люди пытались реализовать схемы шифрования, которые по сути являлись шифрами Виженера.
История
В 1466 году Леон Альберти, знаменитый архитектор и философ представил трактат о шифрах в папскую канцелярию. В трактате рассматриваются различные способы шифрования, в том числе маскировка открытого текста в некотором вспомогательном тексте. Работа завершается собственным шифром, который он назвал «шифр, достойный королей». Это был многоалфавитный шифр, реализованный в виде шифровального диска. В данном шифре используется несколько замен в соответствии с ключом. Позднее Альберти изобрёл код с перешифровкой. Данное изобретение значительно опередило своё время, поскольку данный тип шифра стал применяться в странах Европы лишь 400 лет спустя.
В 1518 году в развитии криптографии был сделан новый шаг благодаря появлению в Германии первой печатной книги по криптографии. Аббат Иоганн Тритемий, настоятель монастыря в Вюрцбурге, написал книгу «Полиграфия», в которой даётся описание ряда шифров. Один из них использует «таблицу Тритемия» (ныне «таблицу Виженера») и развивает идею многоалфавитной замены. Система шифрования следующая: первая буква исходного текста шифруется по первой строке, вторая по второй и так далее. После использования последней строки следующая буква вновь шифруется по первой строке. В шифре Тритемия отсутствует ключ, секретом является сам способ шифрования.
Следующий шаг в развитии предложенного Тритемием способа шифрования был сделан итальянцем Джовани Белазо. В 1553 году вышла его брошюра «Шифр синьора Белазо». В этом шифре ключом является так называемый пароль — фраза или слово. Пароль записывался периодически над буквами открытого текста. Буква пароля, стоящая над соответствующей буквой открытого текста, указывала номер строки в таблице Тритемия, по которой следует проводить замену (шифрование) этой буквы.
В последующем идеи Тритемия и Белазо развил соотечественник Белазо Джованни Батиста Порта. Он предложил отказаться от алфавитного порядка следования букв в первой строке таблицы Тритемия и заменить этот порядок на некоторый произвольный, являющийся ключом шифра. Строки таблицы по-прежнему циклически сдвигались. В книге «О тайной переписке», которая вышла в 1563 году, Порта предложил биграммный шифр, а также привёл описание механического дискового устройства, реализующего биграммную замену.
В середине XVI века в Италии появляется книга Дж. Кардано «О тонкостях» с дополнением «О разных вещах». Там нашли отражение новые идеи криптографии: использование части самого передаваемого открытого текста в качестве ключа шифра (идея «самоключа») и новый способ шифрования, который вошёл в историю как «решётка Кардано».
Посол Франции в Риме Блез де Виженер, познакомившись с трудами Тритемия, Белазо, Кардано, Порта, Альберти, также увлёкся криптографией. В 1585 году он написал «Трактат о шифрах» об основах криптографии. В этом труде он замечает: «Все вещи в мире представляют собой шифр. Вся природа является просто шифром и секретным письмом». Эту мысль в XVII веке повторил один из основоположников теории вероятностей Блез Паскаль, а в XX веке — «отец кибернетики» Норберт Винер.
По сути Виженер объединил подходы Тритемия, Беллазо, Порта к шифрованию открытых текстов, не внеся в них ничего оригинального по существу. В наше время «шифр Виженера», состоящий в периодическом продолжении ключевого слова по таблице Тритемия, вытеснил имена его предшественников. Дэвид Кан в своей книге «Взломщики кодов» отозвался об этом осуждающе, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания».
Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Известный писатель и математик Чарльз Лютвидж Доджсон (Льюис Кэрролл) назвал шифр Виженера невзламываемым в статье «Алфавитный шифр» (), опубликованной в детском журнале в 1868 году. В 1917 году Scientific American также отозвался о шифре Виженера как о не поддающемся взлому. Это представление было опровергнуто после того, как Касиски полностью взломал шифр в XIX веке, хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками ещё в XVI веке.
Шифр Виженера достаточно прост для использования в полевых условиях, особенно если применяются шифровальные диски. Например, «конфедераты» использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Во время войны командование Конфедерации полагалось на три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и — так как война подходила к концу — «Come Retribution».
Гилберт Вернам попытался улучшить взломанный шифр (он получил название шифр Вернама-Виженера в 1918 году), но, несмотря на усовершенствования, шифр остался уязвимым для криптоанализа. Но работа Вернама всё же привела к получению шифра Вернама, который действительно невозможно взломать.
Описание
В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций. Например, в шифре Цезаря при сдвиге +3, A становится D, B становится E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Предположим, что исходный текст имеет вид:
ATTACKATDAWN
Человек, посылающий сообщение, циклически записывает ключевое слово («LEMON»), пока его длина не будет соответствовать длине исходного текста:
LEMONLEMONLE
Первый символ исходного текста («A») зашифрован последовательностью L, которая является первым символом ключа. Первый символ зашифрованного текста («L») находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ зашифрованного текста («X») получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Исходный текст: ATTACKATDAWN Ключ: LEMONLEMONLE Зашифрованный текст: LXFOPVEFRNHR
Расшифровывание производится следующим образом: находим в таблице Виженера строку, соответствующую первому символу ключевого слова; в данной строке находим первый символ зашифрованного текста. Столбец, в котором находится данный символ, соответствует первому символу исходного текста. Следующие символы зашифрованного текста расшифровываются подобным образом.
Если — количество букв в алфавите, — номер буквы открытого текста, — номер буквы ключа в алфавите, то шифрование Виженера можно записать следующим образом:
И расшифровывание:
В компьютере такая операция соответствует сложению кодов ASCII символов сообщения и ключа по некоторому модулю. Кажется, что если таблица будет более сложной, чем циклическое смещение строк, то шифр станет надёжнее. Это действительно так, если её менять чаще, например, от слова к слову. Но составление таких таблиц, представляющих собой латинские квадраты, где любая буква встречается в строке или столбце один раз, трудоёмко и его стоит делать лишь на ЭВМ. Для ручного же многоалфавитного шифра полагаются лишь на длину и сложность ключа, используя приведённую таблицу, которую можно не держать в тайне, а это упрощает шифрование и расшифровывание.
Применение В XIX веке большое распространение получил так называемый метод блокнотного шифрования. Им пользовались революционеры-народники, шпионы и т. п. Шифр использует фразы, взятые из языка, как ключ шифрования. Например, фраза: «14 июля — Mary’s birthday». Если использовать принятую для примеров нумерацию букв английского алфавита, то Marysbirthday означает . Для шифровки фразы Iamgoing ↔ производится сложение mod26 текста с ключом, в роли которого выступает записанная фраза. Получается
↔ U A D E G J V X.
Как видно, в данном случае это обыкновенное гаммирование. Виженер предложил использовать ключ такого типа и в тех случаях, когда текст длиннее ключа, накладывая его столько раз, сколько нужно. При этом необязательно, чтобы ключ получался из осмысленной фразы. Более того, это даже нежелательно, так как осмысленность может помочь взломщику шифра. Возьмём, например, текст:
A SMOKE OF MOTHERLAND IS SWEET FOR US AND PLEASANT ↔ и ключ: .
Шифровка получается гаммированием mod26: Pt: Key: Ct: Pt: Key: Ct:
Таким образом, шифр Виженера получается как повторяющаяся комбинация сдвигов. В общем случае этот шифр не сохраняет частотность встречающихся букв и по этой причине не может быть раскрыт методом статистического анализа.
Шифр Виженера был популярен не только среди европейцев: в 1860-х гг. им активно пользовались обе стороны Гражданской войны в США. Вместо таблиц у них были специальные медные диски, но принцип работы остался прежним.
Криптоанализ
Шифр Виженера «размывает» характеристики частотностей появления символов в тексте, но некоторые особенности появления символов в тексте остаются. Главный недостаток шифра Виженера состоит в том, что его ключ повторяется. Поэтому простой криптоанализ шифра может быть построен в два этапа: Поиск длины ключа. Можно анализировать распределение частотностей в зашифрованном тексте с различным прореживанием. То есть брать текст, включающий каждую 2-ю букву зашифрованного текста, потом каждую 3-ю и т. д. Как только распределение частотностей букв будет сильно отличаться от равномерного (например, по энтропии), то можно говорить о найденной длине ключа. Криптоанализ. Совокупность l шифров Цезаря (где l — найденная длина ключа), которые по отдельности легко взламываются. Тесты Фридмана и Касиски могут помочь определить длину ключа.
Тест Касиски и определение с его помощью длины ключа
Чарльз Беббидж был первым, кто разработал алгоритм атаки на шифр Виженера в 1854 году. Стимулом к разработке алгоритма послужил обмен письмами с Джоном Х. Б. Твейтсом. Он заявил, что создал новый шифр, и отправил его в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Твейтса является лишь частным случаем шифра Виженера, Твейтс предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily — именем жены поэта. Но он не опубликовал своё открытие. Поэтому данный алгоритм назван в честь Фридриха Вильгельма Касиски, офицера прусской армии, который независимо от Беббиджа разработал такой же алгоритм в 1863 году. И только в XX веке, когда учёные исследовали заметки Беббиджа, появилась информация о первом изобретателе этого алгоритма.
Вначале определим понятие индекса совпадения данного текста. Пусть рассматривается текст , соответствующий алфавиту, состоящему из букв. Пусть — длина этого текста. Обозначим через число вхождений буквы с номером в текст . Тогда индекс совпадения текста определяется как
.