наибольших значений pk, 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) в приведенной выше таблице), то в результате этого процесса сдвиг для какой-либо группы может оказаться определенным неправильно либо процесс может вообще не сойтись (будут отброшены все варианты). В таком случае следует заново определить величину сдвига для наихудшей группы (определяемой, например, по наибольшему среднему месту для сдвигов относительно этой группы), учитывая большее число кандидатов.

После определения сдвигов следует найти ключевое слово, как описано в основном тексте, рассматривая все слова вида 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⁻⁵¹ до 10⁻³⁶. Если на вашей ЭВМ такие числа непредставимы, то вычислите логарифмы 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.

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

Примечания

1

Семь лет — традиционный срок ученичества в средневековых ремесленных мастерских Англии. — Прим. перев.

(обратно)

2

Чиппендейл (Chippendale) Томас (1718–1779) — английский мебельный мастер. Сочетал функциональную целесообразность форм с изяществом линий. — Прим. перев.

(обратно)

3

Мы называем нашего читателя «студентом». Это, однако, не должно отпугнуть тех, кто не учится в соответствующем учебном заведении. Научиться программировать можно и в одиночку; желая вдохновить тех, кто вынужден осваивать предмет самостоятельно, мы предлагаем им для решения набор задач, достаточно близких к реальным. Учтите, однако, что осваивать предмет под руководством преподавателя все же неизмеримо легче.

(обратно)

4

Предлагаются такие общедоступные языки, как Фортран, Кобол, Алгол, язык ассемблера, APL, XPL, PL/I, Бейсик, Паскаль, Лисп, Снобол и др. Это не означает, что не подходит какой-нибудь менее известный или менее распространенный язык, тем более что в наших рекомендациях мы руководствовались собственными вкусами. В любом случае приветствуется использование языков и трансляторов более высокого уровня, типа WATFIV, PL/C или SPITBOL, требующих и более серьезного к себе отношения. Можно также использовать задачу для изучения нового языка («полное погружение» — метод тяжелый, но эффективный).

(обратно)

5

На русском языке вышли 3 тома (как, впрочем, и на английском). — Прим. перев.

(обратно)

6

Один из способов сокращения памяти, требуемой для запоминания позиций, состоит в том, чтобы хранить позицию в виде массива битов, отводя для каждой клетки один бит (а не слово памяти). Как это ни странно, такой способ позволяет также получить выигрыш во времени, если воспользоваться командами поразрядных логических операций над векторами битов, имеющихся в системах команд почти всех ЭВМ и в некоторых языках программирования высокого уровня (например, в PL/I). Если обозначить через р исходную позицию, через p1, p2, …, p8 — позиции, сдвинутые на одну клетку в направлении всех соседей клетки, и через r — новую позицию, то каждый бит r будет однозначно определяться битами с тем же номером в позициях p1, p2, …, p8, т. е. будет логической функцией от них. Всякую логическую функцию можно, как известно, записать с помощью элементарных логических операций: ∧ (логическое И), ∨ (логическое ИЛИ), ⊕ (сложение по модулю два) и ¬ (логическое отрицание). Задача состоит в том, чтобы выразить r через p1, p2, …, p8 экономно, с использованием возможно меньшего числа