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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Блез Виженер

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

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

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

История[править | править код]

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

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

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

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

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

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

Посол Франции в Риме Блез де Виженер, познакомившись с трудами Тритемия, Белазо, Кардано, Порта, Альберти, также увлекся криптографией. В 1585 году он написал «Трактат о шифрах», в котором излагаются основы криптографии. В этом труде он замечает: «Все вещи в мире представляют собой шифр. Вся природа является просто шифром и секретным письмом». Эта мысль была позднее повторена Блезом Паскалем — одним из основоположников теории вероятностей, а в настоящее время и Норбертом Винером — «отцом кибернетики».[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:
Итак, шифр Виженера получается как повторяющаяся комбинация сдвигов. В общем случае этот шифр не сохраняет частоту встречающихся букв и по этой причине не может напрямую подвергаться статистическому анализу.

Криптоанализ[править | править код]

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

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

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

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

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

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

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

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






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

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

Частота букв в английском алфавите.jpg

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

Частота букв в английском алфавите с сдвигом на 4.jpg

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

Роторные машины[править | править код]

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

Частотный анализ[править | править код]

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

Упоминания в литературе[править | править код]

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

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

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

О Р Т Е Г А

Т У Ф К Д Г 

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

НАСТОЯЩИЙ ВИНОВНИК КРАЖИ АЛМАЗОВ

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

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

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

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

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

ФНШЗГЭЛЛ ШРУДЕНКОЛГ ГНСБКССЕУ
ОКРУГА; ДА, Я ОДИН, В ЧЕМ И ПОДПИСЫ

ПНФЦЕЕ ЕГ Г СЖНО И ЫИО Н РСИТКЦЬ
ВАЮСЬ СВОИМ НАСТОЯЩИМ ИМЕНЕМ,

ЕДБУБ ТЕТЛО ТБФЦСБЮЙП МПЗТЖП
ОРТЕГА

ТУФКДГ

Варианты[править | править код]

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

Вариант 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.
  3. Сергей и Марина Бондаренко. Шифры из прошлого: тайнопись и загадки докомпьютерной эпохи (рус.), 3DNews - Daily Digital Digest (8 июля 2015). Проверено 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).
  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.
  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. 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.
  13. Lab exercise: Vigenere, RSA, DES, and Authentication Protocols // CS 415: Computer and Network Security. — 2006.
  14. Arto Salomaa. Public-Key Cryptography. — ISBN 3540528318.

Литература[править | править код]

Ссылки[править | править код]