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

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

История

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

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

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

Наиболее известным и исторически значимым полиалфавитным шифром является шифр Виженера, опубликованный в 1586 году французским дипломатом Блезом де Виженером в книге «Traicté des Chiffres». Хотя Виженер опирался на работы Альберти и немецкого аббата Иоганна Тритемия (который в 1508 году описал таблицу с 24 алфавитами — «tabula recta»), именно его имя закрепилось за этим методом. Шифр Виженера использует ключевое слово: каждая буква ключа указывает, на сколько позиций нужно сдвинуть алфавит (по принципу шифра Цезаря) для шифрования соответствующей буквы текста. Ключ повторяется циклически.

На протяжении нескольких столетий шифр Виженера считался «неразгадываемым» (le chiffre indéchiffrable). В 1863 году прусский полковник Фридрих Казиски опубликовал метод взлома, основанный на поиске повторяющихся последовательностей в шифротексте для определения длины ключа. Позднее, в 1920-х годах, американский криптоаналитик Уильям Фридман разработал более совершенный метод — индекс совпадений.

XX век и современность

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

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

Классификация полиалфавитных шифров

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

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

• На основе таблицы (tabula recta): Используется заранее составленная таблица, где каждый столбец или строка представляет собой алфавит, сдвинутый на определённое число позиций. Пример — шифр Виженера.
• На основе ключевого слова: Алфавиты формируются путём выписывания букв ключевого слова (без повторений) и последующих букв алфавита в естественном порядке. Пример — шифр Гронсфельда (вариант с цифровым ключом).
• На основе вращающихся дисков или роторов: Механические устройства, где алфавиты меняются при каждом повороте диска или ротора. Пример — машина «Энигма».

По типу ключа

• С повторяющимся ключом: Ключевое слово или последовательность повторяется циклически на протяжении всего сообщения. Это делает шифр уязвимым для атаки Казиски.
• С бесконечным (одноразовым) ключом: Ключ имеет длину, равную длине сообщения, и не повторяется. Теоретически невзламываемый шифр, известный как «шифр Вернама» или одноразовый блокнот (one-time pad). Является частным случаем полиалфавитного шифра.

Принцип работы (на примере шифра Виженера)

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

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

Пример

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

1. Преобразуем буквы в числа (А=0, Б=1, ..., Я=31):

• П = 16, Р = 17, И = 9, В = 2, Е = 6, Т = 19
• К = 11, Л = 12, Ю = 31, Ч = 23

1. Шифруем по позициям:

• 1: (16 + 11) mod 32 = 27 → Ы
• 2: (17 + 12) mod 32 = 29 → Ь
• 3: (9 + 31) mod 32 = 40 mod 32 = 8 → Й
• 4: (2 + 23) mod 32 = 25 → Ч
• 5: (6 + 11) mod 32 = 17 → Р (ключ повторяется: 5-я буква ключа — снова К)
• 6: (19 + 12) mod 32 = 31 → Я

1. Шифротекст: «ЫЬЙЧРЯ».

Дешифрование

Дешифрование производится обратной операцией: P = (C - K) mod N. Если разность отрицательна, прибавляется N.

Криптоанализ полиалфавитных шифров

Атака Казиски

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

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

Метод, предложенный Уильямом Фридманом в 1920-х годах, позволяет статистически определить длину ключа. Индекс совпадений (IC) — это вероятность того, что два случайно выбранных символа из шифротекста будут одинаковыми. Для случайного текста IC ≈ 1/N (где N — мощность алфавита), для осмысленного текста IC значительно выше. Если шифротекст разбить на группы, соответствующие одному алфавиту (то есть с шагом, равным предполагаемой длине ключа), то IC для каждой группы будет близок к IC осмысленного текста, что подтверждает правильность длины ключа.

Восстановление ключа

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

Применение

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

• Дипломатическая переписка: Шифр Виженера и его модификации активно использовались европейскими дипломатами в XVII–XIX веках.
• Военная связь: В период Гражданской войны в США (1861–1865) армия Конфедерации применяла упрощённые варианты полиалфавитных шифров.
• Шифровальные машины: Машины «Энигма», «Сигба» (США) и «Типекс» (Швеция) реализовывали сложные полиалфавитные подстановки с помощью роторов.

Современное

• Образовательные цели: Изучение полиалфавитных шифров является классическим примером в курсах криптографии и информационной безопасности для демонстрации принципов частотного анализа и методов криптоанализа.
• Легковесные приложения: В некоторых случаях, где не требуется высокая стойкость (например, в головоломках или компьютерных играх), могут использоваться простые полиалфавитные шифры.
• Основы для современных алгоритмов: Принцип смены ключа по позиции используется в поточных шифрах (например, RC4, Salsa20), а также в режимах работы блочных шифров (например, CFB, OFB, CTR).

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

• Шифр Виженера долгое время называли «неразгадываемым», хотя ещё в 1854 году Чарльз Бэббидж (изобретатель аналитической машины) независимо от Казиски разработал метод его взлома, но не опубликовал его.
• В 1920-х годах советский криптограф Григорий Фридман (не путать с Уильямом Фридманом) внёс вклад в развитие теории полиалфавитных шифров, работая над системами шифрования для нужд НКВД.
• Одноразовый блокнот (шифр Вернама), являющийся полиалфавитным шифром с бесконечным ключом, до сих пор используется в некоторых системах правительственной и дипломатической связи, где требуется абсолютная стойкость, при условии надёжного распространения ключей.