После определения сдвигов следует найти ключевое слово, как описано в основном тексте, рассматривая все слова вида xa, xa ⊖ r(1, 2), xa ⊖ r(1, 3), … (а = 1, …, n). Возможно, для получения осмысленного слова придется изменить одну из букв. Определив ключевое слово, находим окончательные величины сдвигов.
Теперь для определения перестановки вычислим вероятности p(xi|yj) того, что буква yj в зашифрованном тексте соответствует букве xi в первой группе, xi ⊕ r(1, 2) — во второй и т. д.:
(r(1, 1) полагаем равным нулю, d — число групп)
Фактические значения xi должны давать большие значения p(xi|yj). Числа p(xi|yj) дают для определения перестановки существенно более четкую информацию, чем числа pk,l, r для определения сдвигов. Оказывается, что при длине текста около 700 букв для большинства букв yj зашифрованного текста соответствующие им xi дают максимальное значение p(xi|yj). Перестановка легко уточняется, если начать расшифровку, учитывая осмысленность получаемого текста.
При реализации этого алгоритма на ЭВМ следует иметь в виду, что числа p̃k, l, r могут оказаться весьма малыми. Так, при расшифровке оригинала примера они лежали в диапазоне от 10−51 до 10−36. Если на вашей ЭВМ такие числа непредставимы, то вычислите логарифмы log p̃k, l, r. Числа pk, l, r и p(xi|yj) можно не вычислять, воспользовавшись вместо них pk, l, r и p(xi|yj), отличающимися постоянным множителем.
Этот способ позволил расшифровать английский оригинал примера. Удастся ли вам проделать то же с русским текстом?
Гэн (Gaines H. F.). Cryptanalysis. Dover, New York, NY, 1956.
Элементарная книга, которая обычно прежде всех других попадает в руки любителям тайнописи. Здесь указано недорогое издание в бумажном переплете, содержащее подробные методы раскрытия для довольно сложных шифров. Оригинал книги вышел в свет достаточно давно, поэтому в ней вы не найдете обсуждения математических методов, имеющихся в книге Синкова, но классические методы описаны хорошо. Приводится несколько полезных таблиц.
Гарднер (Gardner М.). Mathematical Games. Scientific American, August, 1977, pp. 120–124.
Гарднер сообщает о новом, практически нераскрываемом шифре. Метод шифрования основан на свойствах очень больших простых чисел, а для зашифровки необходима ЭВМ. Если вы реализуете задачу гл. 22, то будете иметь средство для создания идеально секретного метода коммуникации.
Кан (Kahn D.). The Code Breakers. Macmillan, New York, NY, 1967.
Кан написал очень ясную книгу по криптографии. Хотя после 1967 г. стали известны некоторые новые интересные материалы о второй мировой войне, тем не менее книга содержит все, что может быть интересно любителю, об истории и методах тайнописи. В книге прекрасная библиография,
Синков (Sinkov A.). Elementary Cryptanalysis — A Mathematical Approach. Random House, New York, NY, 1968.
Очень простая книга по анализу криптограмм. Содержит некоторые математические обоснования. По-видимому, Управлению национальной безопасности известны и более прогрессивные методы тайнописи, но оно, естественно, об этом не распространяется. Рассуждения, приведенные в этой главе, взяты из материалов Синкова.
ТЕМЫ ДЛЯ КУРСА ПО КОМПИЛЯТОРАМ
Для того чтобы охватить полный курс по компиляторам, темы для этюдов собраны в одно место. Любой студент, справившийся со всеми четырьмя этюдами, хорошо усвоит как практические, так и теоретические вопросы создания трансляторов. Если выполнять этюды в порядке их следования, то результаты каждого из них могут служить входными данными для последующих. Например, для тестирования компилятора можно применить эмулятор машины и загрузчик. Не каждый студент возьмется, вероятно, в одиночку за изготовление компилятора или загрузчика, а вот интерпретатор Трака или моделирование компьютера под силу и одному исполнителю. Все четыре темы могут быть исполнены за полтора — два семестра при соответствующем руководстве.