Книга шифров. Тайная история шифров и их расшифровки



страница7/32
Дата24.08.2017
Размер4,62 Mb.
1   2   3   4   5   6   7   8   9   10   ...   32

Очень скоро он приобрел известность в лондонском обществе как дешифровальщик, готовый взяться за любое зашифрованное сообщение, и к нему стали обращаться со всевозможными задачами. Так, Бэббидж помог отчаявшемуся биографу, пытающемуся дешифровать стенографические записи Джона Флемстида, первого королевского астронома Англии. Он также пришел на помощь историку, разгадывающему шифр Генриетты-Марии, жены Карла I. В 1854 году Бэббидж сотрудничал с адвокатом и использовал криптоанализ, чтобы представить в судебном разбирательстве решающее доказательство. За эти годы он собрал значительную картотеку зашифрованных сообщений, которые он собирался использовать в качестве основы для авторитетной книги по криптоанализу под названием «Основные принципы дешифрования». В книге были бы даны по два примера каждого вида шифра; на одном из примеров было бы показано, как взломать шифр, а второй предназначался бы в качестве упражнения для читателя. К сожалению, как это случилось и со множеством других его грандиозных замыслов, книга не была закончена.

Несмотря на то что большинство криптоаналитиков уже оставили всякую надежду когда-либо взломать шифр Виженера, Бэббиджа побудил попытаться дешифровать его обмен письмами с Джоном Холом Бруком Твэйтсом, дантистом из Бристоля, имевшим довольно наивное представление о шифрах. В 1854 году Твэйтс заявил, что он придумал новый шифр, который по сути был аналогичен шифру Виженера. Он написал в «Джорнел оф зе Сэсайети оф Артс» с намерением запатентовать свою идею, явно не осознавая, что опоздал на несколько столетий. Бэббидж написал в журнал, указав, что «данный шифр… известен уже очень давно и его можно найти во многих книгах». Твэйтс был непримирим и потребовал от Бэббиджа, чтобы тот раскрыл его шифр. Можно ли было взломать этот шифр или нет, никак не зависело от того, был ли он старым или новым, но любопытство Бэббиджа было достаточно разбужено, чтобы попробовать найти слабое место в шифре Виженера.

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

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

Если для зашифровывания буквы е используется К из слова KING, то в шифртексте будет стоять буква О.

Если для зашифровывания буквы е используется I из слова KING, то в шифртексте будет стоять буква М.

Если для зашифровывания буквы е используется N из слова KING, то в шифртексте будет стоять буква R.

Если для зашифровывания буквы е используется G из слова KING, то в шифртексте будет стоять буква К.

Точно так же различными способами будут зашифрованы и цельте слова: слово the, например, в зависимости от его положения относительно ключевого слова, может быть зашифровано как DPR, BUK, CNO или ZRM. Хотя это и усложняет проведение криптоанализа, но он все же возможен. Следует отметить следующий важный, момент: если существует всего лишь четыре способа зашифровывания слова the, и если в исходном тексте это слово появляется несколько раз, то некоторые из этих четырех возможных зашифрованных слов почти наверняка встретятся в шифртексте. Это показано в следующем примере, где строка The Sun and the Man in the Moon была зашифрована с помощью шифра Виженера и ключевого слова KING.

Слово the зашифровывается как DPR в первом случае и как BUK во втором и третьем случаях. Причина повторного появления BUK заключается в том, что второе the отстоит от третьего the на восемь букв, а восемь кратно длине ключевого слова, которое состоит из четырех букв. Другими словами, второе the было зашифровано в соответствии с тем, как оно располагается относительно ключевого слова (the находится прямо под ING), и к тому моменту, как мы дойдем до третьего the, ключевое слово повторится точно два раза.

Таблица 7 Квадрат Виженера, применяемый совместно с ключевым словом KING. Ключевое слово задает четыре различных шифралфавита, так что буква е может быть зашифрована как О, М, R или К.

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

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

Рис. 13 Шифртекст, созданный с помощью шифра Виженера.

Если мы ограничимся только длинными последовательностями, например, как в данном случае, когда будем рассматривать повторяющиеся последовательности, только если они состоят из четырех или более букв, то вторая причина станет практически нереализуемой и ее можно будет в расчет не принимать. В таблице 8 приведены эти повторяющиеся последовательности, а также указаны интервалы между повторениями этих последовательностей. К примеру, последовательность Е-F-I-Q появляется в первой строке шифртекста, а затем в пятой строке; интервал составляет 95 букв.

Ключевое слово, помимо того что оно служит для преобразования открытого текста в зашифрованный, используется также получателем, чтобы расшифровать зашифрованный текст. Поэтому, если бы мы смогли определить ключевое слово, то дешифровать текст было бы очень просто. На этом этапе у нас нет пока достаточно информации, чтобы подобрать ключевое слово, но таблица 8 дает несколько очень ценных подсказок о его длине. Здесь перечислены, какие последовательности повторяются и интервал между этими повторениями, а остальная часть таблицы посвящена определению множителей интервала между повторениями — чисел, на которые можно разделить нацело интервал между повторениями.

Например, последовательность W-C–X-Y-M повторяется через 20 букв, так что множителями будут числа 1, 2, 4, 5, 10 и 20, поскольку на них 20 делится без остатка. Эти множители означают наличие шести возможностей:

(1) Длина ключа составляется 1 букву, и он повторяется 20 раз.

(2) Длина ключа составляется 2 буквы, и он повторяется 10 раз.

(3) Длина ключа составляется 4 буквы, и он повторяется 5 раз.

(4) Длина ключа составляется 5 букв, и он повторяется 4 раза.

(5) Длина ключа составляется 10 букв, и он повторяется 2 раза.

(6) Длина ключа составляется 20 букв, и он повторяется 1 раз.

Первая возможность может быть исключена, так как ключ, длина которого составляет всего 1 букву, сразу же приводит к одноалфавитному шифру; для шифрования всего текста будет использоваться только одна строка квадрата Виженера, и шифралфавит не будет меняться. Крайне маловероятно, чтобы криптограф так поступил. Чтобы показать все другие возможности, в соответствующей колонке таблицы 8 поставлен символ Ѵ. Каждый символ Ѵ указывает возможную длину ключа.

Чтобы определить, какова длина ключа, то есть будет ли она составлять 2,4, 5,10 или 20 букв, нам понадобится рассмотреть множители и всех остальных интервалов между повторениями. Поскольку, по всей видимости, длина ключевого слова составляет 20 букв или меньше, в таблице 8 для всех этих интервалов указаны те множители, которые не превышают 20. Здесь явно прослеживается тенденция делимости интервалов на 5. Фактически на 5 делятся все интервалы. Первая повторяющаяся последовательность, Е-F-I-Q, может быть объяснена следующим образом: ключевое слово длиной 5 букв девятнадцать раз повторяется между первой и второй последовательностями. Вторая повторяющаяся последовательность, Р-S-D-L-Р, может быть объяснена тем, что между первой и второй последовательностями ключевое слово длиной 5 букв повторилось только один раз.

Третья повторяющаяся последовательность, W-С-Х-Y-М, может быть объяснена тем, что ключевое слово длиной 5 букв между первой и второй последовательностями повторилось четыре раза. Четвертая повторяющаяся последовательность, Е-Т-R-L, может быть объяснена тем, что ключевое слово длиной 5 букв между первой и второй последовательностями повторилось двадцать четыре раза. Короче говоря, все указывает на наличие пятибуквенного ключевого слова.

Предположим, что длина ключевого слова действительно составляет 5 букв; тогда следующий этап будет заключаться в том, чтобы найти эти буквы. Пока обозначим ключевое слово в виде L1-L2-L3-L4-L5, где L1 будет первой буквой ключевого слова, L2 — второй, и так далее. Тогда процесс шифрования начнется с зашифровывания первой буквы открытого текста в соответствии с первой буквой ключевого слова Буква определяет строку квадрата Виженера и, тем самым, задает одноалфавитный шифр замены для первой буквы открытого текста. Однако когда наступает время для зашифровывания второй буквы открытого текста, криптограф должен использовать L2, чтобы определить другую строку квадрата Виженера, задавая тем самым уже иной одноалфавитный шифр замены. Третья буква открытого текста будет зашифровываться в соответствии с L3, четвертая — в соответствии с L4, а пятая — в соответствии с L5. Каждая буква ключевого слова задает для шифрования свой отличающийся шифралфавит. Но затем шестая буква открытого текста будет опять зашифровываться в соответствии с L1, седьмая буква — в соответствии с L2, и далее цикл повторяется. Другими словами, в нашем случае многоалфавитный шифр состоит из пяти одноалфавитных шифров, причем каждый одноалфавитный шифр отвечает за шифрование 1/5 части всего сообщения. Но самое главное состоит в том, что нам уже известно, как проводить криптоанализ одноалфавитных шифров.

Таблица 8 Повторяющиеся последовательности и интервалы между ними в шифртексте.

Поступим следующим образом. Мы знаем, что одна из строк квадрата Виженера, определяемая буквой задает шифралфавит, которым зашифрованы 1-я, 6-я, 11-я, 16-я… буквы сообщения. Поэтому если возьмем 1-ю, 6-ю, 11-ю, 16-ю… буквы шифртекста, то мы сможем применить добрый, старый частотный анализ для определения данного шифралфавита. На рисунке 14 показано частотное распределение букв, которые стоят на 1-м, 6-м, 11-м, 16-м… местах шифртекста; это буквы W, I, R, Е… Здесь следует напомнить, что каждый шифралфавит в квадрате Виженера — это просто обычный алфавит, сдвинутый на 1… 26 позиций. Поэтому частотное распределение на рисунке 14 должно иметь те же особенности, что и частотное распределение стандартного алфавита, за исключением того, что оно будет сдвинуто на некоторое расстояние. Сравнивая распределение L1 со стандартным распределением, можно определить величину сдвига. На рисунке 15 показано стандартное частотное распределение для отрывка английского открытого текста.

В стандартном распределении имеются пики, плато и впадины, и, чтобы сравнить его с распределением шифра L1 поищем наиболее заметные особенности и их комбинации. Так, весьма характерную особенность в стандартном распределении (рис. 15) составляют три пика у R-S-Т и длинная ложбина справа от них, которая захватывает шесть букв от U до Z включительно. В распределении (рис. 14) есть только один похожий участок с тремя пиками у V-W-Х и последующей впадиной, простирающейся вдоль шести букв от Y до D. А это означает, что все буквы, зашифрованные в соответствии с L1 были сдвинуты на четыре позиции, и L1 определяет шифралфавит, который начинается с Е, F, G, Н…, то есть первая буква ключевого слова, L1 это, по всей видимости, Е. Данное предположение может быть проверено путем сдвига распределения на четыре буквы назад и сравнения его со стандартным распределением. На рисунке 16 даны для сравнения оба распределения. Совпадение между основными пиками очень хорошее, так что нет никаких сомнений, что ключевое слово действительно начинается с буквы Е.

Рис. 14 Частотное распределение букв в зашифрованном с помощью шифралфавита L1 тексте (число появлений букв).

Рис. 15 Стандартное частотное распределение букв (число появлений букв на основе отрывка открытого текста, содержащего то же самое количество букв, что и в шифртексте).

Подведем итоги. Поиск повторений в шифртексте позволил нам определить длину ключевого слова, которое, как оказалось, состоит из пяти букв. Это позволило нам разделить шифртекст на пять частей, где каждая часть зашифрована с помощью шифра одноалфавитной замены, который определяется одной буквой ключевого слова. При анализе той части шифртекста, которая была зашифрована в соответствии с первой буквой ключевого слова, мы смогли показать, что эта буква, L1, является, по-видимому, буквой Е. Этот же прием применяется и для поиска второй буквы ключевого слова. Выясняется распределение частот появления 2-й, 7-й, 12-й, 17-й… букв в шифртексте, и получившееся распределение, приведенное на рисунке 17, снова сравнивается со стандартным распределением, после чего находится величина сдвига.

Это распределение анализировать сложнее. Явных кандидатов для трех соседствующих пиков, которые соответствуют буквам R-S-T, не находится. Однако отчетливо видна ложбина, которая тянется от G до L и которая, видимо, соответствует ложбине, идущей от U до Z в стандартном распределении. Если это так, то можно ожидать, что пики, соответствующие R-S-T, появятся у букв D, Е и F, однако пика у буквы Е не наблюдается.

Рис. 16 Распределение L1 сдвинутое на четыре буквы назад (вверху), в сравнении со стандартным частотным распределением (внизу). Совпадают все основные пики и впадины.

Рис. 17 Частотное распределение букв в зашифрованном с помощью шифралфавита L2 тексте (число появлений букв).

Забудем пока об отсутствующем пике, посчитав его статистическим выбросом, и продолжим наш анализ, предполагая, что ложбина от G до L как раз и является той самой отличительной особенностью. Отсюда следует, что все буквы, зашифрованные в соответствии с L2, были сдвинуты на двенадцать позиций, и L2 определяет шифралфавит, который начинается с М, N, О, Р…, то есть второй буквой ключевого слова, L2, является М. Данное предположение вновь может быть проверено путем сдвига распределения L2 на двенадцать букв назад и сравнения его со стандартным распределением.

На рисунке 18 даны для сравнения оба распределения. Совпадение между основными пиками очень хорошее, так что нет никаких сомнений, что второй буквой ключевого слова действительно является м.

Я не буду продолжать дальнейшее рассмотрение; достаточно сказать, что при анализе 3-й, 8-й, 13-й… букв третьей буквой ключевого слова будет буква I, при анализе 4-й, 9-й, 14-й… букв четвертой буквой ключевого слова будет L, а при анализе 5-й, 10-й, 15-й… букв пятой буквой ключевого слова будет Y. Ключевым словом является EMILY. Теперь можно завершить криптоанализ. Первая буква шифртекста — W, и она была зашифрована в соответствии с первой буквой ключевого слова Е. Будем действовать в обратном порядке:

Рис. 18 Распределение L2, сдвинутое назад на двенадцать букв (вверху), в сравнении со стандартным частотным распределением (внизу). Совпадают все основные пики и впадины

возьмем квадрат Виженера и поищем W в ряду, начинающемся с буквы Е, а затем посмотрим, какая буква находится вверху этого столбца. Этой буквой будет буква в, которая и будет первой буквой открытого текста. Повторяя эту операцию шаг за шагом, мы получим открытый текст, который начинается следующим образом: sittheedow-nandhavenoshamecheekbyjol… Вставив в соответствующих местах пробелы между словами и знаки пунктуации, приведем открытый текст к окончательному виду:

Sit thee down, and have no shame,

Cheek by jowl, and knee by knee:

What саге I for any name?

What for order or degree?

Let me screw thee up a peg:

Let me loose thy tongue with wine:

Callest thou that thing a leg?

Which is thinnest? thine or mine?

Thou shalt not be saved by works:

Thou hast been a sinner too:

Ruined trunks on withered forks,

Empty scarecrows, I and you!

Fill the cup, and fill the can:

Have a rouse before the morn:

Every moment dies a man,

Every moment one is born.

Это стихи из поэмы Альфреда Теннисона «Видение греха». Ключевым словом оказалось первое имя жены Теннисона, Эмилии Селлвуд. Я выбрал в качестве примера криптоанализа отрывок этой замечательной поэмы, так как именно он побудил Бэббиджа направить письмо великому поэту. Будучи строгим ревнителем статистики и составителем таблиц смертности, Бэббидж не был согласен со строками: «Каждую минуту умирает человек, Но каждую минуту человек рождается», — последними строками приведенного выше незашифрованного текста. И он предложил подправить «во всем остальном превосходную» поэму Теннисона:

Следует указать, что если это было бы так, то тогда численность населения Земли не менялась бы… поэтому я беру на себя смелость предложить, чтобы в следующем издании Вашей поэмы Вы исправили бы эти строчки следующим образом: «Каждую минуту умирает человек, Но 11/16 человека рождается»…На самом деле число настолько длинное, что я не могу записать его в одну строку, но полагаю, что 11/16 будет достаточно точным для поэзии.

Остаюсь в Вашем распоряжении,

Чарльз Бэббидж

По-видимому, успеха во взломе шифра Виженера Бэббидж добился в 1854 году, вскоре после разногласий с Твэйтсом, но о его открытии никто так и не узнал, потому что Бэббидж не опубликовал его. Это обнаружилось только в двадцатом веке, когда ученые принялись разбирать его многочисленные заметки. А тем временем этот же способ независимо от Бэббиджа был найден Фридрихом Вильгельмом Касиски, отставным офицером прусской армии. С 1863 года, когда он опубликовал в «Die Geheimschriften und die Dechiffrirkunst» («Тайнопись и искусство дешифрования») работу о своем крупном открытии в криптоанализе, этот алгоритм известней как «тест Касиски», имя же Бэббиджа и его вклад вспоминают нечасто.

Так почему же Бэббидж не сообщил о том, что он сумел взломать этот имеющий столь важное значение шифр? Несомненно, была у него такая привычка — бросать незавершенными значительные и многообещающие начинания и не сообщать о своих открытиях, и в данном случае это могло бы являться просто еще одним примером его равнодушного к этому отношения. Имеется, однако, и другое объяснение. Бэббидж сделал свое открытие вскоре после того, как разразилась Крымская война, а в одной из теорий было выдвинуто предположение, что оно давало Британии явное преимущество над Россией, ее противником. Вполне возможно, что британская секретная служба потребовала от Бэббиджа, чтобы он сохранил свою работу в секрете, тем самым обеспечив себе девятилетнюю фору перед остальным миром. И если это так, то это полностью соответствует многолетней традиции умалчивания о достижениях в области криптоанализа в интересах национальной безопасности, — обычай, который сохранился и в двадцатом столетии.

От объявлений в газете о розыске родных до кладов

Благодаря достижениям Чарльза Бэббиджа и Фридриха Касиски шифр Виженера более не был безопасным. Теперь, когда криптоаналитики вновь обрели контроль в коммуникационной войне, криптографы не могли гарантировать секретности. Хотя они и пытались разрабатывать новые шифры, но во второй половине девятнадцатого столетия не появилось ничего существенного, и профессиональные криптографы были в смятении. Однако как раз в это же самое время у широкой публики появился огромный интерес к шифрам.

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

По мере того как люди все увереннее выполняли шифрование, они начинали выражать свое умение в криптографии разнообразными способами. Например, юным влюбленным в викторианской Англии часто запрещалось в открытую выражать свои чувства, и они не могли даже переписываться, поскольку их родители могли перехватить письмо и прочитать его. В результате этого влюбленные стали посылать друг другу зашифрованные сообщения посредством газетной колонки частных объявлений. Эти «объявления о розыске родных», как их стали называть, вызвали любопытство криптоаналитиков, которые стали просматривать объявления и старались дешифровать их содержание. Как было известно, не отказывал себе в этом даже Чарльз Бэббидж со своими друзьями* сэром Чарльзом Уитстоном и бароном Леоном Плейфером, которые вместе разработали шифр Плейфера (приведен в Приложении Е). Как-то раз Уитстон расшифровал объявление в «Таймс» от оксфордского студента, который предлагал тайно бежать своей возлюбленной. Спустя несколько дней Уитстон поместил свое собственное сообщение, зашифрованное тем же самым шифром, советуя паре не действовать так бунтарски и поспешно. Вскоре после этого там же появилось и третье сообщение, уже от леди, на сей раз незашифрованое: «Дорогой Чарли, больше не пиши. Наш шифр раскрыт».

Со временем в газетах появлялось всё большее количество разнообразных зашифрованных объявлений. Криптографы начали помещать там зашифрованные сообщения, просто чтобы бросить вызов своим коллегам. В других случаях зашифрованные объявления использовались в целях критики общественных деятелей или организации. Однажды «Таймс» разместила следующее сообщение, содержащее в себе непреднамеренно зашифрованный подтекст: «“Таймс” — это Джеффрис прессы». Газета, по сути, приравняла себя печально известному судье-вешателю семнадцатого века Джеффриру, что означало, что она являлась жестоким, беспощадным печатным органом, который действовал как рупор правительства.

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



Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   10   ...   32


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница