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

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

История

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

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

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

Наиболее известным и исторически значимым представителем полиалфавитной замены является шифр Виженера, названный в честь французского дипломата и криптографа Блеза де Виженера (1523–1596). В 1586 году он опубликовал трактат «Трактат о шифрах» (фр. Traité des chiffres), где описал метод, основанный на использовании таблицы (квадрата) Виженера и ключевого слова. Однако, как установлено историками, сам принцип был известен ранее: в 1553 году итальянский математик Джованни Баттиста Беллазо в книге «La cifra del sig. Giovan Battista Bellaso» предложил шифр с использованием ключа и таблицы. Виженер усовершенствовал систему, добавив возможность использования «автоключа» (когда ключом служит само сообщение).

В течение нескольких столетий шифр Виженера считался невскрываемым и получил название «le chiffre indéchiffrable» (франц. «неразгаданный шифр»). Он активно использовался в дипломатической переписке европейских государств, особенно в XVII–XVIII веках.

Взлом и развитие

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

XX век

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

С развитием компьютерной техники полиалфавитная замена уступила место более сложным блочным и поточным шифрам, но её принципы легли в основу многих современных алгоритмов, таких как AES (Advanced Encryption Standard) и RC4.

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

Основная идея

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

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

Классическим инструментом является таблица Виженера — квадратная матрица размером N×N, где N — количество символов в алфавите. Строки таблицы соответствуют символам ключа, столбцы — символам открытого текста. На пересечении строки и столбца находится символ шифротекста. Формально:

Если открытый текст \( P = p_1 p_2 ... p_n \),
Ключ \( K = k_1 k_2 ... k_m \) (циклически повторяется),
То шифротекст \( C = c_1 c_2 ... c_n \), где \( c_i = (p_i + k_i) \mod N \).

Пример

Для латинского алфавита (A=0, B=1, ..., Z=25) и ключа «KEY»:

Открытый текст: «HELLO»
Ключ (повторённый): «KEYKE»
Шифрование:
H (7) + K (10) = 17 → R
E (4) + E (4) = 8 → I
L (11) + Y (24) = 35 mod 26 = 9 → J
L (11) + K (10) = 21 → V
O (14) + E (4) = 18 → S
Шифротекст: «RIJVS»

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

По способу задания ключа

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

По типу алфавитов

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

По механизму реализации

Ручные: с использованием таблиц, дисков (шифровальные диски Альберти, Джефферсона).
Механические: роторные машины (Энигма, «Кристалл»).
Электронные и программные: современные алгоритмы (например, шифр Вернама в цифровом виде).

Криптостойкость

Преимущества перед моноалфавитной заменой

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

Уязвимости

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

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

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

Применение

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

Дипломатическая переписка: шифр Виженера использовался французскими, испанскими и другими европейскими дипломатами в XVI–XIX веках.
Военная связь: роторные машины (Энигма) применялись нацистской Германией во Второй мировой войне.
Коммерческая тайна: в XIX веке полиалфавитные шифры использовались для защиты телеграфных сообщений.

Современное

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

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

Шифр Виженера долгое время считался невскрываемым, пока в 1863 году не был опубликован метод Казиски. Однако, как выяснилось, Чарльз Бэббидж взломал его ещё в 1854 году, но не обнародовал результаты.
В романе Жюля Верна «Матиас Шандор» (1885) используется шифр Виженера.
Принцип полиалфавитной замены лежит в основе шифра «Энигма», который был взломан союзниками во Второй мировой войне, что, по мнению историков, сократило войну на два года.
Одноразовый блокнот (шифр Вернама) является единственным шифром с абсолютной стойкостью, но его практическое применение ограничено из-за необходимости передачи ключа такой же длины, как и сообщение.

Источники

Брюс Шнайер. «Прикладная криптография» (1996).
Дэвид Кан. «Взломщики кодов: история криптографии» (1967).
Саймон Сингх. «Книга шифров» (1999).
Фридрих Казиски. «Die Geheimschriften und die Dechiffrir-Kunst» (1863).
Блез де Виженер. «Traité des chiffres» (1586).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →