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

К:Википедия:Статьи без источников (тип: не указан)

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

Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джован Баттиста Беллазо (итал. 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 году), но, несмотря на его усовершенствования, шифр так и остался уязвимым к криптоанализу. Однако работа Вернама в конечном итоге всё же привела к получению шифра, который действительно невозможно взломать.

Описание

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

ATTACKATDAWN

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

LEMONLEMONLE

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

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

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

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

<math>C_i \equiv (P_i + K_i) \mod\ 26</math>

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

<math>P_i \equiv (C_i - K_i + 26) \mod\ 26</math>

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

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

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

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

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

В 1863 году Фридрих Касиски был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя Чарльз Беббидж разработал этот алгоритм уже в 1854 году. В то время когда Беббидж занимался взломом шифра Виженера, Джон Холл Брок Твейтс представил новый шифр в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Твейтса является лишь частным случаем шифра Виженера, Твейтс предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «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 году. Фридман использовал индекс совпадения, который измеряет частоты повторения символов, чтобы взломать шифр. Зная вероятность <math>\kappa_p</math> того, что два случайно выбранных символа текста совпадают (примерно 0,067 для англ. языка) и вероятность совпадения двух случайно выбранных символов алфавита <math>\kappa_r</math> (примерно 1 / 26 = 0,0385 для англ. языка), можно оценить длину ключа как:

<math>\frac{\kappa_p-\kappa_r}{\kappa_o-\kappa_r}.</math>

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

<math>\kappa_o = \frac{\sum_{i=1}^c n_i(n_i - 1)}{N(N-1)},</math>

где С — размер алфавита (26 символов для англ. языка), N — длина текста, и <math>n_i</math> — наблюдаемые частоты повторения символов зашифрованного текста. Однако, это только приблизительное значение, точность которого увеличивается при большем размере текста. На практике это^[что?] было бы необходимо для перебора различных ключей приближаясь к исходному.

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

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

Варианты

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

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

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

Отрывок, характеризующий Шифр Виженера

За жарким подали шампанское. Гости встали с своих мест, поздравляя старого князя. Княжна Марья тоже подошла к нему.
Он взглянул на нее холодным, злым взглядом и подставил ей сморщенную, выбритую щеку. Всё выражение его лица говорило ей, что утренний разговор им не забыт, что решенье его осталось в прежней силе, и что только благодаря присутствию гостей он не говорит ей этого теперь.
Когда вышли в гостиную к кофе, старики сели вместе.
Князь Николай Андреич более оживился и высказал свой образ мыслей насчет предстоящей войны.
Он сказал, что войны наши с Бонапартом до тех пор будут несчастливы, пока мы будем искать союзов с немцами и будем соваться в европейские дела, в которые нас втянул Тильзитский мир. Нам ни за Австрию, ни против Австрии не надо было воевать. Наша политика вся на востоке, а в отношении Бонапарта одно – вооружение на границе и твердость в политике, и никогда он не посмеет переступить русскую границу, как в седьмом году.
– И где нам, князь, воевать с французами! – сказал граф Ростопчин. – Разве мы против наших учителей и богов можем ополчиться? Посмотрите на нашу молодежь, посмотрите на наших барынь. Наши боги – французы, наше царство небесное – Париж.
Он стал говорить громче, очевидно для того, чтобы его слышали все. – Костюмы французские, мысли французские, чувства французские! Вы вот Метивье в зашей выгнали, потому что он француз и негодяй, а наши барыни за ним ползком ползают. Вчера я на вечере был, так из пяти барынь три католички и, по разрешенью папы, в воскресенье по канве шьют. А сами чуть не голые сидят, как вывески торговых бань, с позволенья сказать. Эх, поглядишь на нашу молодежь, князь, взял бы старую дубину Петра Великого из кунсткамеры, да по русски бы обломал бока, вся бы дурь соскочила!
Все замолчали. Старый князь с улыбкой на лице смотрел на Ростопчина и одобрительно покачивал головой.
– Ну, прощайте, ваше сиятельство, не хворайте, – сказал Ростопчин, с свойственными ему быстрыми движениями поднимаясь и протягивая руку князю.
– Прощай, голубчик, – гусли, всегда заслушаюсь его! – сказал старый князь, удерживая его за руку и подставляя ему для поцелуя щеку. С Ростопчиным поднялись и другие.


Княжна Марья, сидя в гостиной и слушая эти толки и пересуды стариков, ничего не понимала из того, что она слышала; она думала только о том, не замечают ли все гости враждебных отношений ее отца к ней. Она даже не заметила особенного внимания и любезностей, которые ей во всё время этого обеда оказывал Друбецкой, уже третий раз бывший в их доме.
Княжна Марья с рассеянным, вопросительным взглядом обратилась к Пьеру, который последний из гостей, с шляпой в руке и с улыбкой на лице, подошел к ней после того, как князь вышел, и они одни оставались в гостиной.
– Можно еще посидеть? – сказал он, своим толстым телом валясь в кресло подле княжны Марьи.
– Ах да, – сказала она. «Вы ничего не заметили?» сказал ее взгляд.
Пьер находился в приятном, после обеденном состоянии духа. Он глядел перед собою и тихо улыбался.
– Давно вы знаете этого молодого человека, княжна? – сказал он.
– Какого?
– Друбецкого?
– Нет, недавно…
– Что он вам нравится?
– Да, он приятный молодой человек… Отчего вы меня это спрашиваете? – сказала княжна Марья, продолжая думать о своем утреннем разговоре с отцом.
– Оттого, что я сделал наблюдение, – молодой человек обыкновенно из Петербурга приезжает в Москву в отпуск только с целью жениться на богатой невесте.
– Вы сделали это наблюденье! – сказала княжна Марья.
– Да, – продолжал Пьер с улыбкой, – и этот молодой человек теперь себя так держит, что, где есть богатые невесты, – там и он. Я как по книге читаю в нем. Он теперь в нерешительности, кого ему атаковать: вас или mademoiselle Жюли Карагин. Il est tres assidu aupres d'elle. [Он очень к ней внимателен.]
– Он ездит к ним?
– Да, очень часто. И знаете вы новую манеру ухаживать? – с веселой улыбкой сказал Пьер, видимо находясь в том веселом духе добродушной насмешки, за который он так часто в дневнике упрекал себя.
– Нет, – сказала княжна Марья.
– Теперь чтобы понравиться московским девицам – il faut etre melancolique. Et il est tres melancolique aupres de m lle Карагин, [надо быть меланхоличным. И он очень меланхоличен с m elle Карагин,] – сказал Пьер.
– Vraiment? [Право?] – сказала княжна Марья, глядя в доброе лицо Пьера и не переставая думать о своем горе. – «Мне бы легче было, думала она, ежели бы я решилась поверить кому нибудь всё, что я чувствую. И я бы желала именно Пьеру сказать всё. Он так добр и благороден. Мне бы легче стало. Он мне подал бы совет!»
– Пошли бы вы за него замуж? – спросил Пьер.
– Ах, Боже мой, граф, есть такие минуты, что я пошла бы за всякого, – вдруг неожиданно для самой себя, со слезами в голосе, сказала княжна Марья. – Ах, как тяжело бывает любить человека близкого и чувствовать, что… ничего (продолжала она дрожащим голосом), не можешь для него сделать кроме горя, когда знаешь, что не можешь этого переменить. Тогда одно – уйти, а куда мне уйти?…
– Что вы, что с вами, княжна?
Но княжна, не договорив, заплакала.
– Я не знаю, что со мной нынче. Не слушайте меня, забудьте, что я вам сказала.
Вся веселость Пьера исчезла. Он озабоченно расспрашивал княжну, просил ее высказать всё, поверить ему свое горе; но она только повторила, что просит его забыть то, что она сказала, что она не помнит, что она сказала, и что у нее нет горя, кроме того, которое он знает – горя о том, что женитьба князя Андрея угрожает поссорить отца с сыном.
– Слышали ли вы про Ростовых? – спросила она, чтобы переменить разговор. – Мне говорили, что они скоро будут. Andre я тоже жду каждый день. Я бы желала, чтоб они увиделись здесь.
– А как он смотрит теперь на это дело? – спросил Пьер, под он разумея старого князя. Княжна Марья покачала головой.
– Но что же делать? До года остается только несколько месяцев. И это не может быть. Я бы только желала избавить брата от первых минут. Я желала бы, чтобы они скорее приехали. Я надеюсь сойтись с нею. Вы их давно знаете, – сказала княжна Марья, – скажите мне, положа руку на сердце, всю истинную правду, что это за девушка и как вы находите ее? Но всю правду; потому что, вы понимаете, Андрей так много рискует, делая это против воли отца, что я бы желала знать…
Неясный инстинкт сказал Пьеру, что в этих оговорках и повторяемых просьбах сказать всю правду, выражалось недоброжелательство княжны Марьи к своей будущей невестке, что ей хотелось, чтобы Пьер не одобрил выбора князя Андрея; но Пьер сказал то, что он скорее чувствовал, чем думал.
– Я не знаю, как отвечать на ваш вопрос, – сказал он, покраснев, сам не зная от чего. – Я решительно не знаю, что это за девушка; я никак не могу анализировать ее. Она обворожительна. А отчего, я не знаю: вот всё, что можно про нее сказать. – Княжна Марья вздохнула и выражение ее лица сказало: «Да, я этого ожидала и боялась».
– Умна она? – спросила княжна Марья. Пьер задумался.
– Я думаю нет, – сказал он, – а впрочем да. Она не удостоивает быть умной… Да нет, она обворожительна, и больше ничего. – Княжна Марья опять неодобрительно покачала головой.
– Ах, я так желаю любить ее! Вы ей это скажите, ежели увидите ее прежде меня.
– Я слышал, что они на днях будут, – сказал Пьер.
Княжна Марья сообщила Пьеру свой план о том, как она, только что приедут Ростовы, сблизится с будущей невесткой и постарается приучить к ней старого князя.


Женитьба на богатой невесте в Петербурге не удалась Борису и он с этой же целью приехал в Москву. В Москве Борис находился в нерешительности между двумя самыми богатыми невестами – Жюли и княжной Марьей. Хотя княжна Марья, несмотря на свою некрасивость, и казалась ему привлекательнее Жюли, ему почему то неловко было ухаживать за Болконской. В последнее свое свиданье с ней, в именины старого князя, на все его попытки заговорить с ней о чувствах, она отвечала ему невпопад и очевидно не слушала его.
Жюли, напротив, хотя и особенным, одной ей свойственным способом, но охотно принимала его ухаживанье.
Жюли было 27 лет. После смерти своих братьев, она стала очень богата. Она была теперь совершенно некрасива; но думала, что она не только так же хороша, но еще гораздо больше привлекательна, чем была прежде. В этом заблуждении поддерживало ее то, что во первых она стала очень богатой невестой, а во вторых то, что чем старее она становилась, тем она была безопаснее для мужчин, тем свободнее было мужчинам обращаться с нею и, не принимая на себя никаких обязательств, пользоваться ее ужинами, вечерами и оживленным обществом, собиравшимся у нее. Мужчина, который десять лет назад побоялся бы ездить каждый день в дом, где была 17 ти летняя барышня, чтобы не компрометировать ее и не связать себя, теперь ездил к ней смело каждый день и обращался с ней не как с барышней невестой, а как с знакомой, не имеющей пола.
Дом Карагиных был в эту зиму в Москве самым приятным и гостеприимным домом. Кроме званых вечеров и обедов, каждый день у Карагиных собиралось большое общество, в особенности мужчин, ужинающих в 12 м часу ночи и засиживающихся до 3 го часу. Не было бала, гулянья, театра, который бы пропускала Жюли. Туалеты ее были всегда самые модные. Но, несмотря на это, Жюли казалась разочарована во всем, говорила всякому, что она не верит ни в дружбу, ни в любовь, ни в какие радости жизни, и ожидает успокоения только там . Она усвоила себе тон девушки, понесшей великое разочарованье, девушки, как будто потерявшей любимого человека или жестоко обманутой им. Хотя ничего подобного с ней не случилось, на нее смотрели, как на такую, и сама она даже верила, что она много пострадала в жизни. Эта меланхолия, не мешавшая ей веселиться, не мешала бывавшим у нее молодым людям приятно проводить время. Каждый гость, приезжая к ним, отдавал свой долг меланхолическому настроению хозяйки и потом занимался и светскими разговорами, и танцами, и умственными играми, и турнирами буриме, которые были в моде у Карагиных. Только некоторые молодые люди, в числе которых был и Борис, более углублялись в меланхолическое настроение Жюли, и с этими молодыми людьми она имела более продолжительные и уединенные разговоры о тщете всего мирского, и им открывала свои альбомы, исписанные грустными изображениями, изречениями и стихами.
Жюли была особенно ласкова к Борису: жалела о его раннем разочаровании в жизни, предлагала ему те утешения дружбы, которые она могла предложить, сама так много пострадав в жизни, и открыла ему свой альбом. Борис нарисовал ей в альбом два дерева и написал: Arbres rustiques, vos sombres rameaux secouent sur moi les tenebres et la melancolie. [Сельские деревья, ваши темные сучья стряхивают на меня мрак и меланхолию.]
В другом месте он нарисовал гробницу и написал:
«La mort est secourable et la mort est tranquille
«Ah! contre les douleurs il n'y a pas d'autre asile».
[Смерть спасительна и смерть спокойна;
О! против страданий нет другого убежища.]
Жюли сказала, что это прелестно.
– II y a quelque chose de si ravissant dans le sourire de la melancolie, [Есть что то бесконечно обворожительное в улыбке меланхолии,] – сказала она Борису слово в слово выписанное это место из книги.
– C'est un rayon de lumiere dans l'ombre, une nuance entre la douleur et le desespoir, qui montre la consolation possible. [Это луч света в тени, оттенок между печалью и отчаянием, который указывает на возможность утешения.] – На это Борис написал ей стихи:
«Aliment de poison d'une ame trop sensible,
«Toi, sans qui le bonheur me serait impossible,
«Tendre melancolie, ah, viens me consoler,
«Viens calmer les tourments de ma sombre retraite