Математика и криптография. Тайны шифров и логическое мышление

Есть и более легкий метод шифрования этим способом. Для него требуется одна таблица. Она на следующем развороте.

Пользоваться ею легко. Для шифрования надо найти букву открытого текста в первой строке и букву ключа в первом столбце. Буква шифрограммы находится на пересечении выбранного столбца и строки. Для расшифровки надо найти букву ключа в первом столбце и букву шифрограммы в выбранной строке. Буква открытого текста будет в первой строке полученного столбца. Всё довольно просто.

Однако я рекомендую научиться использовать арифметику вычетов. В дальнейшем это очень пригодится. Это как с таблицей умножения: можно вызубрить её в том виде, в каком она приводится на тетрадных обложках. А можно понять правила умножения, и тогда без проблем перемножать любые числа.

Теперь давай научимся расшифровывать тексты, записанные шифрами многоалфавитной замены. Например, у тебя оказалось зашифрованное послание и ты знаешь, что оно зашифровано именно таким шифром. Как подступиться к расшифровке? Вот простейший метод:

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

2. Как только длина ключа установлена, у нас появляется столько шифрограмм (зашифрованных шифром одноалфавитной замены), из скольких символов состоит ключ. А взламывать такие шифрограммы ты уже умеешь, то есть твоя задача сводится к тому, что мы изучили на прошлой неделе. Да, в этот раз расшифровка намного более трудоёмкая, поскольку придется несколько раз подсчитывать частоты и выдвигать гипотезы, а это непросто. Кроме того, надо суметь не запутаться и сопоставить расшифровки друг с другом. Но при должном умении и старании все получится.

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

А вот второй метод – именно что хитроумный, но не всегда работает. Его мы и изучим. Он называется «метод Фридриха Касиски[1 - Фридрих Вильгельм Касиски – Немецкий криптограф и археолог. В 1863 году опубликовал труд «Тайнопись и искусство дешифрования», в котором детально описал методы расшифровки текстов, зашифрованных шифрами многоалфавитной замены. При помощи этих методов был взломан шифр, который считался неприступным более четырехсот лет.]». Идея заключается в том, что в обычном языке, на котором говорят люди, очень часто повторяются некоторые группы символов. Это коротенькие словечки или даже буквосочетания вроде многочисленных «ОРО» и «ОЛО» в русском языке. Грамотный шифровальщик избегает использования коротких словечек (об этом мы уже рассуждали на прошлой неделе), но вот с частыми буквосочетаниями это сделать сложно. Так что надо искать в шифрограмме такие повторяющиеся буквосочетания.

Итак, в шифрограмме мы ищем повторяющиеся группы символов. Лучше всего, чтобы длина этих групп была не менее трёх символов: если будет меньше, то велик шанс пойти по ложному следу. Это происходит из-за того, что разные двухбуквенные сочетания из шифруемого текста были зашифрованы при помощи разных символов в ключе, а в результате получились одинаковые буквосочетания в шифрограмме. Если группа символов длиннее, то такого практически не происходит.

Расстояния между последовательными появлениями одинаковых групп в шифрограмме будут кратны длине ключа. Так что мы подсчитаем расстояния между всеми этими группами, а длина ключа будет равна наибольшему общему делителю всех расстояний.

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

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

Давай потренируемся во всем этом на практике. Представь себе, что ты видишь такое послание:

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

Если сделать здесь частотный анализ, то получится вот такая таблица:

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

Что делают настоящие криптоаналитики для анализа подобной ситуации? Они строят графики. Вот два графика (они называются «гистограммами»):

Гистограмма частот символов в шифрограмме

Гистограмма частот букв русского языка

Ты можешь представить себе, что эти графики – набор вертикальных штырьков, на которые нанизаны блины, как в детской пирамидке или головоломке «ханойская башня». Количество блинов на штырьке соответствует количеству целых процентов, а последний блин по толщине соответствует долям процента. Если расположить эти башни по убыванию количества блинов, то как раз получатся такие гистограммы. По горизонтали отложены буквы по убыванию частот их в языке, а по вертикали – относительные частоты в процентах.

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

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

Быстрый просмотр шифрограммы показывает, что есть одно семисимвольное сочетание «ЗЗЫХШЮХ», которое встречается в шифрограмме дважды. При этом повторяющихся восьмисимвольных сочетаний нет. (Надо отметить, что чем больше в повторяющихся сочетаниях символов, тем лучше). Проверим, на каких позициях стоят эти буквосочетания. Первое стоит на позиции 49, а второе – на 509. Разница: 509 – 49 = 460. Запомним.

Больше семисимвольных сочетаний нет, поэтому посмотрим на шестисимвольные. Есть четыре таких буквосочетания, но первые два из них – это префикс и суффикс семисимвольного сочетания, рассмотренного ранее, поэтому учитывать их не будем. Другие – это «ЛЕПФВТ» и «ТЩРГГП». Первое из этих двух буквосочетаний встречается на позициях 225 и 421. Их разница: 421–225 = 196. Второе стоит на позициях 294 и 330, и разница составляет 330–294 = 36.

Итак, у нас есть три числа, три разницы: 460, 196 и 36. Рассмотрим наибольший общий делитель этих чисел. Он равен 4. В принципе, на этом можно остановиться, поскольку мы только что нашли длину ключа. Теоретически, ключ может быть длиной в 2 символа (поскольку 4 делится на 2), но можно предположить, что никто не будет кодировать сообщение при помощи такого короткого ключа. Если бы у нас в качестве наибольшего общего делителя получилось число 8, то нам пришлось бы проверить ещё и пятисимвольные сочетания, а потом и все остальные, чтобы убедиться, что длина ключа равна именно 8, а не 4.

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

ТИЪР

УЫМТ

УНРШ

АТПЮ

АКЧЧ

ЙАЙТ

ГЗУШ

МНОЧ

ЖАЧЗ

СЦСЮ

ЙЗЗЫ

ХШЮХ

АФЭБ

ДЦПЯ

…

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

Итак, мы разобрались с длиной ключа и распределили буквы шифрограммы по столбцам (то есть по алфавитам). Теперь они полностью соответствуют частотам употребления букв (и пробела) в русском языке. Поскольку пробел встречается чуть ли не в два раза чаще, чем самая частая буква русского алфавита «О», то резонно предположить, что самый частый символ в каждом столбце обозначает пробел.

А теперь, если ты внимательно изучишь таблицу, приведённую ранее, то увидишь, что у пробела – код 0. Это значит, что при сложении с ним символ не меняется. Получается, что самая часто встречающаяся буква в каждом столбце и есть буква ключа. Вот это да!

Давай подсчитаем. Вот первый столбец:

«ТУУААЙГМЖСЙХАДХУАЖУЖУШАЗППЕАТПЫБЫГСШГАПУОАХЙДПБАЭЛМОУОРПЛЙРМСШБУАОВПОЙЛЩПБАОЭЕБЯЩПНГОПУАЖИБУЛАЖОЖЕЙАВППФЗЙЭЖЗА ЙЕУБНБПАЖЫПРВХБАВОБВЯАИЭНЕБ».

Можно заметить, что чаще всего здесь встречается буква «А». Итак, первая буква ключа найдена. Я рекомендую тебе тщательно подсчитать в каждом столбце количество букв и определить наиболее часто встречающуюся, после чего понять ключ.

Если у тебя все получилось, то нашелся ключ – «АЗОТ» (это газ). И теперь можно легко расшифровать секретное послание. Как я уже писал, надо из шифрограммы вычесть ключ по модулю 32. Вот так:

Если всё сделано правильно, то проявится открытое сообщение: «САЛЮТУЮ ТЕБЕ. КАК ВИДИШЬ, В ДЕЛЕ ДЕШИФРОВКИ ШИФРОВ МНОГОАЛФАВИТНОЙ ЗАМЕНЫ ТАКЖЕ НЕТ НИЧЕГО СЛОЖНОГО. НЕОБХОДИМО ПРОСТО ОЧЕНЬ ТЩАТЕЛЬНО ВСЁ РАССЧИТЫВАТЬ, ВЫПОЛНЯТЬ МНОГО АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ И БЫТЬ КРАЙНЕ ВНИМАТЕЛЬНЫМ. ПОЭТОМУ, КАК И В ПРОШЛЫЙ РАЗ, Я ХОЧУ ЗАЯВИТЬ О ПОЛНОЙ БЕСПОЛЕЗНОСТИ ТАКИХ ШИФРОВ. КАКОЙ БЫ НИ БЫЛА ДЛИНА КЛЮЧА, ШИФРОГРАММА В КОНЕЧНОМ ИТОГЕ БУДЕТ ВЗЛОМАНА ТЕМ, КОМУ ИНТЕРЕСНО ЕЁ СОДЕРЖИМОЕ. НО БЛАГОДАРЯ ЭТОМУ УПРАЖНЕНИЮ ТЫ УЖЕ МОЖЕШЬ ПОНЯТЬ И ПОДУМАТЬ НА ТЕМУ, КАК МОЖНО ИЗМЕНИТЬ ЭТОТ СПОСОБ ШИФРОВАНИЯ, ЧТОБЫ ОН СТАЛ АБСОЛЮТНО НЕВЗЛАМЫВАЕМЫМ. ДЕРЗАЙ».

Что ж, ещё пара моментов: