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

Блез Виженер

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

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

История

Репродукция шифровального диска Конфедерации

В 1466 году Леон Альберти, знаменитый архитектор и философ представил трактат о шифрах в папскую канцелярию. В трактате рассматриваются различные способы шифрования, в том числе маскировка открытого текста в некотором вспомогательном тексте. Работа завершается собственным шифром, который он назвал «шифр, достойный королей». Это был многоалфавитный шифр, реализованный в виде шифровального диска. Суть заключается в том, что в данном шифре используется несколько замен в соответствии с ключом. Позднее Альберти изобрел код с перешифровкой. Данное изобретение значительно опередило свое время, поскольку данный тип шифра стал применяться в странах  Европы лишь 400 лет спустя.

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

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

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

В середине XVI века в Италии появляется книга Дж. Кардано "О тонкостях" с дополнением "О разных вещах". Там нашли отражение новые идеи криптографии: использование части самого передаваемого открытого текста в качестве ключа шифра (идея "самоключа") и новый способ шифрования, который вошел в историю как "решетка Кардано".

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

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

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

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

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

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

Описание

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

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

ATTACKATDAWN

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

LEMONLEMONLE

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

Исходный текст:             ATTACKATDAWN
Ключ:                               LEMONLEMONLE
Зашифрованный текст:  LXFOPVEFRNHR

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

Если $n$ - количество букв в алфавите, $m_{j}$ - буквы открытого текста, $k_{j}$ - буквы ключа, т шифрование Виженера можно записать следующим образом:

$c_{j}=m_{j}+k_{j}{\pmod {n}}$

И расшифровывание:

$m_{j}=c_{j}-k_{j}{\pmod {n}}$

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

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

Шифр Виженера «размывает» характеристики частот появления символов в тексте.

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

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

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

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

Чарльз Беббидж был первым, кто разработал алгоритм атаки на шифр Виженера в 1854 году. Стимулом к разработке алгоритма послужил обмен письмами с Джоном Х. Б. Твейтсом. Он заявил, что создал новый шифр, и отправил его в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Твейтса является лишь частным случаем шифра Виженера, Твейтс предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily — именем жены поэта. Но он не опубликовал свое открытие. Поэтому данный алгоритм назван в честь Фридриха Вильгельма Касиски, офицера прусской армии, который независимо от Беббиджа разработал такой же алгоритм в 1863 году. И только в 20 веке, когда ученые исследовали заметки Беббиджа, появилась информация о первом изобретателе этого алгоритма.

Идея этого метода основана на периодичности потока ключей. Кроме того, в естественном языке существуют часто встречаемые буквосочетания: биграммы и триграммы. Учитывая это, возникает надежда, что повторяющиеся наборы символов в шифротексте — след повторений популярных биграмм и триграмм открытого текста. Расстояние между повторениями в таком случае должно быть кратно длине лозунга. Слодовательно, вычислив наибольший общий делитель всех таких расстояний, мы получим рабочую гипотезу о длине ключа.

В качестве примера рассмотрим следующую криптограмму:

UTPDHUG NYH USVKCG MVCE FXL KQIB. WX RKU GI TZN,
RLS BHZLXMSNP KDKS; СЕВ IH HKEWIBA, YYM SRB PER
SBS, JV UPL О UVADGR HRRWXF. JV ZTVOOV УН ZCQU У
UKWGEB, PL UQFB Р FOUKCG, TBF RQ VHCF R KPG, 0U
КЕТ ZCQU MAW QKKW ZGSY, ЕР PGM QKETK UQEB DER EZRN,
MCYE, MG UCTESVA, WP KFT ZCQU MAW KOIJS, LCOV                                                                                                        NTHDNV JPNUJVB IH GGV RWX ONKCGTHKFL XG VKD, ZJM
VG CCI MVGD JPNUJ, RLS EWVKJT ASGUCS MVGD; DDK
VG NYH PWUV CCHIIY RD DBQN RWTH PFRWBBI VTTK
VCGNTGSF FL IAWU XJDUS, HFP VHSF, RR LAWEY QDFS
RVMEES FZB СНН JRTT MVGZP UBZN FD ATIIYRTK WP КЕТ
HIVJCI; TBF BLDPWPX RWTH ULAW TG VYCHX KQLJS US
DCGCW OPPUPR, VG KFDNUJK GI JIKKC PL KGCJ lAOV
KFTR GJFSAW KTZLZES WG RWXWT VWTL WP XPXGG, CJ
EPOS VYC BTZCUW XG ZGJQ PMHTRAIBJG WMGEG. JZQ DPB
JVYGM ZCLEWXR:CEB lAOV NYH JIKKC TGCWXE UHE JZK.
WX VCULD YTTKETK WPKCGVCWIQT PWVY QEBFKKQ, QNH
NZTTWIREL IAS VERPE ODJRXGSPTC EKWPTGEES, GMCG
TTVVPLTEEJ; YCW WV NYH TZYRWH LOKU MU AWO, KEPM
VG BLTP VQN RD DSGG AWKWUKKPL KGCJ, XY GPP KPG
ONZTT ICUJCHLSE KET DBQHJTWUG. DYN MVCK ZT MEWCW
HTWE ED JL, GPU YAE CH LQ! PGR UE, YH MWPP RXE
CDJCGOSE, XMS UZGJQJL, SXVPN HBG!

Исследуем расстояния между повторениями биграммы WX в приведенном выше шифротексте. Некоторые из расстояний между повторениями этого буквосочетания равны 9, 21, 66 и 30. Отдельные совпадения могут возникнуть случайно, в то время как остальные содержат информацию о длине ключевого слова. Вычислим попарные наибольшие общие делители этих чисел.

НОД (30,66) = 6,
НОД (3,9) = НОД (9,66) = НОД (9,30) = НОД (21,66) = 3.

Маловероятно, что ключевое слово состоит из трех букв, так что будем считать, что расстояния 9 и 21 попали случайно, а длина ключа равна 6.

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

Основная статья: Индекс совпадений

Тест Фридмана (иногда называемый каппа-тестом) был изобретен Вильямом Фридманом в 1920 году. Фридман использовал индекс совпадения, который измеряет частоты повторения символов, чтобы взломать шифр. Зная вероятность $\kappa _{p}$ того, что два случайно выбранных символа текста совпадают (примерно 0,067 для англ. языка) и вероятность совпадения двух случайно выбранных символов алфавита $\kappa _{r}$ (примерно 1 / 26 = 0,0385 для англ. языка), можно оценить длину ключа как:

${\frac {\kappa _{p}-\kappa _{r}}{\kappa _{o}-\kappa _{r}}}.$

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

$\kappa _{o}={\frac {\sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)}},$

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

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

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

Варианты

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

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

Виженер фактически изобрёл более стойкий шифр — шифр с автоключом. Несмотря на это, «шифр Виженера» ассоциируется с более простым многоалфавитным шифром. Фактически эти два шифра часто путали, называя их le chiffre indechiffrable. Беббидж фактически взломал более стойкий шифр с автоключом, в то время когда Касиски издал первое решение взлома многоалфавитного шифра с фиксированным ключом. Метод Виженера шифровки и расшифровки сообщений иногда относится к «варианту Битфорда». Его отличие от шифра Битфорда, изобретённого сэром Френсисом Битфордом, который, тем не менее, подобен шифру Виженера, заключается в использовании немного изменённого механизма шифрования и таблиц.

Несмотря на очевидную стойкость шифра Виженера, он широко не использовался в Европе. Большее распространение получил шифр Гронсфельда, созданный графом Гронсфельдом, идентичный шифру Виженера, за исключением того, что он использовал только 10 различных алфавитов (соответствующих цифрам от 0 до 9). Преимущество шифра Гронсфельда состоит в том, что в качестве ключа используется не слово, а цифровая последовательность, которая повторяется до тех пор, пока не станет равной длине шифруемого сообщения. Шифр Гронсфельда широко использовался по всей Германии и Европе, несмотря на его недостатки.

Литература

• Бабаш А.В., Шанкин Г.П. История криптографии. Часть I. — М.: Гелиос АРВ, 2002. — 240 с. — ISBN 5854380439.
• Жельников В. Кpиптография от папируса до компьютера — М.: ABF, 1996. — 336 с. — ISBN 978-5-87484-054-9
• Arto Salomaa. Public-Key Cryptography. — ISBN 3540528318.
• Н. Смарт. Криптография.. — Москва: Техносфера, 2005. — 528 с. — ISBN 5-94836-043-1.
• Singh S. The Code Book, Histoire des codes secrets (англ.): The Science of Secrecy from Ancient Egypt to Quantum Cryptography, De l'Égypte des pharaons à l'ordinateur quantique — New York City: Doubleday, Knopf Doubleday Publishing Group, 1999. — 416 p.
• Richard A. Mollin. Codes: The Guide to Secrecy From Ancient to Modern Times. — Chapman and Hall/CRC, 2005. — 704 Pages с. — ISBN 9781584884705.

Ссылки

• Носов В. А. Краткий исторический очерк развития криптографии (рус.) // Московский университет и развитие криптографии а России. Материалы конференции в МГУ.. — (17 октября 2002).