Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Представим, что мы перехватили шифрограмму объёмом 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),

136 - 133 = 3,

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: …

 

 




Поделиться с друзьями:


Дата добавления: 2014-11-29; Просмотров: 1644; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.