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

Квадрат Виженера (также таблица Виженера, tabula recta) — это таблица, используемая в полиалфавитном шифре, который был назван в честь французского дипломата и криптографа XVI века Блеза де Виженера. Квадрат представляет собой квадратную матрицу размером 26×26 (для латинского алфавита) или 33×33 (для русского), где каждая строка является циклическим сдвигом алфавита на одну позицию влево относительно предыдущей. Данный инструмент лежит в основе шифра Виженера, который на протяжении нескольких столетий считался одним из самых надёжных методов ручного шифрования и получил прозвище «неразгаданный шифр».

История

Предшественники

Идея использования полиалфавитного шифрования впервые была описана в XV веке итальянским архитектором Леоном Баттистой Альберти в трактате «О шифрах» (1466). Альберти предложил шифровальный диск с двумя алфавитами, который позволял менять смещение в процессе шифрования. В 1518 году немецкий аббат Иоганн Тритемий в своей книге «Полиграфия» описал таблицу, названную tabula recta, которая стала прообразом квадрата Виженера. Тритемий, однако, не предложил алгоритма смены строк в зависимости от ключа, а использовал таблицу для последовательного применения всех сдвигов.

Вклад Виженера

Блез де Виженер, французский дипломат и криптограф, в 1585 году опубликовал труд «Трактат о шифрах» (Traité des Chiffres), в котором систематизировал и усовершенствовал идеи предшественников. Он предложил использовать для шифрования ключевое слово, которое определяло, какая строка квадрата будет применяться для каждой буквы открытого текста. Таким образом, шифр Виженера стал первым практическим полиалфавитным шифром с переменным сдвигом, зависящим от ключа. Сам квадрат часто называют «квадратом Виженера», хотя его изобретателем по праву считается Тритемий.

Распространение и криптоанализ

На протяжении XVII–XIX веков шифр Виженера считался невзламываемым, что породило миф о его абсолютной стойкости. Однако в 1854 году английский математик Чарльз Бэббидж независимо разработал метод взлома, основанный на поиске повторяющихся последовательностей в шифротексте. В 1863 году прусский офицер Фридрих Касиски опубликовал описание метода, который позже стал известен как тест Касиски. Этот метод позволяет определить длину ключа, после чего задача сводится к взлому нескольких шифров Цезаря. Таким образом, шифр Виженера был признан уязвимым, хотя и оставался популярным вплоть до начала XX века.

Устройство квадрата

Структура таблицы

Квадрат Виженера представляет собой квадратную матрицу, где первый столбец и первая строка содержат алфавит в естественном порядке. Для латинского алфавита (A–Z) таблица имеет размер 26×26. Каждая последующая строка является циклическим сдвигом предыдущей строки на одну позицию влево. Таким образом, строка с номером n (где n отсчитывается от 0) содержит алфавит, начинающийся с буквы, соответствующей номеру n в алфавите.

Пример для латинского алфавита (первые три строки):

• Строка A (ключ A): A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Строка B (ключ B): B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
• Строка C (ключ C): C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

Алгоритм шифрования

Шифрование с использованием квадрата Виженера выполняется по следующему правилу:

1. Выбирается ключевое слово (например, «KEY»).
2. Открытый текст записывается, и под ним повторяется ключевое слово до длины текста.
3. Для каждой буквы открытого текста находится пересечение строки, соответствующей букве ключа, и столбца, соответствующего букве открытого текста. На пересечении находится буква шифротекста.

Пример шифрования слова «HELLO» с ключом «KEY»:

• Открытый текст: H E L L O
• Ключ: K E Y K E
• Для первой буквы (H, ключ K): строка K, столбец H → R
• Для второй буквы (E, ключ E): строка E, столбец E → I
• Для третьей буквы (L, ключ Y): строка Y, столбец L → J
• Для четвёртой буквы (L, ключ K): строка K, столбец L → V
• Для пятой буквы (O, ключ E): строка E, столбец O → S
• Шифротекст: R I J V S

Алгоритм расшифрования

Расшифрование выполняется обратным образом: для каждой буквы шифротекста находится строка, соответствующая букве ключа, и в этой строке отыскивается буква шифротекста. Столбец, в котором она находится, указывает на букву открытого текста.

Классификация шифров на основе квадрата

Шифр Цезаря как частный случай

Если ключ состоит из одной буквы, шифр Виженера вырождается в шифр Цезаря с фиксированным сдвигом, равным номеру этой буквы в алфавите. Таким образом, квадрат Виженера включает в себя все возможные шифры Цезаря.

Автоключевые варианты

Существуют модификации шифра, где ключом служит сам открытый текст или шифротекст. Например, в шифре с автоключом (предложенном самим Виженером) после начального ключевого слова для каждой последующей буквы используется предыдущая буква открытого текста. Это делает шифр более устойчивым к частотному анализу, но усложняет использование квадрата.

Современные аналоги

В цифровой криптографии принцип полиалфавитной замены, реализованный в квадрате Виженера, применяется в некоторых поточных шифрах, таких как RC4, где вместо таблицы используется псевдослучайная последовательность. Однако современные алгоритмы (например, AES) основаны на более сложных математических структурах, таких как подстановочно-перестановочные сети.

Применение

Историческое использование

Шифр Виженера активно применялся в дипломатической и военной переписке в XVII–XIX веках. Например, во время Гражданской войны в США (1861–1865) конфедераты использовали его для шифрования сообщений, хотя к тому времени метод взлома уже был известен. В Европе шифр использовался вплоть до Первой мировой войны, когда его вытеснили более сложные механические шифровальные машины, такие как «Энигма».

Образовательное значение

В настоящее время квадрат Виженера является классическим примером для изучения основ криптографии в учебных заведениях. Он наглядно демонстрирует разницу между моноалфавитными и полиалфавитными шифрами, а также принципы частотного анализа и криптоанализа.

Интересные факты

• В 1917 году американский криптограф Уильям Фридман, один из основоположников современной криптологии, в своей работе «Индекс совпадений» использовал квадрат Виженера для статистического анализа шифротекстов.
• В романе Жюля Верна «Путешествие к центру Земли» (1864) упоминается шифр, основанный на квадрате Виженера, который герои расшифровывают, чтобы найти путь к центру Земли.
• В 2011 году шифр Виженера был использован в компьютерной игре «Assassin’s Creed: Revelations» как часть головоломки, связанной с историей тамплиеров.

Криптоанализ

Тест Касиски

Метод, предложенный Фридрихом Касиски, основан на поиске повторяющихся фрагментов в шифротексте. Если длина ключа равна L, то одинаковые фрагменты открытого текста, зашифрованные одной и той же частью ключа, дадут одинаковые фрагменты шифротекста. Расстояние между такими повторениями кратно L. Анализируя расстояния, можно определить длину ключа.

Индекс совпадений

После определения длины ключа шифротекст разбивается на L групп, каждая из которых зашифрована одним и тем же сдвигом (шифром Цезаря). Для каждой группы вычисляется индекс совпадений — вероятность того, что две случайно выбранные буквы из группы одинаковы. Для английского языка этот индекс составляет около 0,065. Если индекс близок к этому значению, значит, сдвиг подобран верно. Затем сдвиги подбираются перебором, и открытый текст восстанавливается.

Современное состояние

С появлением компьютеров взлом шифра Виженера занимает доли секунды, даже для длинных ключей. Однако в XIX веке этот метод считался прорывом, так как он опроверг миф о «неразгаданности» полиалфавитных шифров.

Критика и ограничения

Основным недостатком квадрата Виженера является его уязвимость к частотному анализу при известной длине ключа. Кроме того, ключ должен быть достаточно длинным и случайным, чтобы избежать повторений. Если ключ короче сообщения, шифр становится уязвимым для теста Касиски. Если ключ совпадает с длиной сообщения и является случайным, шифр превращается в одноразовый блокнот, который теоретически невзламываем, но требует передачи ключа той же длины, что и сообщение, что на практике неудобно.

Источники

• Сингх С. «Книга шифров: Тайная история шифрования и его роль в войнах, шпионаже и бизнесе». — М.: АСТ, 2007.
• Кан Д. «Взломщики кодов: История криптоанализа». — М.: Центрполиграф, 2000.
• Фридман У. «Индекс совпадений и его применение в криптографии». — 1922.
• Касиски Ф. «Die Geheimschriften und die Dechiffrir-Kunst». — 1863.