Многоалфавитный шифр

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

История

Ранние предшественники

Идея использования нескольких алфавитов для шифрования восходит к античности. Одним из первых известных примеров является шифр Полибия (II век до н. э.), который, хотя и не был многоалфавитным в современном смысле, использовал квадрат 5×5 для замены букв координатами. Однако настоящий прорыв произошёл в эпоху Возрождения.

Шифр Альберти

В 1466 году итальянский архитектор и теоретик искусства Леон Баттиста Альберти в своём трактате «De componendis cifris» впервые описал принцип многоалфавитной замены. Он предложил использовать два вращающихся диска (шифровальный диск Альберти), на одном из которых был написан алфавит открытого текста, а на другом — смешанный алфавит шифротекста. После шифрования нескольких букв диск поворачивался, меняя соответствие между алфавитами. Это изобретение считается первым в истории многоалфавитным шифром.

Шифр Тритемия

В начале XVI века немецкий аббат Иоганн Тритемий в своей книге «Полиграфия» (1508) разработал таблицу Тритемия — квадратную таблицу размером 26×26, где каждая строка представляла собой алфавит, сдвинутый на одну позицию относительно предыдущей. Для шифрования использовалась последовательная замена букв открытого текста на буквы из разных строк таблицы, начиная с первой строки для первой буквы, со второй — для второй и так далее. Это был первый систематический многоалфавитный шифр, не требующий механических устройств.

Шифр Виженера

Наиболее известным и широко применяемым многоалфавитным шифром стал шифр Виженера, описанный французским дипломатом Блезом де Виженером в 1586 году. Он усовершенствовал таблицу Тритемия, добавив использование ключевого слова для определения порядка сдвига алфавитов. Шифр Виженера долгое время считался невзламываемым (le chiffre indéchiffrable), пока в 1863 году немецкий криптоаналитик Фридрих Касиски не разработал метод его взлома (тест Касиски).

Развитие в XIX—XX веках

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

Принцип работы

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

Ключ и сдвиг

Ключом обычно является слово, фраза или числовая последовательность. Для шифрования каждая буква ключа определяет, какой алфавит (или сдвиг) будет использован для текущей буквы открытого текста. Например, в шифре Виженера ключу «KEY» соответствуют сдвиги 10 (K), 4 (E) и 24 (Y). Если ключ короче сообщения, он повторяется циклически.

Таблица Виженера (квадрат Виженера)

Это таблица размером 26×26 (для латиницы), где строки и столбцы помечены буквами алфавита. Строка i представляет собой алфавит, сдвинутый на i позиций. Для шифрования буквы открытого текста (столбец) с помощью буквы ключа (строка) на пересечении находится буква шифротекста. Для расшифровки используется обратная операция: зная букву ключа (строку), находят в ней букву шифротекста и определяют соответствующий столбец — букву открытого текста.

Математическая модель

Для латинского алфавита (A=0, B=1, ..., Z=25) шифрование и расшифровка в шифре Виженера описываются формулами:

• Шифрование: Ci = (Pi + Ki) mod 26
• Расшифровка: Pi = (Ci - Ki) mod 26

где Pi — номер буквы открытого текста, Ci — номер буквы шифротекста, Ki — номер буквы ключа (сдвиг) для i-й позиции.

Классификация

Многоалфавитные шифры можно классифицировать по нескольким признакам.

По способу генерации алфавитов

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

По типу ключа

• С фиксированным ключом: Ключ задаётся заранее и используется для всего сообщения (шифр Виженера).
• С автоматическим ключом: Ключ генерируется из самого открытого текста или шифротекста (шифр Плейфера, шифр Бофора).
• С одноразовым ключом (одноразовый блокнот): Ключ является случайной последовательностью, равной по длине сообщению, и используется только один раз. Теоретически такой шифр является абсолютно стойким.

Примеры многоалфавитных шифров

• Шифр Виженера: Классический пример с циклическим ключом.
• Шифр Бофора: Вариант шифра Виженера, где используется обратный сдвиг.
• Шифр Плейфера: Шифрует пары букв (биграммы) с помощью таблицы 5×5, используя ключевое слово.
• Роторные машины («Энигма», «Сигма»): Электромеханические устройства, реализующие сложную многоалфавитную замену с помощью вращающихся роторов.
• Одноразовый блокнот: Теоретически абсолютно стойкий шифр, использующий случайный ключ, равный по длине сообщению.

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

Многоалфавитные шифры значительно устойчивее к частотному анализу, чем одноалфавитные, но не являются абсолютно стойкими (за исключением одноразового блокнота).

Метод Касиски (1863)

Фридрих Касиски разработал метод взлома шифра Виженера, основанный на поиске повторяющихся последовательностей букв в шифротексте. Расстояние между повторениями указывает на возможную длину ключа (или её кратное). Зная длину ключа, шифротекст разбивается на группы, каждая из которых зашифрована одним и тем же алфавитом, и к каждой группе применяется частотный анализ.

Индекс совпадений (1920-е годы)

Метод, разработанный Уильямом Фридманом, позволяет статистически оценить длину ключа. Индекс совпадений (IC) для случайного текста составляет около 0,038 (для латиницы), а для осмысленного текста — около 0,065. Если шифротекст разбит на группы с правильной длиной ключа, то внутри каждой группы IC будет близок к 0,065, что указывает на одноалфавитную замену.

Атака по известному открытому тексту

Если криптоаналитик знает фрагмент открытого текста и соответствующий ему шифротекст, он может восстановить часть ключа. Для шифра Виженера это делается простым вычитанием: Ki = (Ci - Pi) mod 26.

Применение

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

• Обучение криптографии: Как наглядный пример принципов подстановки и частотного анализа.
• Исторические исследования: Для расшифровки архивных документов, зашифрованных такими методами.
• Развлекательные задачи: В головоломках, квестах, настольных играх и литературных произведениях.
• Основы для современных алгоритмов: Принципы многоалфавитной замены лежат в основе многих поточных шифров и генераторов псевдослучайных последовательностей.

Источники

• Криптография и свобода / М. Е. Смышляев. — М.: Издательство «Либроком», 2010.
• Handbook of Applied Cryptography / A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. — CRC Press, 1996.
• The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet / D. Kahn. — Scribner, 1996.
• История криптографии / В. В. Ященко. — М.: МЦНМО, 2012.