Как взломать шифр виженера

Нижеописанные шифры не используются на пратике. Они представляют историческую ценность и могут применяться в различных головоломках.

Взлом шифра Цезаря

Суть шифра Цезаря очень проста. Мы просто заменяем каждый символ алфавита на следующий или предыдущий на n позиций. Например, для n = 3.

Таким образом, сообщение HELLOWORLD будет зашифровано как KHOORZRUOG .

Лингвисты подсчитали насколько часто каждый символ алфавита встречается в текстах определенного языка. Например, в английском языке символ E встречается чаще остальных (12.702%). Применяя частотный анализ находим наиболее часто встречающийся в шифротексте символ. Т.е. если чаще всего в шифротексте встречается символ K – то, наиболее вероятно, что при шифровании E переходит в K, значит n = 6. Зная n и метод шифрования ничего не стоит заменить каждый символ шифротекста на его n-го предшественника в алфавите и получить исходный текст. Либо можно продолжить работать с частотами символов: взять второй по частоте символ в шифротексте и заменить его на A. И так далее, до победного конца. Данный метод можно использовать для пар, троек и больших сочетаний символов.

Примером использования шифра Цезаря является Unix утилита ROT13, которая осуществляет шифрование сдвигом символа на 13 позиций. Так как в английском языке 26 букв – двухкратное применение ROT13 возвращает исходный текст.

Взлом шифра Виженера

В шифре Виженера каждый символ открытого текста складывается по модулю длины алфавита с символом ключа. Для английского языка символы складываются по модулю (+ mod 26). Если ключ короче шифруемого сообщения – он дублируется столько раз, сколько необходимо. Например, шифрование сообщения HOUSTONWEHAVEAPROBLEM ключом NEVERMORE будет иметь вид:

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

Взлом шифра Виженера ненамного сложнее взлома шифра Цезаря. Допустим, нам известна длина ключа n = |key|, тогда рассмотрим символы на позициях 0, n-1, 2n-1…. Как и в случае с шифром Цезаря, можно предположить, что наиболее часто встречающимся символом будет зашифрованная E. Тогда, сложив по модулю E с наиболее частым символом мы получим первый символ ключа. Повторим для второго и последующих символов ключа. Зная ключ – дешифруем сообщение. В случаях, когда длина ключа неизвестна – просто выполним указанную процедуру для ключа длины 1, 2, …, n пока не будет получен связный текст.

Взлом одноразового шифроблокнота

Взлом шифра с правильным использованием одноразового шифроблокнота невозможен. Идея шифра с одноразовым шифроблокнотом состоит в том, чтобы сложить исходное сообщение со случайной строкой. Данный шифр обладает абсолютной криптографической стойкостью и не может быть взломан при наличии у взломщика одного лишь шифротекста. Почему этот метод практически не используется? Для дешифрования зашифрованного сообщения необходимо знать ключ. Ключ может быть использован только один раз. При этом длина ключа равна длине сообщения. А если мы можем передать ключ – почему бы вместо этого не передать сообщение?

В случае, если один ключ был использован для шифрования нескольких сообщений – например m1 и m2 все, что необходимо сделать взломщику – сложить их шифротексты по модулю.

Естественные языки достаточно избыточны, поэтому имея эту информацию, можно восстановить оригинальные сообщения m1 и m2. Например, зная что в ASCII кодировке XOR пробела с символами A-Z окажется в диапазоне [33, 58], можно получить символы открытого текста. Чем больше у взломщика сообщений зашифрованых одним ключом – тем проще осуществить взлом шифра.

Калькулятор шифрует входной текст на русском языке шифром Виженера. Неалфавитные символы (пробелы, знаки препинания, цифры) — не преобразуются.

Так как Шифр Цезаря у нас уже есть, было бы логично дополнить его калькулятором, который шифрует/расшифровывает текст используя шифр Виженера.

Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (ROTX — см. Шифр Цезаря). То есть к первой букве текста применяется преобразование, например, ROT5, ко второй, например, ROT17, и так далее. Последовательность применяемых преобразований определяется ключевой фразой, в которой каждая буква слова обозначает требуемый сдвиг, например, фраза ГДЕ ОН задает такую последовательность шифров Цезаря: ROT3-ROT4-ROT5-ROT15-ROT14, которая повторяется, пока не будет зашифрован весь текст сообщения.

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

Читайте также:  Как вернуть скайп на ноутбуке

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

Представим, что мы перехватили шифрограмму объёмом 226 символов:

ЮЬ ХЕ ИШ ЛО ФЫ ОХ ЕЯ ВГ ЦЭ ЦУ ЭШ ЮЛ ФЦ ЪЦ ЬЭ

ХО ХО ЪГ ЫЦ НЬ ИК ЦО БГ ЬХ ФЦ ЪЦ ЬЭ

ИИ КЦ ОБ ГЕ ХЧ ИХ ЙШ СО ИХ ЩУ ЦМ ЬО ЕЫ ЛУ

ИП ЬФ ЭЪ ИЙ ОЫ СТ ИЛ ГЩ БК ЬЕ ЦЦ НГ

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

ЭУ ЧЖ ЦГ ЪИ ЦН ЭЛ ЯХ ЙР ГЦ ЦИ ХИ ТЧ ЕХ СА ЯГ

Попробуем восстановить секретное сообщение. Предположим – нам известно, что в открытом тексте Ъ применён для обозначения пробелов, точек и запятых, а мягкий знак применяется и как Ь и вместо Ъ.

Прежде всего, нам следует определить длину ключа. Для этого необходимо найти повторяющиеся сочетания букв (диграфы, триграфы …). Если эти повторы не случайны, то они отстоят друг от друга на расстояние, кратное длине ключа. Чем длиннее повторяющиеся отрезки и чем больше повторений, тем лучше ситуация для криптоаналитика.

Диграф ЬХ встречается на позициях 2 и 47. Найдём расстояние между ними, которое равно 45 (47-2). Разложим разность позиций на множители: 45=3´3´5. Судя по этому можно сделать вывод, что ключ может быть длиной или 3, или 5, или 9, или 15 знаков.

Пара ХЕ встречается на позициях 3, 12, 165. Вычислим разности номеров позиций и разложим их на множители: 165-12=153 (3´3´17), 12-3=9 (3´3). Разность 153 и разность 9 имеют общие делители 3 и 9. Сопоставляя их с цифрами предыдущего диграфа ЬХ, видим общие делители 3 и 9. На данном этапе можно сделать предварительный вывод, что длина ключа равна 3 или 9.

Продолжая анализировать шифротекст, ищем повторы одинаковых последовательностей букв. Трёхзначную группу ФЫО находим на позициях 9 и 141. Расстояние между этими порядковыми номерами равно 132 (3´ 2´2´11). Возможные варианты длины ключа: 2 (но это неэффективно и маловероятно), 3, 4, 6, 11, 12 или 22.

Пара букв ГЫ (выделено жирным) появляется в шифрограмме пять раз – на позициях 36, 124, 133, 136, 169. Расстояние между позициями и разложение на множители следующее:

169 – 136 = 33 (3 ´ 11),

133 – 124 = 9 (3 ´ 3),

124 – 36 = 88 (8 ´ 11).

Очевидно, что общий делитель равен 3.

Диграф ЦН встречается на позициях 38, 104, 110, 205. Разность между номерами позиций кратна трём.

Диграф ИХ встречается на позициях 65, 71, 146 и 216. Причём на позициях 71 и 146 является началом 12-буквенной повторяющейся последовательности ИХЩУЦМЬОЕЫЛУ (она в шифровке подчёркнута). Повторение цепочек такой длины не случайно. Поэтому придаём расстоянию между этими номерами особое значение. Оно равно 75 и кратно 3.

Нельзя не обратить внимание на шестибуквенное повторение ФЦЪЦЬЭ на позициях 25 и 49 (выделено курсивом). Разность позиций также кратна трём.

Читайте также:  Видеокарта запускается но не выдает изображение

Расстояние (15) между позициями 41 и 56 шестибуквенной группы ИКЦОБГ также кратно трём.

Итак, сравнивая цифры, можно с большой вероятностью заключить, что длина ключевого слова (период гаммы) равна 3. Т.е. используется три сдвига алфавита: первый сдвиг применяется к буквам 1, 4, 7 и т.д.; второй сдвиг – к буквам 2, 5 , 8 и т.д.; третий сдвиг – к буквам 3, 6 , 9 и т.д. Поэтому выпишем шифротекст в три строки:

1). Ю Е Л Ы Е Г Ц Ш Ф Ц Х О Ы Ь Ц Г Ф Ц И …

2). Ь И О О Я Ц У Ю Ц Ь О Ъ Ц И О Ь Ц Ь И …

3). Х Ш Ф Х В Э Э Л Ъ Э Х Г Н К Б Х Ъ Э К …

Подсчитаем частоту встречаемости букв в каждой строке отдельно и получим таблицу, показанную на рис.13.

Сосредоточимся на аномально высокой частоте встречаемости (14) буквы Г в первой строке. Очевидно, что Г представляет собой шифр пробела, т.е. буквы Ъ открытого текста. Значит, сдвиг для первой строчки равен 9 (Ъ+9=Г). Т.е. для замены 1-ой, 4-ой, 7-ой и т.д. букв открытого текста брались буквы (по таблице Виженера) из строки, начинающейся с буквы Й, сдвинутой на 9 позиций (А+9=Й). Следующие по частоте мы видим буквы Ц (встретилась 9 раз) и О (6 штук). Им соответствуют буквы Н и Е открытого текста, отстоящие от них в алфавите на 9 позиций. Н и Е – часто встречающиеся буквы в русском языке (см. статистику под заголовком «Разработка средств шифрования»), это подтверждает, что первый сдвиг равен 9. Таким образом, первый элемент ключа равен 9 (в цифровом виде) или Й (в буквенном представлении), что соответствует следующей нумерации алфавита (без буквы Ё): А=0, Б=1, В=2, …, Я=31.

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

Рис. 13. Частоты встречаемости букв в шифрограмме.

Во второй строке буква И встречается 14 раз. С уверенностью можно сказать, что И является шифром твёрдого знака, который стоит на местах пробелов в открытом тексте. Поскольку буква И отстоит на 14 позиций от Ъ, то второй сдвиг равен 14. Дальше по частоте идут буквы Ц (9), Ь (8) и У (7). Сдвигая их на 14 позиций, видим соответствующие буквы открытого текста И, О и Е. Поскольку эти буквы имеют наибольшую частоту встречаемости в русском языке, мы окончательно убеждаемся, что второй элемент ключа равен 14, что соответствует букве О.

Проанализируем третий сдвиг. В третьей строке наиболее часто встречаются буквы Х и Э, каждая 11 раз. В отличие от первой и второй строк эта цифра не сильно выделяется над остальными, но, скорее всего, одна из этих букв соответствует пробелу. Буква Х отстоит от Ъ на 27 пунктов, буква Э – на 3. Мы могли бы поочерёдно опробовать оба сдвига, но существует другой подход.

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

Первая буква шифротекста – Ю. Применим сдвиг на 9. В таблице Виженера в строке начинающейся с буквы Й находим букву шифротектста (Ю), над которой в верхней строке увидим букву открытого текста (Х). Под первой буквой шифротекста (Ю) записываем первую букву открытого текста (Х).

Расшифровывая вторую букву шифрограммы (Ь) используем сдвиг на 14 позиций, соответствующий второму элементу ключа. В строке, начинающейся с буквы О, ищем букву шифрограммы (Ь). Над мягким знаком в верхней строке таблицы расположена буква О. Под второй буквой шифротекста (Ь) записываем вторую букву открытого текста (О). Под третьей буквой шифротекста (Х) записываем вопросительный знак, поскольку пока третья буква исходного сообщения нам неизвестна.

Читайте также:  Если не помнишь пин код симки

Четвёртую букву шифротекста (Е) расшифровываем аналогично, применяя сдвиг алфавита на 9 позиций, и записываем под ней букву открытого текста (Ь). Продолжая так далее, получим:

ШТ:ЮЬХ ЕИШ ЛОФ ЫОХ ЕЯВ ГЦЭ ЦУЭ ШЮЛ…

ОТ:ХО? ЬЪ? ВА? ТА? ЬС? ЪИ? НЕ? ПР? …

Мы знаем, что Ъ в открытом тексте означает пробел. Перепишем оба текста, отбрасывая Ъ в открытом тексте и стоящие над ним буквы в шифротексте, делая вместо них пробелы. Получим тексты, сгруппированные по словам.

ЮЬХЕ ШЛОФЫОХЕЯВ ЦЭЦУЭ ШЮЛФЦЪЦЬЭ

ХО?Ь ?ВА ? Т А?Ь С? И? НЕ? ПР? ЛИ? НО?

ХОХОЪГЫЦНЬ КЦОБ ЬХФЦЪЦЬЭ

МА?ЕМ?ТИ? У ?НА? О? ЛИ? НО?

И КЦОБ ЕХЧ ХЙШСО ХЩУЦМЬОЕЫЛУ

Я ? НА? Ч?О ? АК? Е ? РЕ? ГО? ЬН?К

ПЬФЭЪ ЙОЫСТ Л ЩБКЬЕЦЦН

? УЖ?С ? ЕН?Й ? Л?БО? НИ?

НЭЦЦНЧСЗЙ РО ООХЦ ЫГ ЮС ПЬР

Я? НИ?ОГ?А ?Е ?ЕЗ? Н? Р? ЖО?

ЫС ЫИ БФЫОРЬ Х ЩУЦ МЬОЕЫЛУЦЭАУУ ЫЦХЕ

Н? Н? У? ТА? У ? РЕ? ГО? ЬН? КИ? ЧЕ?ТИ? Ь

Л ЫЛАУЖЧ РОАЭЪЩГВУЭАБЙСГЭПУР

? Н?ЧЕ? О ?ЕТ? СЛ?ЩЕ?ЧУ? ИХ?ЖЕ?

ЭУЧЖЦ ЪИЦНЭЛЯХЙРГЦЦИ Х ТЧЕХСАЯ

П?ОШ? М?НЯ? ВС? АВ?НИ? М ?ОЧ? ИТ?

Обратим внимание на короткие слова, в которых не хватает одной буквы. В третьей строке открытого текста третье слово, скорее всего, – «ЧТО». Вместо вопросительного знака подставим букву Т. Буква открытого текста Т отстоит от буквы шифротекста Х (в алфавите) на 3 позиции. В пятой строке открытого текста во втором (двухбуквенном) слове, по-видимому, первая буква – Н. По буквам шифрованного (Р) и открытого (Н) текстов находим величину сдвига. Она тоже равна трём. Таким образом, мы получили подтверждение, что третий сдвиг равен 3. Третий элемент ключа соответствует букве Г.

Итак, мы имеем полный ключ, все три элемента: 9-14-3 (в цифровом виде) или ЙОГ (в буквенном варианте). Применяя сдвиг на 3 пункта, вместо вопросительного знака получаем недостающие буквы открытого текста. Вместо твёрдого знака ставим пробелы. Исходный текст восстановлен. "Секретное" сообщение называется «Я – великий математик». 🙂

Хоть хвастаться и неприлично,

Математику знаю отлично.

Я знаю, что такое треугольник –

Муж с женой и любовник.

Я никогда не лезу на рожон,

Но не устану треугольники «чертить».

И ничего нет слаще чужих жён!

Прошу меня вставанием почтить.

3.9.2. МОНОФОНИЧЕСКАЯ ЗАМЕНА.

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

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

В качестве примера зашифруем монофоническим шифром тот же текст:

ОТ– Ч Е Р Е З Э Т И Ш Т У К О В И Н Ы В С Ё, …

ШТ – Z Ь Б Ю Я I Г h И Л S Ъ Х + Ы Щ П 8 L :

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент – человек, постоянно откладывающий неизбежность. 10586 – | 7335 – или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Ссылка на основную публикацию
Adblock detector