Что такое шифр виженера
Что такое шифр виженера
Шифр Виженера — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.
В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее.
Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет такой вид:
Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:
Первый символ исходного текста («A») зашифрован последовательностью L, которая является первым символом ключа. Первый символ зашифрованного текста («L») находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ зашифрованного текста («X») получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Расшифровывание производится следующим образом: находим в таблице Виженера строку, соответствующую первому символу ключевого слова; в данной строке находим первый символ зашифрованного текста. Столбец, в котором находится данный символ, соответствует первому символу исходного текста. Следующие символы зашифрованного текста расшифровываются подобным образом.
Шифр Виженера
Шифр Виженера (фр. 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 году, и позднее изобретение шифра было присвоено именно ему. Давид Кан в своей книге «Взломщики кодов» отозвался об этом осуждающе, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания».
Шифр Виженера достаточно прост для использования в полевых условиях, особенно если применяются шифровальные диски. Например, «конфедераты» использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Во время войны командование Конфедерации полагалось на три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и — так как война подходила к концу — «Come Retribution».
Гилберт Вернам попытался улучшить взломанный шифр (он получил название шифр Вернама-Виженера в 1918 году), но, несмотря на его усовершенствования, шифр так и остался уязвимым к криптоанализу. Однако работа Вернама в конечном итоге всё же привела к получению шифра, который действительно невозможно взломать.
Описание
В шифре Цезаря каждая буква алфавита сдвигается на несколько строк; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На разных этапах кодировки шифр Виженера использует различные алфавиты из этой таблицы. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет вид:
Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:
Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Расшифровывание производится следующим образом: находим в таблице Виженера строку, соответствующую первому символу ключевого слова; в данной строке находим первый символ зашифрованного текста. Столбец, в котором находится данный символ, соответствует первому символу исходного текста. Следующие символы зашифрованного текста расшифровываются подобным образом.
Если буквы A-Z соответствуют числам 0-25, то шифрование Виженера можно записать в виде формулы:
Криптоанализ
Шифр Виженера «размывает» характеристики частот появления символов в тексте, но некоторые особенности появления символов в тексте остаются. Главный недостаток шифра Виженера состоит в том, что его ключ повторяется. Поэтому простой криптоанализ шифра может быть построен в два этапа:
Тесты Фридмана и Касиски могут помочь определить длину ключа.
Метод Касиски
В 1863 году Фридрих Касиски был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя Чарльз Беббидж разработал этот алгоритм уже в 1854 году. В то время когда Беббидж занимался взломом шифра Виженера, John Hall Brock Thwaites представил новый шифр в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Thwaites’а является лишь частным случаем шифра Виженера, Thwaites предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily — именем жены поэта.
Зашифрованный текст в данном случае не будет повторять последовательности символов, которые соответствуют повторным последовательностям исходного текста. В данном шифрованном тексте есть несколько повторяющихся сегментов, которые позволяют криптоаналитику найти длину ключа:
Более длинные сообщения делают тест более точным, так как они включают в себя больше повторяющихся сегментов зашифрованного текста. В данном шифрованном тексте есть несколько повторяющихся сегментов, которые позволяют криптоаналитику найти длину ключа:
Расстояние между повторяющимися DYDUXRMH равно 18, это позволяет сделать вывод, что длина ключа равна одному из значений: 18,9,6,3 или 2. Расстояние между повторяющимися NQD равно 20. Из этого следует, что длина ключа равна 20 или 10, или 5, или 4 или 2. Сравнивая возможные длины ключей, можно сделать вывод, что длина ключа (почти наверняка) равна 2.
Тест Фридмана
Тест Фридмана (иногда называемый каппа-тест) был изобретен Вильямом Фридманом в 1920 году. Фридман использовал индекс совпадения, который измеряет частоты повторения символов, чтобы взломать шифр. Зная вероятность 
того, что два случайно выбранных символа текста совпадают (примерно 0,067 для англ. языка) и вероятность совпадения двух случайно выбранных символов алфавита 
(примерно 1 / 26 = 0,0385 для англ. языка), можно оценить длину ключа как:
Из наблюдения за частотой совпадения следует:
Где С — размер алфавита (26 символов для англ. языка), N — длина текста, и 
до 
— наблюдаемые частоты повторения символов зашифрованного текста. Однако, это только приблизительное значение, точность которого увеличивается при большем размере текста. На практике это было бы необходимо для перебора различных ключей приближаясь к исходному.
Частотный анализ
Как только длина ключа становится известной, зашифрованный текст можно записать во множество столбцов, каждый из которых соответствует одному символу ключа. Каждый столбец состоит из исходного текста, который зашифрован шифром Цезаря; ключ к шифру Цезаря является всего-навсего одним символом ключа для шифра Виженера, который используется в этом столбце. Используя методы, подобные методам взлома шифра Цезаря, можно расшифровать зашифрованный текст. Усовершенствование теста Касиски, известное как метод Кирхгофа, заключается в сравнении частоты появления символов в столбцах с частотой появления символов в исходном тексте для нахождения ключевого символа для этого столбца. Когда все символы ключа известны, криптоаналитик может легко расшифровать шифрованный текст, получив исходный текст. Метод Кирхгофа не применим, когда таблица Виженера скремблирована, вместо использования обычной алфавитной последовательности, хотя тест Касиски и тесты совпадения всё ещё могут использоваться для определения длины ключа для этого случая.
Варианты
Вариант running key (бегущий ключ) шифра Виженера когда-то был невзламываемым. Эта версия использует в качестве ключа блок текста, равный по длине исходному тексту. Так как ключ равен по длине сообщению, то методы предложенные Фридманом и Касиски не работают (так как ключ не повторяется). В 1920 году Фридман первым обнаружил недостатки этого варианта. Проблема с running key шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым.
Виженер фактически изобрёл более стойкий шифр — шифр с автоключом. Несмотря на это, «шифр Виженера» ассоциируется с более простым многоалфавитным шифром. Фактически эти два шифра часто путали, называя их le chiffre indechiffrable. Беббидж фактически взломал более стойкий шифр с автоключом, в то время когда Касиски издал первое решение взлома многоалфавитного шифра с фиксированным ключом. Метод Виженера зашифровки и расшифровки сообщений иногда относится к «варианту Битфорда». Его отличие от шифра Битфорда, изобретенного сэром Френсисом Битфордом, который, тем не менее, подобен шифру Виженера, заключается в использовании немного измененного механизма шифрования и таблиц.
Несмотря на очевидную стойкость шифра Виженера, он широко не использовался в Европе. Большее распространение получил шифр Гронсфилда, созданный графом Гронсфилдом, идентичный шифру Виженера, за исключением того, что он использовал только 10 различных алфавитов (соответствующих цифрам от 0 до 9). Преимущество шифра Гронсфилда состоит в том, что в качестве ключа используется не слово, а недостаток — в небольшом количестве алфавитов. Шифр Гронсфилда широко использовался по всей Германии и Европе, несмотря на его недостатки.
Шифр Вижинера и его разгадка
Сразу скажу, что этот топик интересен только с точки зрения истории криптографии, описываемый шифр малопригоден для защиты информации в современном мире. Но, тем не менее, алгоритмы, описываемые в топике, могут пригодится на специализированных олимпиадах.
Блезом Вижинером в 17 веке был предложен довольно интересный метод шифрования. Ключом шифра служит специальная фраза. Эта фраза, многократно повторяясь, пишется над шифруемым текстом. Каждая буква секретного сообщения получается сдвигом каждой буквы исходного текста на определённое число, задаваемое буквой ключевой фразы (Буква А не даёт сдвига, буква Б — сдвиг на одну позицию, В — на две и т.д.).
Например попробуем зашифровать слово «СЕКРЕТ», пользуясь ключевой фразой «АБВ». Буква С не сдвигается, первая буква Е сдвигается на одну позицию, превращаясь в Ж, буква К сдвигается на две позиции, превращаясь в М. Продолжая шифровать сообщение, мы в итоге получим «СЖМРЖФ».
На протяжении трёх веков этот шифр считался практически не взламываемым. Первые попытки взлома этого шифра были предприняты в 19 веке. Все эти попытки были основаны на определении длины ключевой фразы. Если нам известна её длина, то весь зашифрованый текст мы можем разбить на фрагменты, каждый из которых кодируется одним и тем же сдвигом. В нашем примере буквы С, Р кодируются с нулевым сдвигом, Е, Е кодируются со сдвигом в единицу, К, Т кодируются со сдвигом 2. Если текст достаточно длинный, мы можем применить частотный анализ и тем самым, раскрыть исходное сообщение. Получается, что разгадка этого шифра сводится к поиску длины ключевой фразы.
Сейчас мы рассмотрим два метода нахождения этой длины. Первый метод был предложен Фридрихом Касицким. Основа метода Касицкого — поиск биграмм. В случае, когда в шифруемом сообщении одна и та же биграмма повторяется на расстоянии, кратном длине ключевой фразы, она встретитс на тех же позициях и в зашифрованном тексте. Найдя это расстояния и, получив все его делители, мы получим набор чисел-кандидатов на длину ключевой фразы.
Попробуем расшифровать методом Касицкого следующий текст: «ОАИТАБНПХЮПМЪАЭМАЗЧАФРЮЯЦМАТВУШКГЮНШИЪДООЯВТЫХЧЪТЫЖПЫТЕЭНХЕАПНХДРСЕЗЬУНЯЗ». Зашифрованный текст содержит три повторяющихся биграммы МА (позиции 16 и 26), ТЫ (позиции 44 и 49) и НХ (позиции 57 и 62). Биграмма МА повторяется на расстоянии в 10 позиций, биграммы ТЫ и НХ на расстоянии в 5 позиций. Скорее всего позиции длина ключевой последовательности равна 5. Рассматриваемый метод требует некоторого везения, т.к. в тексте могут возникать «случайные» биграммы. Их вероятность много ниже, чем у «регулярных», но в небольших текстах они могут значительно усложнить расшифровку.
Прежде чем окончательно расшифровать текст, мы рассмотрим ещё один метод определения длины ключа, предложенный Фридманом. Суть метода в циклическом сдвиге сообщения. Полученные таким образом сообщения записываются под оригинальным шифротекстом и подсчитывается число совпавших букв в верхней и нижней строке. На основе этих чисел вычисляется т.н. индекс совпадений, равный отношению количества совпадений к полной длине сообщения. Для русских текстов индекс совпадений равен примерно 6%, но для случайных текстов этот индекс равен 1/32, т.е. приблизительно 3%. На этом факте и основан метод Фридмана. Текст записывается со сдвигом в 1,2,3 и т.д. позиций и для каждого сдвига вычисляется индекс совпадений. Циклический сдвигая наше сообщение получаем:
Сдвиг Совпадений Индекс
2 0 0.000
3 5 0.068
4 2 0.027
5 8 0.110 (!)
6 1 0.014
7 1 0.014
8 2 0.027
При сдвиге 5 индекс резко возрастает, следовательно длина ключевого слова скорее всего равна 5. Понять почему индекс резко возрастает довольно просто. В случае, когда все символы сдвигаются на одну и ту же позицию, индекс совпадения такой же, как и у исходного текста. В случае, когда мы вычисляем индекс для шифра Вижинера мы во всех случаях (кроме того, где длина сдвига равна длине ключа) сравниваем фактически случайный текст.
Определив длину ключа мы можем, воспользовавшись таблицей частоты букв, выяснить, что зашифровано было известное детское стихотворение:
Наша Таня громко плачет:
Уронила в речку мячик.
Таня, Танечка, не плачь,
Не утонет в речке мяч!
В качестве пароля была взята фамилия автора «Барто».
Надеюсь, в этой заметке вы нашли для себя что-то новое. И, надеюсь, полученные знания вы используете исключительно во благо.
Шифр Виженера
Калькулятор шифрует входной текст на русском языке шифром Виженера. Неалфавитные символы (пробелы, знаки препинания, цифры) — не преобразуются.
Так как Шифр Цезаря у нас уже есть, было бы логично дополнить его калькулятором, который шифрует/расшифровывает текст используя шифр Виженера.
Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (ROTX — см. Шифр Цезаря). То есть к первой букве текста применяется преобразование, например, ROT5, ко второй, например, ROT17, и так далее. Последовательность применяемых преобразований определяется ключевой фразой, в которой каждая буква слова обозначает требуемый сдвиг, например, фраза ГДЕ ОН задает такую последовательность шифров Цезаря: ROT3-ROT4-ROT5-ROT15-ROT14, которая повторяется, пока не будет зашифрован весь текст сообщения.
Как повествует Википедия, шифр Виженера является шифром подстановки, то есть шифром, в котором каждая буква исходного текста заменяется буквой шифр-текста. Для вскрытия подобных шифров используется частотный криптоанализ.
Еще там можно прочитать про вариант шифра с бегущим ключом (running key), который был когда-то был невзламываемым. Этот вариант заключается в использовании в качестве ключа блока текста, равного по длине исходному тексту. Впрочем, и этот вариант, как оказалось, успешно поддается взлому. Проблема с бегущим ключом шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым, но такие системы уже относятся к классу систем одноразового кода, или одноразового шифр-блокнота (one-time pad). Они действительно не поддаются взлому, однако их практическое применение довольно затруднительно.
Как шифр из XVI века стал основой для невзламываемого шифра XX века
История информационной безопасности: как шифр Виженера, популярный еще с XVI века, стал основой для невзламываемого шифра XX века.
Большинство «исторических» и фигурирующих в художественной литературе и кино шифров принадлежат к одному и тому же виду — моноалфавитным шифрам. Про главную слабость данной криптосхемы — возможность взлома шифра путем анализа частоты использования символов — мы уже сказали достаточно, и осознана она была задолго до появления вычислительной техники.
Один из самых знаменитых и интересных шифров, призванных решить эту проблему, — это так называемый шифр Виженера. Названный именем французского дипломата XVI века, он был на самом деле изобретен независимо друг от друга разными людьми. Что интересно, Блеза Виженера при этом среди них не было, он лишь убедил в свое время Генриха III использовать его, а название это шифр получил уже в XIX веке.
Первое его описание можно найти еще в XVI веке в «Трактате о шифрах» Леона Баттиста Альберти, более известного тем, что он впервые изложил математические основы перспективы в живописи. Идея была довольно простой, однако все равно означала выход криптографии на новый уровень — полиалфавитные шифры.
Моноалфавитный шифр использует для замены каждого знака исходного сообщения постоянно соответствующий ему другой — представьте, что вы просто пользуетесь другим алфавитом. Дальше уже в общем-то не важно, случайные это замены или полученные сдвигом на условленное число мест, как в шифре Цезаря, буквы ли это, цифры или вовсе другие знаки.
Как наглядно иллюстрирует рассказ Конан Дойля «Пляшущие человечки», это могут быть хоть картинки, главная уязвимость шифра остается прежней, можно делать предположения о встречающихся в тексте словах, можно проанализировать частоту использования той или иной буквы в зашифрованном сообщении и построить свои догадки.
Ваш покорный слуга один раз сам — скорее от скуки, чем по необходимости, — «расшифровал» именно таким образом email, пришедший ему в неверной кодировке, это не потребовало никаких особых навыков или серьезных вычислительных мощностей.
Полиалфавитный шифр использует множество разных алфавитов подстановки циклически. На примере шифра Виженера это выглядит следующим образом: берем за основу шифр Цезаря и составляем таблицу, содержащую все возможные смещения:
У нас есть 26 разных алфавитов замены, теперь нужно решить, по какому принципу мы их меняем. Простой переход к следующему алфавиту для каждой новой буквы был бы уже некоторым усложнением, но по-настоящему сложным для взлома этот шифр становится с использованием ключевой фразы.
Раз уж мы говорим о разных древностях, пусть нашей ключевой фразой будет VINTAGE. В таком случае, чтобы зашифровать фразу THINK ABOUT, нам нужно повторить ключевую фразу так, чтобы получить столько же букв, сколько в исходном сообщении:
Теперь для каждого знака исходного сообщения мы используем замену, которая стоит в строке, обозначенной буквой ключевой фразы, в столбце буквы исходного текста. Например, первая буква заменяется на тот символ, который стоит на пересечении строки T и столбца V, то есть на «O».
Расшифровка производится, соответственно, в обратном порядке: мы перебираем по очереди строки, соответствующие буквам ключевой фразы, находим в них очередные знаки зашифрованного сообщения и записываем буквы, обозначающие колонки, в которых они стоят.
Интересно, что в оригинальном изложении идеи у Альберти описывается специальный диск с вращающимися кольцами с алфавитом, и только чуть позже, уже другим автором, была предложена таблица, которую мы используем выше. Диск, описанный в трактате 1466 года, в итоге использовался, например, в армии конфедератов во время гражданской войны в Америке.
В целом шифр имел репутацию очень надежного. Его называл невзламываемым математик Чарльз Лутвидж Доджсон (более известный как писатель Льюис Кэрролл), и восхвалял журнал Scientific American, однако гораздо более широкое распространение получила его модификация, известная как шифр Гронсфилда. Он отличался тем, что алфавитов замены в нем было всего 10 (по числу цифр), а ключевая фраза была не словом, а числом.
Но интересна эта история как раз тем, что на самом деле шифр Виженера поддавался криптоанализу при определенных условиях: по ряду признаков можно было определить длину ключа, а дальше, анализируя ряды букв, зашифрованных одной и той же строкой таблицы, уже можно применить стандартный метод анализа, использующий данные о сравнительной частоте разных букв в языке.
История информационной безопасности: как #шифр из XVI века стал основой для невзламываемого шифра XX века
Первым успешную атаку на шифр Виженера (если быть совсем точным — на одну из его модификаций, но метод применим и к оригинальной версии) осуществил в 1854 году еще один знаменитый англичанин — Чарльз Бэббидж, один из пионеров вычислительной техники. Но опубликовал схему анализа уже другой исследователь — Фридрих Касиски девятью годами позже.
И вот здесь начинается самое интересное: это послужило отправной точкой для работы по усилению этого шифра. Одно из усовершенствований заключалось в использовании ключевой фразы, равной по длине самому сообщению, что исключало возможность частотного анализа.
Однако данное улучшение содержало в себе другую уязвимость — по крайней мере, в том виде, в каком это было предложено, — использование реального текста в качестве ключевой фразы давало криптоаналитику статистическую информацию о ключе, что тоже могло помочь расшифровать текст.
Но от этой идеи оставался один шаг до следующей — использования в качестве ключа не осмысленного текста, а случайной последовательности знаков.
В итоге данная идея была реализована в виде одноразового шифровального блокнота. И вот такие шифры с использованием одноразовых блокнотов как раз и стали на какое-то время принципиально невзламываемыми и получили широкое распространение в гражданской и военной криптографии. Но про это в другой раз.