Многоалфавитные шифры замены
В европейских странах многоалфавитные шифры были изобретены в эпоху Возрождения, когда развитие торговли потребовало надежных способов защиты информации. Шифр многоалфавитной замены впервые был предложен Леоном Батиста Альберти (1404–1472), итальянским ученым, архитектором, писателем и музыкантом, который в 1466 г. представил трактат о шифрах, где рассматривались различные способы шифрования, в том числе маскировка открытого текста в некотором вспомогательном тексте. Альберти изобрел, по его собственным словам, «шифр, достойный королей», – многоалфавитный шифр, реализованный в виде шифровального диска. Многоалфавитная замена может быть описана таблицей шифрования. Суть алгоритма шифрования заключается в том, что здесь используется несколько замен в соответствии с ключом. Позднее Альберти изобрел код с перешифровкой. Его изобретение значительно опередило свое время, поскольку такой тип шифра стал применяться в странах Европы только спустя 400 лет.
В 1518 г. в Германии появляется первая печатная книга по криптографии «Полиграфия». Ее автор, аббат Иоганнес Тритемий (1462–1516), развивает идею Альберти о многоалфавитной замене. Следующим этапом развития криптографии можно считать 1563 г., когда в своей книге «О тайной переписке» итальянский естествоиспытатель, основатель одного из первых в мире научных обществ «Секретная академия» Джованни Батиста Порта (1535–1615) описал биграммный шифр, в котором по определенной схеме осуществляется замена не одной буквы, а пары букв одним знаком. В своем исследовании по криптологии Порта впервые произвел систематизацию всех известных в то время шифров.
Еще один известный криптолог XVI века, французский дипломат Блез де Виженер (1523–1596), работавший в Риме, познакомился с трудами Альберти, Тритемия и Порта, детально проверил их идеи и создал на их основе новый шифр полиалфавитной замены с так называемым подвижным ключом. Хотя и Альберти, и Тритемий, и Порта, каждый внесли значительный вклад в изобретение данного шифра, шифр известен как шифр Виженера, в честь ученого, который придал ему окончательный вид.
Дополним естественный порядок букв в алфавите. Будем считать, что за последней буквой алфавита следует его первая буква. Расположим буквы на окружности в естественном порядке по часовой стрелке. Тогда значения относительных порядковых номеров (относительно фиксированной буквы) букв алфавита из n элементов совпадают со значениями всевозможных остатков от деления целых чисел на натуральное число n.
Определение 2.3.4. Число D(N1, N2), равное порядковому номеру буквы с естественным номером N1 относительно буквы с порядковым номером N2 в алфавите, называется знаком гаммы.
Обозначим rm(N) остаток от деления целого N на m Î N. Таким образом, D(N1, N2) = rn(N1 – N2), где n – число букв в алфавите.
Введем следующие обозначения:
N1 [–] N2 = rn(N1 – N2),
N1 [+] N2 = rn(N1 + N2).
Тогда
D(N1, N2) = N1 [–] N2,
N1 = N2 [+] D(N1, N2).
Для рассматриваемого шифра характерно то, что буквы открытого текста, зашифрованные одним и тем же знаком гаммы, по сути, зашифрованы одним и тем же шифром простой замены. Например, ключевая таблица этого шифра простой замены при знаке гаммы, равном 1, для русского алфавита имеет следующий вид:
А Б В … Э Ю Я
Б В Г … Ю Я А
Вторую строку этой ключевой таблицы называют алфавитом шифрования, соответствующим данному знаку гаммы. Поскольку в рассматриваемом шифре возможны все значения гаммы от 0 до 29 (русский алфавит без «Ё», «Й», «Ъ»), то данный шифр можно рассматривать как 30-алфавитный шифр замены. Если каждому из этих алфавитов поставить в соответствие его первую букву, то каждый знак гаммы можно заменить порядковым номером этой буквы. В этом случае ключ рассматриваемого шифра можно взаимно однозначно заменить соответствующим словом в этом же алфавите.
Такой многоалфавитный шифр замены был описан в 1585 г. Блезом де Виженером в его книге «Трактат о шифрах». Взяв за основу тайный алфавит Юлия Цезаря, Виженер построил по изобретенной Тритемием квадратной схеме четырехугольник, который впоследствии получил название таблицы Виженера. Все алфавиты шифрования относительно латинского алфавита были сведены Виженером в таблицу. Над таблицей располагался открытый текст, а слева от нее – ключ. Ниже приведена таблица Виженера для современного латинского алфавита, она составлена из списка 26 алфавитов шифрования, расположенных горизонтально. Каждый алфавит сдвинут относительно находящегося над ним на одну букву влево.
А В С D … W X Y Z
B C D E … X Y Z A
C D E F … Y Z A B
…
Z A B C … V W X Y
Способ зашифровывания с помощью таблиц Виженера заключается в том, что первый из алфавитов соответствует алфавиту открытого текста, а букве ключевого слова соответствует алфавит шифрования из данного списка, начинающийся с этой буквы. Буква зашифрованного текста находится в алфавите шифрования на месте, соответствующем данной букве открытого текста. Рассмотренный ранее шифр Цезаря – частный случай, соответствующий ключевой последовательности, состоящей из одной буквы. Например,
УНИВЕРСИТЕТ – открытый текст,
ВЛТВЛТВЛТВЛ – периодическая ключевая последовательность,
ХЧЫДРВУУГЗЭ – зашифрованный текст.
Простота построения таблиц Виженера делает эту систему привлекательной для практического использования. Виженер использовал идею алгоритма многоалфавитной замены для создания шифрующего устройства, состоящего из вращающихся колес. Изобретенная им система кодов применяется в современных шифровальных машинах. Виженером было издано около 20 книг по криптологии. Среди них уже упоминавшийся «Трактат о шифрах», который содержит разделы, посвященные полиалфавитным системам, методам шифрования, а также созданию ключей. Еще одно важное усовершенствование многоалфавитных шифров замены, состоящее в идее использования в качестве ключа текста самого сообщения или же шифрованного текста, принадлежит Кардано и Виженеру. Такой шифр был назван самоключом.
Итак, первая идея вскрытия зашифрованного текста при таком методе шифрования состоит в использовании вероятного слова, то есть слова, которое с большой вероятностью может содержаться в данном открытом тексте или в ключевой последовательности. Речь идет в том числе и о словах, часто встречающихся в любых открытых текстах, к ним, например, относятся такие слова как «который», «тогда», «что», «если», приставки и предлоги «при», «пре», «под» и т.д. В вышеупомянутой книге «О тайной переписке» Порта привел примеры списков вероятных слов из различных областей знания, существенно предвосхитив то, что впоследствии криптологами было названо методом вероятного слова.
Вторая идея основана на том, что буквы открытого сообщения находятся в тексте на вполне определенных позициях. Если разность номеров их позиций окажется кратной периоду ключевой последовательности, то стоящие на этих позициях буквы будут зашифрованы одним и тем же знаком гаммы. Это означает, что определенные части открытого текста окажутся зашифрованными шифром Цезаря. Эту идею можно использовать для определения периода ключа многоалфавитного шифра замены.
На протяжении почти трехсот лет шифр Виженера считался практически не вскрываемым. Впервые метод разгадки шифра Виженера предложил в 1863 г. в своей книге «Тайнопись и искусство дешифровки» немецкий криптоаналитик и археолог, отставной офицер прусской армии Фридрих Вильгельм Казиски (1805–1881). С тех пор этот алгоритм вскрытия многоалфавитных шифров с ключом неизвестного периода известен как тест Казиски. Данный тест, по сути, заключается в том, что в зашифрованном тексте надо найти пары одинаковых отрезков из не менее чем трех символов, вычислить разности номеров позиций их начал и определить общие делители найденных разностей. Как правило, один из этих общих делителей равен периоду ключевой последовательности. Если нам известна длина ключевой фразы, то можно разбить текст на несколько фрагментов, для каждого из которых применяется шифр Цезаря. К каждому из фрагментов затем можно применить метод частотного анализа, как в случае обычных шифров однобуквенной замены. Таким образом, разгадывание шифра Виженера сводится на 90% к нахождению длины ключевой последовательности. Конечно, этот метод применим, только если текст достаточно большой, а ключевая фраза значительно короче его.
В 1920 г. известный американский криптолог и криптоаналитик, один из основоположников современной криптографии, организатор и первый директор американской службы сигнальной разведки Уильям Фредерик Фридман (1891–1969) предложил другой, более простой и в то же время более продуктивный метод определения длины ключевой фразы. Этот метод является одним из самых ярких достижений классической криптографии. Метод Фридмана основан на подсчете так называемого индекса совпадения. Зашифрованное сообщение переписывается с циклическим сдвигом текста на несколько позиций. Далее полученные таким образом сообщения переписываются одно над другим и подсчитывается число совпавших букв в верхней и нижней строках. Вычисляется индекс совпадения, равный отношению числа совпадений к длине сообщения. Для текстов на русском языке индекс совпадения составляет в среднем примерно 6%. Но для абсолютно случайной последовательности русских букв индекс совпадения значительно ниже! Поскольку всего в русском алфавите 32 буквы (русский алфавит без «Ё»), то вероятность совпадения составляет 1/32, или примерно 0,031 – чуть больше 3%. На этом соображении и основан метод Фридмана. Зашифрованный текст записывается со сдвигами 2, 3, 4 и т.д., и для каждого сдвига вычисляется индекс совпадения. Если индекс совпадения колеблется между 0 и 5%, то, скорее всего, размер сдвига не соответствует длине ключевой последовательности. Длина ключевой последовательности найдена, как только индекс совпадения скачком возрастет до 6% и более.
Понять, почему индекс совпадения резко возрастает, когда величина сдвига становится кратной длине ключевой фразы, совсем не трудно. В случае любого шифра простой замены, в частности шифра Цезаря, индекс совпадения для зашифрованного текста такой же, как и для исходного текста. При сдвиге текста, зашифрованного методом Виженера, на длину ключевой фразы мы сравниваем между собой буквы, которые шифруются одним и тем же шифром Цезаря. Следовательно, индекс совпадения получится в точности таким же, как и у незашифрованного текста при сдвиге на длину ключевой последовательности.
В заключение отметим, что теоретическое открытие, оказавшее серьезное влияние на развитие криптографии, было сделано в работах известного американского математика и инженера, одного из создателей математической теории информации Клода Элвуда Шеннона (1916–2001) «Теория связи в секретных системах» 1949 г. и выдающегося советского и российского ученого в области радиотехники, радиосвязи и радиоастрономии Владимира Александровича Котельникова (1908–2005) «Основные положения автоматической шифровки» 1941 г. В данных работах были сформулированы и доказаны необходимые и достаточные условия недешифруемости системы шифра. Они заключаются в том, что получение противником шифртекста не изменяет вероятностей используемых ключей. При этом было установлено, что единственным недешифруемым шифром является так называемая лента одноразового использования, когда открытый текст шифруется с помощью случайного ключа такой же длины. Однако это делает абсолютно стойкий шифр очень дорогим в эксплуатации.