Этюды для программистов

Фактические значения x_i должны давать большие значения p(x_i|y_j). Числа p(x_i|y_j) дают для определения перестановки существенно более четкую информацию, чем числа p_{k,l, r} для определения сдвигов. Оказывается, что при длине текста около 700 букв для большинства букв y_j зашифрованного текста соответствующие им x_i дают максимальное значение p(x_i|y_j). Перестановка легко уточняется, если начать расшифровку, учитывая осмысленность получаемого текста.

При реализации этого алгоритма на ЭВМ следует иметь в виду, что числа p̃_{k, l, r} могут оказаться весьма малыми. Так, при расшифровке оригинала примера они лежали в диапазоне от 10⁻⁵¹ до 10⁻³⁶. Если на вашей ЭВМ такие числа непредставимы, то вычислите логарифмы log p̃_{k, l, r}. Числа p_{k, l, r} и p(x_i|y_j) можно не вычислять, воспользовавшись вместо них p_{k, l, r} и p(x_i|y_j), отличающимися постоянным множителем.

Этот способ позволил расшифровать английский оригинал примера. Удастся ли вам проделать то же с русским текстом?

Литература

Гэн (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.

Очень простая книга по анализу криптограмм. Содержит некоторые математические обоснования. По-видимому, Управлению национальной безопасности известны и более прогрессивные методы тайнописи, но оно, естественно, об этом не распространяется. Рассуждения, приведенные в этой главе, взяты из материалов Синкова.

ТЕМЫ ДЛЯ КУРСА ПО КОМПИЛЯТОРАМ

Для того чтобы охватить полный курс по компиляторам, темы для этюдов собраны в одно место. Любой студент, справившийся со всеми четырьмя этюдами, хорошо усвоит как практические, так и теоретические вопросы создания трансляторов. Если выполнять этюды в порядке их следования, то результаты каждого из них могут служить входными данными для последующих. Например, для тестирования компилятора можно применить эмулятор машины и загрузчик. Не каждый студент возьмется, вероятно, в одиночку за изготовление компилятора или загрузчика, а вот интерпретатор Трака или моделирование компьютера под силу и одному исполнителю. Все четыре темы могут быть исполнены за полтора — два семестра при соответствующем руководстве.

25. Уча — учимся, или... МОДЕЛИРОВАНИЕ БОЛЬШОГО КОМПЬЮТЕРА

Если вы читаете эти строки, у вас почти наверняка есть под рукой подходящий компьютер. Возможно, покажется несколько странным, зачем нужно писать программу, делающую буквально то же самое, что уже умеет делать компьютер (если он исправен). Но уверены ли вы, что в точности знаете, что ваша ЭВМ в состоянии делать? Да и позволят ли вам другие пользователи достаточно долго узурпировать машину, чтобы изучить все черты ее характера? Билл Мак-Киман утверждает, что никогда не следует браться за большой проект, зависящий от структуры машины вроде компилятора или операционной системы, до тех пор, пока не создан имитатор. Но как это всегда бывает, чтобы чему-то научиться, надо научить этому кого-нибудь другого (скажем, компьютер?!).