Многоалфавитная подстановка

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

История

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

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

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

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

XX век и криптография

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

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

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

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

Пример

Пусть открытый текст — «HELLO», а ключ — «KEY». Ключ повторяется: KEYKE. Шифрование:

• H (позиция 7) + K (строка, соответствующая сдвигу на 10) → R (17)
• E (4) + E (4) → I (8)
• L (11) + Y (24) → J (9)
• L (11) + K (10) → V (21)
• O (14) + E (4) → S (18)

Результат: шифротекст «RIJVS».

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

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

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

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

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

По длине ключа

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

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

Частотный анализ и его ограничения

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

Метод Казиски

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

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

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

Применение

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

• Дипломатическая переписка — шифр Виженера использовался европейскими монархами и дипломатами в XVI–XIX веках.
• Военная связь — роторные машины (Энигма, SIGABA) применялись во время Второй мировой войны для шифрования приказов и разведданных.
• Гражданская криптография — до появления современных алгоритмов (DES, AES) полиалфавитные шифры использовались в коммерческих системах.

Современное

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

• Шифр Вернама (одноразовый блокнот) — теоретически абсолютно стойкий, но требует истинно случайного ключа длины сообщения, что делает его непрактичным для массового использования.
• Потоковые шифры (RC4, Salsa20, ChaCha) — генерируют ключевой поток, который накладывается на открытый текст по модулю 2 (XOR). Фактически это многоалфавитная подстановка с двоичным алфавитом и бесконечным ключом.
• Криптоаналитические методы — изучение полиалфавитных шифров является классическим учебным материалом для криптоаналитиков.

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

• Шифр Виженера долгое время считался невзламываемым, и его называли «le chiffre indéchiffrable» (неразгадываемый шифр). Однако после публикации метода Казиски в 1863 году его репутация была разрушена.
• В романе Эдгара По «Золотой жук» (1843) используется одноалфавитная подстановка, но в более поздних произведениях, например, в «Пляске смерти» (1915) Артура Конан Дойля, упоминаются более сложные шифры.
• Во время Второй мировой войны японская шифровальная машина «Пурпурная» использовала многоалфавитную подстановку с переключаемыми роторами, но была взломана американскими криптоаналитиками под руководством Уильяма Фридмана.

Источники

• Kahn, D. (1967). The Codebreakers: The Story of Secret Writing. Macmillan.
• Singh, S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Doubleday.
• Schneier, B. (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons.
• Фридман, У. (1920). The Index of Coincidence and Its Applications in Cryptography. Riverbank Laboratories.