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

Блез Виженер

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

Хотя шифр легко понять и реализовать, на протяжении трёх столетий он противостоял всем попыткам его взломать, благодаря чему его называли «неразгаданным шифром» (фр. le chiffre indéchiffrable). Многие люди пытались реализовать схемы шифрования, которые по сути являлись шифрами Виженера.[5]

История

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

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

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

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

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

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

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

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

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

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

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

Описание

править
 
Квадрат Виженера, или таблица Виженера, также известная как 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

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

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

 

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

 [10]

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

Применение

править

В 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-х гг. им активно пользовались обе стороны Гражданской войны в США. Вместо таблиц у них были специальные медные диски, но принцип работы остался прежним[12].

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

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

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

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

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

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

править

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

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

 .

Эмпирически проверено, что индекс совпадения длинных осмысленных английских текстов, таких как «Моби Дик» Меллвила, приблизительно равен 0,065. При этом, конечно, в тексте оставляют только 26 букв английского алфавита. В то же время абсолютно случайный достаточно длинный текст на 26 буквах, в котором все буквы встречаются приблизительно одинаковое число раз, равен 0,038. Замечено, что чем «осмысленнее» текст, тем выше его индекс совпадения. Это обстоятельство как раз и помогает вычислять длину ключа в шифре Виженера.

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

Это может свидетельствовать о том, что длина ключа равна  , хотя и может оказаться ложным следом.

Действительно, если длина ключа равна  , то текст   будет получен из   сдвигом, следовательно, сохранит  , а текст   , в свою очередь, является случайной выборкой осмысленного текста, следовательно, должен сохранить его статистические характеристики, в частности индекс совпадения.

Если индекс совпадения некоторого языка неизвестен, то использование теста Касиски также возможно. Нужно не сравнивать полученные значения индексов совпадения со стандартным значением, а смотреть, когда этот индекс резко возрастёт. Это может сигнализировать о найденной длине ключа. Конечно, речь идёт о расшифровке осмысленных и одновременно достаточно длинных текстов. Впрочем, понятие осмысленности для формальных языков — понятие непростое.

Другим применением теста Касиски является проверка сохранения частотностей встречающихся букв при шифровании. Пусть   — зашифрованный текст, причём алгоритм шифрования неизвестен. Если известно, что использовался обычный английский алфавит и значение   близко к 0,065, то это даёт основание полагать, что использовался шифр, сохраняющий частотности. Возможно, что это шифр простой замены. В ситуации, когда значение   далеко от 0,065, можно предположить, что использовался шифр, не сохраняющий частотности, или же текст был бессмысленным, или же использовался другой алфавит и т. п. Одним словом, что-то оказалось не так и необходим более глубокий анализ.

Однако вернёмся к шифру Виженера. Пусть определили правильно длину ключа, равную  . Теперь нужно найти сам ключ.

Гистограмма, построенная по стандартным частотностям букв в языке, имеет свои отличительные особенности. Они объясняются крайне неравномерным использованием букв в английском языке. Эта неравномерность как раз и позволяет эффективно применять частотный анализ.

 

Прежде всего, обращают на себя внимание «пики», соответствующие буквам A, E, H, I, N, O, R, S, T, и «пеньки», соответствующие J, Q, X, Z. При этом некоторые «пики» стоят рядом, даже есть целая тройка: R, S, T. Все вместе даёт весьма специфический рельеф.

 

Если используется сдвиг на 4, то картина изменяется циклически. Наблюдается циклический сдвиг рельефа на 4 единицы. Если не знать величину сдвига, то её нетрудно восстановить, руководствуясь здравым смыслом.

Роторные машины

править

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

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

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

править

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

Упоминания в литературе

править

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

СГУЧПВЭЛЛЗИРТЕПНДНФГИНБОРГЙУГЛЧД
КОТХЖГУУМЗДХРЪСГСЮДТПЪАРВЙГГИЩВЧ
ЭЕЦСТУЖВСЕВХАХЯФБЬБЕТФЗСЭФТХЖЗБЗ
ЪГФБЩИХХРИПЖТЗВТЖЙТГОЙБНТФФЕОИХТ
ТЕГИИОКЗПТФЛЕУГСФИПТЬМОФОКСХМГБТ
ЖФЫГУЧОЮНФНШЗГЭЛЛШРУДЕНКОЛГГНСБК
ССЕУПНФЦЕЕЕГГСЖНОЕЫИОНРСИТКЦЬЕДБ
УБТЕТЛОТБФЦСБЮЙПМПЗТЖПТУФКДГ

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

О Р Т Е Г А
 
Т У Ф К Д Г 
 

Следовательно, ключ — 432513. Зная ключ, можно легко перевести данный документ:

НАСТОЯЩИЙ ВИНОВНИК КРАЖИ АЛМАЗОВ
 
СГУЧПВЭЛЛ ЗИРТЕПНД НФГИН БОРГЙУГ

И УБИЙСТВА СОЛДАТ ОХРАНЫ В НОЧЬ НА
  
Л ЧДКОТХЖГ УУМЗДХ РЪСГСЮ Д ТПЪА РВ

ДВАДЦАТЬ ВТОРОЕ ЯНВАРЯ ТЫСЯЧА
 
ЙГГИЩВЧЭ ЕЦСТУЖ ВСЕВХА ХЯФБЬБ

ВОСЕМЬСОТ ДВАДЦАТЬ ШЕСТОГО ГОДА
 
ЕТФЗСЭФТХ ЖЗБЗЪГФБ ЩИХХРИП ЖТЗВ

НЕ ЖОАМ ДАКОСТА, НЕСПРАВЕДЛИВО ПРИ
 
ТЖ ЙТГО ЙБНТФФЕ ОИХТТЕГИИОКЗП ТФЛ

ГОВОРЕННЫЙ К СМЕРТИ, А Я, НЕСЧАСТНЫЙ
 
ЕУГСФИПТЬМ О ФОКСХМ Г Б ТЖФЫГУЧОЮН

СЛУЖАЩИЙ УПРАВЛЕНИЯ АЛМАЗНОГО
 
ФНШЗГЭЛЛ ШРУДЕНКОЛГ ГНСБКССЕУ

ОКРУГА; ДА, Я ОДИН, В ЧЕМ И ПОДПИСЫ
 
ПНФЦЕЕ ЕГ Г СЖНО И ЫИО Н РСИТКЦЬ

ВАЮСЬ СВОИМ НАСТОЯЩИМ ИМЕНЕМ,
 
ЕДБУБ ТЕТЛО ТБФЦСБЮЙП МПЗТЖП

ОРТЕГА
 
ТУФКДГ

Варианты

править

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

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

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

Примечания

править
  1. Martin, Keith M. Everyday Cryptography (англ.). — Oxford University Press, 2012. — P. 142. — ISBN 978-0-19-162588-6.
  2. Дискретная математика: алгоритмы. Исторический очерк. rain.ifmo.ru. Дата обращения: 22 декабря 2017. Архивировано из оригинала 21 декабря 2017 года.
  3. Сергей и Марина Бондаренко (2015-07-08). "Шифры из прошлого: тайнопись и загадки докомпьютерной эпохи". 3DNews - Daily Digital Digest. Архивировано 23 декабря 2017. Дата обращения: 22 декабря 2017.
  4. 1 2 3 4 5 6 7 Бабаш А.В., Шанкин Г.П. История криптографии. Часть I. — М.: Гелиос АРВ, 2002. — С. 240 с.. — ISBN 5854380439.
  5. Smith, Laurence D. Substitution Ciphers // Cryptography the Science of Secret Writing: The Science of Secret Writing (англ.). — Dover Publications, 1943. — P. 81. — ISBN 0-486-20247-X.
  6. 1 2 Носов В. А. Краткий исторический очерк развития криптографии (рус.) // Московский университет и развитие криптографии а России. Материалы конференции в МГУ.. — (17 октября 2002). Архивировано 26 января 2012 года.
  7. 1 2 3 David, Kahn. The Codebreakers: The Story of Secret Writing. — Simon & Schuster, 1999. — ISBN 0-684-83130-9.
  8. Knudsen, Lars R. Block Ciphers—a survey. — London: Springer, 1997. — ISBN 3-540-65474-7.
  9. Stanislaw Jarecki. Crypto Overview, Perfect Secrecy, One-time Pad // University of California. — 2004. Архивировано 17 мая 2017 года.
  10. Richard A. Mollin. Codes: The Guide to Secrecy From Ancient to Modern Times. — Chapman and Hall/CRC, 2005. — 704 Pages с. — ISBN 9781584884705.
  11. Жельников В. Кpиптография от папируса до компьютераМ.: ABF, 1996. — 336 с. — ISBN 978-5-87484-054-9
  12. Маккей, 2023, с. 60.
  13. Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. — New York City: Doubleday, 1999. — 416 p. с. — ISBN 978-1-85702-879-9.
  14. Lab exercise: Vigenere, RSA, DES, and Authentication Protocols // CS 415: Computer and Network Security. — 2006. Архивировано 23 июля 2011 года.
  15. Arto Salomaa. Public-Key Cryptography. — ISBN 3540528318.

Литература

править

Ссылки

править