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

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

Инструментовка. Эта задача прямо-таки создана для языка типа Снобол, в котором средства работы с текстовыми данными сочетаются с простыми арифметическими операциями. Хорошим кандидатом может быть и какой-нибудь другой язык, с более широким диапазоном алгебраических вычислений и с достаточными средствами обработки текстовых данных, например PL/I, Паскаль или XPL. Но какой бы язык вы ни выбрали, постарайтесь избежать представления литер целыми числами; требования машинного представления не должны навязывать некрасивое, путаное решение задачи.

Длительность исполнения. Одному исполнителю на 2 недели.

* Партия переводчика. При переводе на русский язык зашифрованного примера надо было сначала расшифровать его. Попытка сделать это с помощью описанной процедуры не привела к успеху. После небольшого размышления стало ясно, что наш ключ не подходит потому, что он от другого замка! Действительно, предлагаемый автором способ определения относительных сдвигов столбцов с помощью величин R_{i, j, r} исходит из того, что два столбца отличаются, кроме случайных отклонений, циклическим сдвигом на величину, равную разности номеров двух букв ключевого слова. Это свойство будет иметь место, если несколько изменить способ шифрования. В нашем случае вместо R_{i, j, r} следует использовать числа p_{i, j, r}, вычисляемые, как описано ниже.

Пусть число букв алфавита равно n. Будем обозначать i-ю букву алфавита x_i или y_i в зависимости от того, идет речь об исходном тексте или о зашифрованном. Нам известны средняя частота p_i = = p(x_i) появления i-й буквы в русском языке, число f_{k, i} появлений i-й буквы в k-й группе зашифрованного текста, общее число N_k букв в k-й группе. Определим вероятности p_k(y_j|x_i) появления фактического числа букв f_{k, j}, если буква y_j в k-й группе обозначает букву x_i исходного текста. Эти вероятности подчиняются биномиальному распределению.

Далее найдем по формуле Байеса вероятности p_k(x_i|y_j) того, что буква у_j в k-й группе означает букву x_i исходного текста. Априорные вероятности гипотез примем равными 1/n.

Рассмотрим теперь пару групп (столбцов табл. 24.1) k и l. Будем говорить, что между ними имеется сдвиг r, если каждой букве y_j зашифрованного текста в 1-й группе соответствует буква исходного текста на r большая (по модулю n), чем в k-й группе. Это означает, что в ключевом слове 1-я буква на r меньше k-й. Для оценки вероятностей p_{k, l, r} того, что между k-й и l-й группами имеется сдвиг r, вычислим величины

Символы ?, ? означают сложение и вычитание по модулю n. Величина рк, i г есть вероятность фактического распределения числа появлений букв при условии, что имеет место сдвиг r. Здесь не учитывается, что разные y_j соответствуют разным Значения p_{k, l, r} получаются по формуле Байеса

Фактический сдвиг r(k, l) между k-й и l-й группами должен иметь довольно большую вероятность p_{k, l, r}. Но насколько большую? В следующей таблице приведены данные о расшифровке оригинала примера.

В клетке с координатами k, l указано, какое место в порядке убывания p_{k, l, r} для фиксированных k и l занимает фактический сдвиг r(k, l). Видно, что за двумя исключениями номер места не превышает шести. Таким образом, величины сдвигов r(k, l) следует искать среди тех, которые дают 6–7 наибольших значений p_{k, l, r} для данных k и l. Для выбора из них фактических величин сдвига следует воспользоваться согласованностью сдвигов r(k, l) ? r(l, n) = r(k, m). Складывая всех кандидатов для r(1, 2) с r(2, 3) и проверяя, находится ли результат среди кандидатов для r(1, 3), можно отбросить большую часть вариантов. Затем следует аналогично определить r(1, 4), учитывая r(2, 4) и r(3, 4), и т. д. Этот перебор легко провести вручную, если число кандидатов для каждого r(k, l) не более 8. Поскольку возможны исключительные случаи (r(3, 5) и r(4, 5) в приведенной выше таблице), то в результате этого процесса сдвиг для какой-либо группы может оказаться определенным неправильно либо процесс может вообще не сойтись (будут отброшены все варианты). В таком случае следует заново определить величину сдвига для наихудшей группы (определяемой, например, по наибольшему среднему месту для сдвигов относительно этой группы), учитывая большее число кандидатов.

После определения сдвигов следует найти ключевое слово, как описано в основном тексте, рассматривая все слова вида x_a, x_{a ? r(1, 2)}, x_{a ? r(1, 3)}, … (а = 1, …, n). Возможно, для получения осмысленного слова придется изменить одну из букв. Определив ключевое слово, находим окончательные величины сдвигов.

Теперь для определения перестановки вычислим вероятности p(x_i|y_j) того, что буква y_j в зашифрованном тексте соответствует букве x_i в первой группе, x_{i ? r(1, 2)} — во второй и т. д.:

(r(1, 1) полагаем равным нулю, d — число групп)

Фактические значения 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 ^?51 до 10^?36. Если на вашей ЭВМ такие числа непредставимы, то вычислите логарифмы log p?_{k, l, r}. Числа p_{k, l, r} и p(x_i|y_j) можно не