Математики, шпионы и хакеры. Кодирование и криптография - [12]

Фрагмент одного из писем шотландской королевы Марии Стюарт к ее сообщнику Энтони Бабингтону. За это письмо ее в конечном счете осудили на смерть.

Идея Альберти

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

Строка (1) — стандартный алфавит. Строка (2) — первый шифроалфавит. Строка (3) — второй шифроалфавит.

Для зашифровки какого-либо сообщения Альберти предложил чередовать два шифроалфавита. Например, в случае слова SHEEP («овца») шифр для первой буквы берется из первого алфавита (V), а шифр для второй буквы — из второго алфавита (L), и так далее. В нашем примере слово SHEEP будет зашифровано как VLHCS. Преимущество такого алгоритма полиалфавитного шифрования по сравнению с предыдущими видно сразу: буква Е исходного слова шифруется двумя различными способами — как Н и С. Чтобы еще больше запутать криптоаналитика, пытающегося расшифровать этот текст, одна и та же буква криптограммы соответствует двум разным буквам оригинального текста. Частотный анализ, таким образом, теряет значительную часть своей силы. Альберти так нигде и не записал свои идеи, поэтому шифр был позже разработан примерно в одно и то же время, но независимо друг от друга двумя учеными: немцем Иоганном Тритемием и французом Блезом де Виженером.

Квадрат Виженера

В шифре Цезаря используется одноалфавитный шифр подстановки; один шифроалфавит соответствует алфавиту открытого текста, так что одна зашифрованная буква соответствует одной и той же букве исходного текста. (В классическом шифре Цезаря буква D всегда соответствует букве А, Е — В, и так далее).

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

Обратите внимание на симметрию в расположении букв. Пара (A, R) = (R, А), и это же соотношение справедливо для всех букв.

Мы видим, что квадрат Виженера содержит стандартный алфавит из n букв, повторяющийся n раз с различными увеличивающимися параметрами. Так, первый шифроалфавит получается применением шифра Цезаря с параметрами а = 1 и b = 2; второй — эквивалентен шифру Цезаря с Ь = 3 и так далее. Ключом к квадрату Виженера является правило для каждой буквы, которое указывает, на сколько строк вниз надо спуститься, чтобы найти зашифрованное значение, соответствующее этой букве. Простейший ключ состоит из движения вниз на одну строку при переходе от одной буквы исходного сообщения к другой.

Таким образом, наша классическая фраза VENI VIDI VICI будет зашифрована следующим образом:

Для шифрования первой V мы найдем соответствующую букву в строке 2: W.

Для шифрования Е мы найдем соответствующую букву в строке 3: G.

Для шифрования N мы найдем соответствующую букву в строке 4: Q.

I (строка 5): М.

V (строка 6): А.

I (строка 7): О.

D (строка 8): К.

I (строка 9): Q.

V (строка 10): Е.

I (строка 11): S.

С (строка 12): N.

I (строка 13): U.

* * *

ИГРА С ДИСКАМИ

На практике для полиалфавитного шифрования используется устройство, известное как шифровальный диск Альберти. Этот портативный прибор состоит из двух концентрических дисков: один — фиксированный, с выгравированным на нем стандартным алфавитом, второй — подвижный, с другим алфавитом. Отправитель, поворачивая подвижный диск, может сопоставить стандартный алфавит с разными шифроалфавитами в зависимости от числа поворотов диска, максимальное количество которых равно числу букв используемого алфавита. Шифр, полученный с помощью диска Альберти, очень устойчив к частотному анализу. Чтобы расшифровать сообщение, получатель должен сделать то же число оборотов, что и отправитель. Безопасность этого шифра, как всегда, зависит от сохранения в тайне кода, а именно — от расположения алфавита на подвижном диске плюс число необходимых поворотов. Диск Альберти с одним подвижным кольцом, на котором выгравирован стандартный алфавит, дает шифр Цезаря при каждом повороте. Аналогичные устройства использовались во время Гражданской войны в США, и сегодня их можно встретить в детских шпионских играх.

Диск Альберти, используемый Конфедерацией во время американской гражданской войны.

В результате наша фраза превратится в WGQM AOKQ ESNU. При этом повторяющиеся буквы исходного сообщения исчезнут. Однако каждый криптограф стремится к тому, чтобы генерировать шифры, которые легко запомнить, распространять и обновлять. Тогда стали брать ключевые слова с таким же или меньшим количеством букв, что и в исходном сообщении, чтобы строить более короткие и легкие в использовании квадраты Виженера. Ключевое слово дает первые буквы каждой строки (см. стр. 47), и строки продолжаются остатком алфавита (как они представлены в полном квадрате). Затем ключевое слово, повторенное нужное количество раз, пишется под буквами сообщения, которое необходимо было зашифровать. Буква ключевого слова под каждым символом сообщения подсказывала криптографу строку в матрице, из которой нужно было взять зашифрованное значение этой буквы.