Что такое шифр виженера
Что такое шифр виженера
Шифр Виженера — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.
В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее.
Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет такой вид:
Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:
Первый символ исходного текста («A») зашифрован последовательностью L, которая является первым символом ключа. Первый символ зашифрованного текста («L») находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ зашифрованного текста («X») получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Расшифровывание производится следующим образом: находим в таблице Виженера строку, соответствующую первому символу ключевого слова; в данной строке находим первый символ зашифрованного текста. Столбец, в котором находится данный символ, соответствует первому символу исходного текста. Следующие символы зашифрованного текста расшифровываются подобным образом.
Шифр Виженера
Калькулятор шифрует входной текст на русском языке шифром Виженера. Неалфавитные символы (пробелы, знаки препинания, цифры) — не преобразуются.
Так как Шифр Цезаря у нас уже есть, было бы логично дополнить его калькулятором, который шифрует/расшифровывает текст используя шифр Виженера.
Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (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 году еще один знаменитый англичанин — Чарльз Бэббидж, один из пионеров вычислительной техники. Но опубликовал схему анализа уже другой исследователь — Фридрих Касиски девятью годами позже.
И вот здесь начинается самое интересное: это послужило отправной точкой для работы по усилению этого шифра. Одно из усовершенствований заключалось в использовании ключевой фразы, равной по длине самому сообщению, что исключало возможность частотного анализа.
Однако данное улучшение содержало в себе другую уязвимость — по крайней мере, в том виде, в каком это было предложено, — использование реального текста в качестве ключевой фразы давало криптоаналитику статистическую информацию о ключе, что тоже могло помочь расшифровать текст.
Но от этой идеи оставался один шаг до следующей — использования в качестве ключа не осмысленного текста, а случайной последовательности знаков.
В итоге данная идея была реализована в виде одноразового шифровального блокнота. И вот такие шифры с использованием одноразовых блокнотов как раз и стали на какое-то время принципиально невзламываемыми и получили широкое распространение в гражданской и военной криптографии. Но про это в другой раз.
Что такое шифр виженера
Шифр Виженера ( фр. Chiffre de Vigenère ) — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.
Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джован Баттиста Беллазо (итал. Giovan Battista Bellaso ) в книге La cifra del. Sig. Giovan Battista Bellasо в 1553 году, однако в XIX веке получил имя Блеза Виженера, французского дипломата. Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа.
Описание
В шифре Цезаря каждая буква алфавита сдвигается на несколько строк; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет вид:
Человек, посылающий сообщение, записывает ключевое слово (« LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:
Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Расшифровывание производится следующим образом: находим в таблице Виженера строку, соответствующую первому символу ключевого слова; в данной строке находим первый символ зашифрованного текста. Столбец, в котором находится данный символ, соответствует первому символу исходного текста. Следующие символы зашифрованного текста расшифровываются подобным образом.
Если буквы A-Z соответствуют числам 0-25, то шифрование Виженера можно записать в виде формулы:
Шифр Вижинера и его разгадка
Сразу скажу, что этот топик интересен только с точки зрения истории криптографии, описываемый шифр малопригоден для защиты информации в современном мире. Но, тем не менее, алгоритмы, описываемые в топике, могут пригодится на специализированных олимпиадах.
Блезом Вижинером в 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. Понять почему индекс резко возрастает довольно просто. В случае, когда все символы сдвигаются на одну и ту же позицию, индекс совпадения такой же, как и у исходного текста. В случае, когда мы вычисляем индекс для шифра Вижинера мы во всех случаях (кроме того, где длина сдвига равна длине ключа) сравниваем фактически случайный текст.
Определив длину ключа мы можем, воспользовавшись таблицей частоты букв, выяснить, что зашифровано было известное детское стихотворение:
Наша Таня громко плачет:
Уронила в речку мячик.
Таня, Танечка, не плачь,
Не утонет в речке мяч!
В качестве пароля была взята фамилия автора «Барто».
Надеюсь, в этой заметке вы нашли для себя что-то новое. И, надеюсь, полученные знания вы используете исключительно во благо.