Многоалфавитная замена

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

История

Ранние предпосылки

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

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

Наиболее известным и широко применяемым многоалфавитным шифром стал шифр, ошибочно приписываемый французскому дипломату Блезу де Виженеру (XVI век). На самом деле его основу — таблицу с 26 строками сдвинутых алфавитов (квадрат Виженера) — описал Джованни Баттиста Беллазо в 1553 году. Виженер же усовершенствовал систему, добавив «автоключ» (использование предыдущего символа шифротекста как части ключа). Тем не менее, именно под названием «шифр Виженера» метод получил широкую известность и использовался в европейских армиях и дипломатических службах в XVII–XIX веках. Шифр Виженера считался невскрываемым на протяжении почти трёх столетий.

Кризис и взлом

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

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

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

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

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

Ключ и его использование

Ключ обычно представляет собой слово или короткую фразу. Для шифрования:

1. Ключ записывается под открытым текстом, повторяясь циклически.
2. Для каждой позиции сообщения определяется номер символа ключа (например, его порядковый номер в алфавите).
3. Этот номер указывает, какой из алфавитов (или на сколько позиций сдвинуть базовый алфавит) использовать для замены текущей буквы.

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

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

• Строка выбирается по букве открытого текста.
• Столбец выбирается по букве ключа.
• На пересечении строки и столбца находится буква шифротекста.

Пример

Пусть алфавит — русский (33 буквы, для простоты без Ё). Открытый текст: «ПРИВЕТ». Ключ: «КЛЮЧ».

1. Записываем ключ циклически: КЛЮЧКЛ
2. Шифрование:

• П (строка) + К (столбец) → ? (На пересечении строки П и столбца К в таблице Виженера стоит буква, смещённая на позицию К (11-я буква алфавита) от П. П (16-я) + 11 = 27-я буква — это Ъ. Или, в терминах сдвига: буква «П» сдвигается на 11 позиций вперёд → «Ъ».
• Р (17-я) + Л (12-я) = 29-я → Ы.
• И (9-я) + Ю (31-я) = 40-я (40-33=7) → Ё.
• В (3-я) + Ч (24-я) = 27-я → Ъ.
• Е (6-я) + К (11-я) = 17-я → Р.
• Т (19-я) + Л (12-я) = 31-я → Ю.

1. Шифротекст: «ЪЫЁЪРЮ».

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

Классификация и виды

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

По типу ключа

1. С циклическим ключом (шифр Виженера): Ключ повторяется через фиксированный период. Наиболее простой и уязвимый вариант.
2. С автоключом: Ключом для следующей позиции становится либо предыдущий символ открытого текста, либо предыдущий символ шифротекста. Это усложняет взлом, так как ключ не имеет фиксированного периода.
3. С псевдослучайным ключом (гаммирование): Используется генератор псевдослучайных чисел (ГПСЧ), инициализированный истинным ключом. Последовательность сдвигов (гамма) не повторяется в рамках разумного периода. Это основа современных поточных шифров.

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

1. Ручные (табличные): Используют бумажные таблицы или диски (диск Альберти). Период ключа ограничен длиной запоминаемого слова.
2. Механические (роторные): Машины, в которых смена алфавита происходит за счёт механического вращения дисков (роторов). Период ключа может быть огромным (например, 26³ = 17576 для трёхроторной «Энигмы»).
3. Электронные (программные): Реализуются на компьютерах. Позволяют использовать ключи практически неограниченной длины и сложные алгоритмы смешивания.

Криптостойкость и криптоанализ

Достоинства

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

Недостатки и методы взлома

1. Тест Казиски: Позволяет определить длину ключа. Аналитик ищет в шифротексте повторяющиеся группы символов (длиной 3-4 и более). Расстояние между такими группами, как правило, кратно длине ключа. Найдя длину ключа (L), криптоаналитик разбивает шифротекст на L колонок, каждая из которых зашифрована простым шифром Цезаря. Затем каждая колонка взламывается отдельно методами частотного анализа.
2. Индекс совпадений: Статистический метод, предложенный Уильямом Фридманом. Позволяет не только определить длину ключа, но и отличить многоалфавитный шифр от одноалфавитного.
3. Короткий ключ: Если ключ короче сообщения, шифр уязвим для атак, основанных на избыточности естественного языка.

Абсолютная стойкость

Многоалфавитная замена становится абсолютно стойкой (теоретически невзламываемой) при выполнении двух условий, сформулированных Клодом Шенноном:

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

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

Применение

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

• Дипломатическая и военная переписка XVI–XIX веков (шифр Виженера).
• Радиоперехват и шифрование в Первой и Второй мировых войнах (роторные машины, включая «Энигму» и американскую SIGABA).
• Использование в менее критичных сферах (например, в некоторых системах гражданской связи) вплоть до середины XX века.

Современное

В чистом виде классическая многоалфавитная замена с коротким ключом не используется в современных криптосистемах из-за её уязвимости. Однако её принцип лежит в основе:

• Поточных шифров: Современные алгоритмы (например, RC4, Salsa20, ChaCha20) генерируют длинную псевдослучайную последовательность (гамму), которая накладывается на открытый текст по модулю 2 (XOR) или по модулю длины алфавита. Это прямая эволюция многоалфавитной замены.
• Блочных шифров: В некоторых режимах работы блочных шифров (например, режим гаммирования — CTR) фактически реализуется поточное шифрование, где блоки шифруются с использованием счётчика, что также можно рассматривать как многоалфавитную замену на уровне блоков.
• Учебных и любительских целей: Изучение шифра Виженера является обязательной частью курсов криптографии и основ информационной безопасности.

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

• Шифр Виженера долгое время называли «le chiffre indéchiffrable» (фр. «неразборчивый шифр») из-за его кажущейся стойкости.
• Чарльз Бэббидж, взломавший шифр в 1854 году, не опубликовал свою работу, возможно, по соображениям военной секретности, и приоритет открытия долгое время приписывался Казиски.
• Роторная машина «Энигма» использовала не просто сдвиг алфавита, а сложную электрическую коммутацию, что является разновидностью многоалфавитной подстановки с огромным периодом.

Источники

1. Баричев С.Г., Гончаров В.В., Серов Р.Е. «Основы современной криптографии». — М.: Горячая линия – Телеком, 2011.
2. Шеннон К. «Теория связи в секретных системах» (1949) / Сборник «Работы по теории информации и кибернетике». — М.: ИЛ, 1963.
3. Сингх С. «Книга шифров: Тайная история шифров и их взлома». — М.: АСТ, 2006.
4. Касиски Ф. «Die Geheimschriften und die Dechiffrir-Kunst» (Тайнопись и искусство дешифровки). — Берлин, 1863.
5. Хоффман П. «Человек, который разгадал „Энигму“: История Алана Тьюринга». — М.: Эксмо, 2015.