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

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

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

Допустим, что у нас есть открытый текст, состоящий из 1 000 букв и зашифрованный с помощью шифра Виженера; проведем криптоанализ имеющегося шифртекста. Если длина ключевого слова, используемого для шифрования открытого текста составляет всего 5 букв, то на завершающем этапе криптоанализа потребуется провести частотный анализ 5 наборов из 200 букв, что не представляеттруда. Но если ключевое слово состоит из 20 букв, то на завершающем этапе необходимо будет провести частотный анализ 20 наборов из 50 букв, что уже значительно сложнее. Если же ключевое слово состоит из 1000 букв, то вы столкнетесь с тем, что придется провести частотный анализ 1000 наборов, каждый из которых состоит из 1 буквы, что совершенно невыполнимо. Другими словами, если длина ключевого слова (или ключевой фразы) совпадает с длиной сообщения, то криптоаналитический метод, разработанный Бэббиджем и Касиски не работает.

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

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

Этот новый способ криптоанализа начинается с предположения, что в шифртексте содержатся общеупотребительные слова, к примеру, the. Далее, как показано ниже, мы произвольным образом подставляем the в различные места в открытом тексте и определяем, какими должны быть буквы ключа, чтобы преобразовать the в соответствующий шифртекст. Итак, мы решили, что the будет являться первым словом открытого текста. Первая буква ключа будет зашифровывать t в V. Чтобы определить первую букву ключа, возьмем квадрат Виженера и будем двигаться сверху вниз по столбцу, начинающемуся с буквы t, пока не дойдем до V; буква, с которой начинается эта строка — С. Повторим этот процесс для h и е, которые были зашифрованы как Н и R соответственно; в конечном счете мы получим возможные значения первых трех букв ключа — CAN. Все это получено в предположении, что слово the является первым словом открытого текста. Подставим the в несколько других мест и вновь поищем соответствующие буквы ключа. (Вы можете проверить соответствие между каждой буквой открытого текста и буквой шифртекста, обратившись к квадрату Виженера в таблице 9.)

Мы проверили три слова the в трех произвольно выбранных местах шифртекста и выдвинули три предположения относительно элементов определенных частей ключа. Можем ли мы сказать, что какое-нибудь из слов the стоит в нужном месте? Мы предполагаем, что ключ состоит из осмысленных слов; попробуем использовать это в наших целях. Если the стоит не на своем месте, то это приведет, скорее всего, к тому, что ключ будет состоять из хаотичного набора букв. Если же оно стоит в нужном месте, то буквы ключа должны иметь какой-то смысл. Например, первое the дает буквы ключа CAN, что обнадеживает, поскольку это вполне нормальный английский слог. Так что возможно, что это слово the стоит на своем месте. Второе the дает BSJ, — весьма странное сочетание согласных, что позволяет предположить, что второе the, скорее всего, неверно. Для третьего the получается YPT, — редко встречающийся слог, но ею все же стоит проверить. Если YPT действительно является частью ключа, то оно должно находиться внутри более длинного слова; такими словами могут быть только APOCALYPTIC, CRYPT и EGYPT и производные от этих слов. Как мы сможем определить, является ли одно из этих слов частью ключа?

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

Если слово не является частью ключа, то, скорее всего, это опять-таки приведет к тому, что фрагмент открытого текста будет состоять из хаотичного набора букв; если же оно является частью ключа, то получающийся открытый текст должен иметь определенный смысл. При использовании в качестве части ключа слова APOCALYPTIC, получающийся открытый текст состоит из абсолютно бессмысленного набора букв. При использовании в качестве части ключа слова CRYPT, в открытом тексте получается cithe, что, в общем-то, не является невозможным куском открытого текста. Однако если в качестве части ключа использовать EGYPT, то при этом получается atthe — более обещающая комбинация букв, которая, видимо, представляет собой слова at the.

Предположим пока, что скорее всего в качестве части ключа используется EGYPT. Возможно, что в качестве ключа используется перечень стран. А это означает, что CAN, часть ключа, которая соответствует первому the, является началом слова CANADA. Мы можем проверить эту гипотезу, предполагая, что CANADA, как и EGYPT, являются частями ключа, если откроем бóльший фрагмент открытого текста:

Похоже, что наше предположение имеет смысл. CANADA означает, что открытый текст начинается с themee, что, по-видимому, является началом the meeting. Теперь, когда мы определили новые буквы открытого текста, ting, мы можем найти соответствующую им часть ключа; это будет BRAZ, которое, несомненно, является началом слова BRAZIL. Используя в качестве ключа комбинацию CANADABRAZILEGYPT, мы получим следующее: the meeting is at the????.

Чтобы найти завершающее слово открытого текста — место встречи, — лучше всего завершить составление ключа путем проверки перебором названий всех возможных стран, оценивая получающийся при этом открытый текст. Осмысленный открытый текст получается только в случае, когда конечным элементом ключа будет слово CUBA:

Таблица 9 Квадрат Виженера.

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

Когда Первая мировая война уже приближалась к концу, майор Джозеф Моборн, руководитель криптографического исследовательского подразделения армии США, ввел понятие случайного ключа, т. е. такого ключа, который состоит не из распознаваемого набора слов, а из случайной комбинации букв. Он высказывался за применение таких случайный ключей, используемых как часть шифра Виженера, для обеспечения беспрецедентной степени стойкости. Первым этапом в системе Моборна была подготовка толстого блокнота, состоящего из сотен бумажных листов; на каждом листе находится уникальный ключ в виде случайной последовательности строчек букв. Подготавливаются два экземпляра блокнота, один для отправителя, а второй — для получателя. Чтобы зашифровать сообщение, отправитель применял шифр Виженера, пользуясь первым листом блокнота в качестве ключа. На рисунке 30 показаны три листа из такого блокнота (на самом деле, на каждом листе содержатся сотни букв) и сообщение, зашифрованное с использованием случайного ключа, находящегося на первом листе. Получатель сможет легко расшифровать шифртекст, пользуясь идентичным ключом и шифром Виженера. После того как сообщение было успешно отправлено, получено и расшифровано, оба — и отправитель, и получатель — уничтожают лист, использованный в качестве ключа, чтобы никогда уже больше им не пользоваться. При шифровании очередного сообщения применяется следующий случайный ключ из блокнота, который в дальнейшем также уничтожался, и так далее. Поскольку каждый лист используется только один раз, эта система известна как одноразовый шифрблокнот, или шифрблокнот одноразового назначения[15].