Полиалфавитное шифрование

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

История

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

Идея использования нескольких алфавитов для шифрования восходит к трудам арабского криптографа Аль-Кинди (IX век), который описал метод частотного анализа. Однако первое известное практическое применение полиалфавитного шифрования связано с именем итальянского архитектора и писателя Леона Баттисты Альберти. В 1466 году он предложил шифровальный диск, состоящий из двух вращающихся колес с алфавитами. При каждом повороте диска смещение алфавита менялось, что фактически реализовывало полиалфавитную замену.

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

Наиболее известным и исторически значимым полиалфавитным шифром является шифр Виженера, названный в честь французского дипломата и криптографа Блеза де Виженера (XVI век). Хотя сам метод был описан ранее (например, в работах Джованни Баттиста Беллазо), Виженер систематизировал его и представил в виде таблицы (квадрат Виженера).

Шифр Виженера использовался в течение нескольких столетий, считаясь невзламываемым до середины XIX века. Взлом этого шифра стал возможен благодаря работе Фридриха Касиски (1863 год), который разработал метод определения длины ключа (тест Касиски), и Чарльза Бэббиджа, который независимо от него нашел способ дешифровки.

XX век и машинное шифрование

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

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

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

Ключ и его роль

Ключ представляет собой последовательность символов (обычно букв или цифр), которая определяет, какой из алфавитов будет использоваться для шифрования каждого конкретного символа. Ключ может быть коротким (например, слово «КЛЮЧ») или длинным (фраза, книга). Для шифрования длинного сообщения ключ обычно повторяется циклически.

Алгоритм шифрования (на примере шифра Виженера)

1. Открытый текст разбивается на символы.
2. Ключ записывается под открытым текстом, повторяясь до его длины.
3. Для каждого символа открытого текста определяется его позиция в алфавите (например, А=0, Б=1, ..., Я=31).
4. Для соответствующего символа ключа также определяется его позиция.
5. Символ шифротекста вычисляется по формуле: C = (M + K) mod N, где:

• C — позиция символа шифротекста,
• M — позиция символа открытого текста,
• K — позиция символа ключа,
• N — мощность алфавита (количество букв, например, 32 для русского языка).

1. Полученная позиция преобразуется обратно в символ алфавита.

Пример

Пусть открытый текст — «ПРИВЕТ», ключ — «КЛЮЧ».

1. Записываем ключ циклически: П Р И В Е Т

К Л Ю Ч К Л

1. Вычисляем:

• П (16) + К (11) = 27 mod 32 = 27 → Ъ
• Р (17) + Л (12) = 29 mod 32 = 29 → Ы
• И (9) + Ю (31) = 40 mod 32 = 8 → И
• В (2) + Ч (23) = 25 mod 32 = 25 → Ч
• Е (6) + К (11) = 17 mod 32 = 17 → Р
• Т (19) + Л (12) = 31 mod 32 = 31 → Я

1. Шифротекст: ЪЫИЧРЯ.

Расшифрование

Расшифрование производится обратной операцией: M = (C - K) mod N. При известном ключе получатель может восстановить исходный текст.

Виды и классификация

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

По типу ключа

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

По способу реализации

• Табличные (ручные): Используют таблицы (квадрат Виженера) или диски (диск Альберти). Требуют ручного вычисления.
• Механические (роторные): Реализуются с помощью вращающихся роторов (машины «Энигма», «Сигба», M-209). Обеспечивают высокую скорость и сложность.
• Электронные (программные): Реализуются на компьютерах с использованием математических алгоритмов. Современные блочные шифры (например, AES) также используют принцип полиалфавитной замены, но в гораздо более сложной форме.

По сложности смены алфавита

• Простая (линейная): Смещение алфавита меняется на фиксированную величину (шифр Цезаря с переменным сдвигом).
• Нелинейная: Смещение меняется по сложному закону, зависящему от предыдущих состояний (роторные машины).

Криптоанализ и уязвимости

Несмотря на свою стойкость по сравнению с моноалфавитными шифрами, полиалфавитные шифры имеют уязвимости.

Тест Касиски (Kasiski examination)

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

Метод совпадений (Index of coincidence)

Разработан Уильямом Фридманом в 1920-х годах. Этот статистический метод позволяет определить длину ключа, анализируя вероятность того, что два случайно выбранных символа шифротекста окажутся одинаковыми. Для полиалфавитного шифра эта вероятность близка к случайной, в то время как для моноалфавитного — значительно выше. Изменяя длину предполагаемого ключа и анализируя индекс совпадений для каждого сдвига, можно точно определить длину ключа.

Частотный анализ после определения длины ключа

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

Современные методы

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

Применение

Историческое

• Дипломатическая переписка: Шифр Виженера активно использовался в дипломатических миссиях XVI–XIX веков.
• Военная связь: Роторные машины («Энигма», M-209) широко применялись в военных целях в первой половине XX века.
• Коммерческая и личная переписка: Использовалась для защиты частной корреспонденции.

Современное

• Компьютерные алгоритмы: Принцип полиалфавитной замены лежит в основе многих современных блочных шифров (AES, ГОСТ 28147-89), хотя реализован он на уровне байтов и битов, а не букв.
• Криптографические протоколы: Используется в протоколах шифрования данных (SSL/TLS, IPsec).
• Образовательные цели: Изучается в курсах криптографии для демонстрации принципов симметричного шифрования и методов криптоанализа.

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

• Шифр Виженера долгое время назывался «le chiffre indéchiffrable» (неразгадываемый шифр) во французской литературе.
• В 1917 году американский криптограф Гилберт Вернам предложил вариант полиалфавитного шифра с одноразовым блокнотом (one-time pad), который является абсолютно стойким при условии, что ключ используется только один раз и является случайным.
• Современные системы шифрования, такие как AES, используют полиалфавитную замену в сочетании с перестановками (SP-сеть), что обеспечивает высокую стойкость к известным атакам.

Источники

• Сингх С. «Книга шифров: Тайная история шифров и их взлома» (2000).
• Шнайер Б. «Прикладная криптография» (1996).
• Фергюсон Н., Шнайер Б. «Практическая криптография» (2003).
• Стендфордская энциклопедия философии, статья «Криптография» (2020).
• Материалы курса «Криптография и безопасность сетей» (Университет ИТМО, 2021).