код виженера как расшифровать
Шифр Виженера
Шифр Виженера — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.
Описание алгоритма
В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова.
Квадрат Виженера
Например, предположим, что исходный текст имеет вид:
Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:
Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Расшифрование
Криптоанализ шифра может быть построен в два этапа:
Практический пример
Задание:
Необходимо расшифровать данный текст:
Решение:
Для быстрого и качественного решения используем программу Cryptools: 
Вставляем наш текст в созданное окно:
Выбираем вкладку Analysis > Symmetric encryption (classic) > Ciphertext-only > Vigenere
Далее программа находит длину ключа :
Жмём > Continue Далее находит сам ключ: 
Шифр Вижинера и его разгадка
Сразу скажу, что этот топик интересен только с точки зрения истории криптографии, описываемый шифр малопригоден для защиты информации в современном мире. Но, тем не менее, алгоритмы, описываемые в топике, могут пригодится на специализированных олимпиадах.
Блезом Вижинером в 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). Они действительно не поддаются взлому, однако их практическое применение довольно затруднительно.
Криптоанализ шифра Виженера
Прежде всего предположим, что противник уверен в том, что шифрованный текст был получен либо с помощью моноалфавитной подстановки, либо с помо¬щью шифра Виженера. Чтобы выяснить, какой именно из этих двух методов был использован, можно провести простой тест. Если использовалась моноалфа¬витная подстановка, статистические показатели шифрованного текста не будут отличаться от соответствующих показателей языка, на котором написан откры¬тый текст. Если для анализа имеется лишь одно сообщение, точного совпадения статистиче¬ских показателей можно и не получить. Но если статистика достаточно точно повторяет статистику обычного открытого текста, можно предположить, что использовалась моноалфавитная подстановка.
Если же, наоборот, все указывает на то, что был применен шифр Виженера, то, как мы увидим несколько позже, успех дальнейшего анализа текста зависит от того, удастся ли определить длину ключевого слова. Решение этой задачи ос¬новано на следующей особенности данного шифра: если начальные символы двух одинаковых последовательностей открытого текста находятся друг от друга на расстоянии, кратном длине ключа, эти последовательности будут представлены одинаковыми последовательностями и в шифрованном тексте. Например, пусть в открытом тексте имеются две одинаковые последовательности символов (слово или их сочетание), тогда если они будут зашифрованы при с использованием одного и того же фрагмента ключа, мы получим одинаковые последовательности символов шифротекста. Аналитик, имеющий в своем распоряжении только шифрованный текст, обнаружит повторяющуюся последовательность символов со смещением в К (кратное длине ключа) символов.
Дальнейший анализ базируется на другой особенности данного шифра. Если ключевое слово имеет длину N, то шифр, по сути, состоит из N моноалфавитных подстановочных шифров. Например, при использовании ключевого слова deceptive буквы, находящиеся на 1-й, 10-й, 19-й и т.д. позициях, шифруются одним и тем же моноалфавитным шифром. Это дает возможность использования известных характеристик частотных распределений букв открытого текста для взлома каждого моноалфавитного шифра по отдельности.
Периодичности в ключевой строке можно избежать, используя для ключевой строки непериодическую последовательность той же длины, что и само сообще¬ние. Виженер предложил подход, получивший название системы с автоматиче¬ским выбором ключа, когда последовательность ключевой строки получается в результате конкатенации ключевого слова с самим открытым текстом. Для рас¬сматриваемого примера мы получим следующее.
ключ: deceptivewearediscoveredsav
открытый текст: wearediscoveredsaveyourself
шифрованный текст: ZICVTWQNGKZEIIGASXSTSLVVWLA
Однако и эта схема оказывается уязвимой. Поскольку и в ключевой строке, и в открытом тексте значения частоты распределения букв будут одинаковы, статистические методы можно применить и в данном случае. Тогда, например, символ а шифрованный при помощи символа ключа b, будет встречаться с частотой равной произведению частот этих символов. Именно такие закономерности позволяют добиться успеха при анализе шифрованного текста.
Лучшей защитой от подобных методов криптоанализа является выбор ключевого слова, по длине равного длине открытого текста, но отличающегося от открытого текста по статистическим показателям. Такая система была предложена инженером компании AT&T Гилбертом Вернамом (Gilbert Vernam) в 1918 г. Его система оперирует не буквами, а двоичными числами. Кратко ее можно выразить формулой:
Таким образом, шифрованный текст генерируется путем побитового выполне¬ния операции XOR для открытого текста и ключа. Благодаря свойствам этой операции для расшифровки достаточно выполнить подобную операцию:
Сутью этой технологии является способ выбора ключа. Вернам предложил использовать закольцованную ленту, что означает циклическое повторение клю¬чевого слова, так что его система на самом деле предполагала работу хоть и с очень длинным, но все же повторяющимся ключом. Несмотря на то что такая схема в силу очень большой длины ключа значительно усложняет задачу криптоанализа, схему, тем не менее, можно взломать, имея в распоряжении достаточно длинный фрагмент шифрованного текста, известные или вероятно известные фрагменты открытого текста либо и то, и другое сразу.
Офицер армейского корпуса связи Джозеф Моборн (Joseph Mauborgne) предложил такие улучшения схемы шифрования Вернама, которые сделали эту схему исключительно надежной. Моборн предложил отказаться от повторений, а случайным образом генерировать ключ, по длине равный длине сообщения. Такая схема, получившая название ленты однократного использования (или схемы с одноразовым блокнотом), взлому не поддается. В результате ее применения на выходе получается случайная последовательность, не имеющая статистической взаимосвязи с открытом текстом. Поскольку в этом случае шифрованный текст не дает никакой информации об открытом тексте, нет способа и взломать код.
Сложность практического применения этого метода заключается в том, что и отправитель, и получатель должны располагать одним и тем же случайным ключом и иметь возможность защитить его от посторонних. Поэтому, несмотря на все преимущества шифра Вернама перед другими шифрами, на практике к нему прибегают редко.
Как шифр из XVI века стал основой для невзламываемого шифра XX века
История информационной безопасности: как шифр Виженера, популярный еще с XVI века, стал основой для невзламываемого шифра XX века.
Большинство «исторических» и фигурирующих в художественной литературе и кино шифров принадлежат к одному и тому же виду — моноалфавитным шифрам. Про главную слабость данной криптосхемы — возможность взлома шифра путем анализа частоты использования символов — мы уже сказали достаточно, и осознана она была задолго до появления вычислительной техники.
Пять книг и фильмов, в которых взлом шифров происходит по-настоящему интересно: http://t.co/LShWV0qB7X pic.twitter.com/ydMkdeehd1
Один из самых знаменитых и интересных шифров, призванных решить эту проблему, — это так называемый шифр Виженера. Названный именем французского дипломата XVI века, он был на самом деле изобретен независимо друг от друга разными людьми. Что интересно, Блеза Виженера при этом среди них не было, он лишь убедил в свое время Генриха III использовать его, а название это шифр получил уже в XIX веке.
Первое его описание можно найти еще в XVI веке в «Трактате о шифрах» Леона Баттиста Альберти, более известного тем, что он впервые изложил математические основы перспективы в живописи. Идея была довольно простой, однако все равно означала выход криптографии на новый уровень — полиалфавитные шифры.
Моноалфавитный шифр использует для замены каждого знака исходного сообщения постоянно соответствующий ему другой — представьте, что вы просто пользуетесь другим алфавитом. Дальше уже в общем-то не важно, случайные это замены или полученные сдвигом на условленное число мест, как в шифре Цезаря, буквы ли это, цифры или вовсе другие знаки.
Информационная безопасность времен Второй мировой: Рихард Зорге и книжный шифр — http://t.co/vwp8vCEHAR pic.twitter.com/vPxbttY19F
Как наглядно иллюстрирует рассказ Конан Дойля «Пляшущие человечки», это могут быть хоть картинки, главная уязвимость шифра остается прежней, можно делать предположения о встречающихся в тексте словах, можно проанализировать частоту использования той или иной буквы в зашифрованном сообщении и построить свои догадки.
Ваш покорный слуга один раз сам — скорее от скуки, чем по необходимости, — «расшифровал» именно таким образом email, пришедший ему в неверной кодировке, это не потребовало никаких особых навыков или серьезных вычислительных мощностей.
Полиалфавитный шифр использует множество разных алфавитов подстановки циклически. На примере шифра Виженера это выглядит следующим образом: берем за основу шифр Цезаря и составляем таблицу, содержащую все возможные смещения:
У нас есть 26 разных алфавитов замены, теперь нужно решить, по какому принципу мы их меняем. Простой переход к следующему алфавиту для каждой новой буквы был бы уже некоторым усложнением, но по-настоящему сложным для взлома этот шифр становится с использованием ключевой фразы.
Раз уж мы говорим о разных древностях, пусть нашей ключевой фразой будет VINTAGE. В таком случае, чтобы зашифровать фразу THINK ABOUT, нам нужно повторить ключевую фразу так, чтобы получить столько же букв, сколько в исходном сообщении:
Теперь для каждого знака исходного сообщения мы используем замену, которая стоит в строке, обозначенной буквой ключевой фразы, в столбце буквы исходного текста. Например, первая буква заменяется на тот символ, который стоит на пересечении строки T и столбца V, то есть на «O».
Расшифровка производится, соответственно, в обратном порядке: мы перебираем по очереди строки, соответствующие буквам ключевой фразы, находим в них очередные знаки зашифрованного сообщения и записываем буквы, обозначающие колонки, в которых они стоят.
Интересно, что в оригинальном изложении идеи у Альберти описывается специальный диск с вращающимися кольцами с алфавитом, и только чуть позже, уже другим автором, была предложена таблица, которую мы используем выше. Диск, описанный в трактате 1466 года, в итоге использовался, например, в армии конфедератов во время гражданской войны в Америке.
В целом шифр имел репутацию очень надежного. Его называл невзламываемым математик Чарльз Лутвидж Доджсон (более известный как писатель Льюис Кэрролл), и восхвалял журнал Scientific American, однако гораздо более широкое распространение получила его модификация, известная как шифр Гронсфилда. Он отличался тем, что алфавитов замены в нем было всего 10 (по числу цифр), а ключевая фраза была не словом, а числом.
Но интересна эта история как раз тем, что на самом деле шифр Виженера поддавался криптоанализу при определенных условиях: по ряду признаков можно было определить длину ключа, а дальше, анализируя ряды букв, зашифрованных одной и той же строкой таблицы, уже можно применить стандартный метод анализа, использующий данные о сравнительной частоте разных букв в языке.
История информационной безопасности: как #шифр из XVI века стал основой для невзламываемого шифра XX века
Первым успешную атаку на шифр Виженера (если быть совсем точным — на одну из его модификаций, но метод применим и к оригинальной версии) осуществил в 1854 году еще один знаменитый англичанин — Чарльз Бэббидж, один из пионеров вычислительной техники. Но опубликовал схему анализа уже другой исследователь — Фридрих Касиски девятью годами позже.
И вот здесь начинается самое интересное: это послужило отправной точкой для работы по усилению этого шифра. Одно из усовершенствований заключалось в использовании ключевой фразы, равной по длине самому сообщению, что исключало возможность частотного анализа.
Пять актуальных уроков, которые можно извлечь из взлома «Энигмы» во время Второй мировой: http://t.co/lVeB3pbCaW pic.twitter.com/QF5JDKAQiK
Однако данное улучшение содержало в себе другую уязвимость — по крайней мере, в том виде, в каком это было предложено, — использование реального текста в качестве ключевой фразы давало криптоаналитику статистическую информацию о ключе, что тоже могло помочь расшифровать текст.
Но от этой идеи оставался один шаг до следующей — использования в качестве ключа не осмысленного текста, а случайной последовательности знаков.
В итоге данная идея была реализована в виде одноразового шифровального блокнота. И вот такие шифры с использованием одноразовых блокнотов как раз и стали на какое-то время принципиально невзламываемыми и получили широкое распространение в гражданской и военной криптографии. Но про это в другой раз.