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

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

История

До середины XIX века шифр Виженера, изобретённый в XVI веке, считался невскрываемым, так как использовал переменный ключ, что делало его устойчивым к частотному анализу — основному методу взлома одноалфавитных шифров. Однако в 1854 году английский математик Чарльз Бэббидж независимо разработал метод, аналогичный методу Казиски, но не опубликовал его. В 1863 году Фридрих Казиски, бывший прусский офицер, опубликовал книгу «Die Geheimschriften und die Dechiffrir-Kunst» («Тайнопись и искусство дешифровки»), где впервые представил систематический подход к взлому шифра Виженера. Метод получил широкое распространение и стал основой для дальнейшего развития криптоанализа.

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

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

Этапы взлома

1. Поиск повторяющихся последовательностей. В зашифрованном тексте находят все повторяющиеся блоки длиной не менее 3 символов. Чем длиннее блок, тем выше вероятность, что он соответствует повторению в открытом тексте, а не случайному совпадению.
2. Вычисление расстояний между повторами. Для каждой найденной пары одинаковых блоков вычисляют расстояние между их началами (в символах).
3. Определение возможной длины ключа. Длина ключа с высокой вероятностью является делителем большинства найденных расстояний. Для этого находят наибольший общий делитель (НОД) всех расстояний или их подмножества. Часто используется метод разложения расстояний на множители и выбор наиболее часто встречающегося множителя.
4. Разделение текста на группы. После определения длины ключа L шифротекст разбивают на L групп, каждая из которых содержит символы, зашифрованные одним и тем же сдвигом (алфавитом). Например, первая группа — символы на позициях 1, L+1, 2L+1 и т.д., вторая — на позициях 2, L+2, 2L+2 и т.д.
5. Частотный анализ каждой группы. Каждая группа представляет собой одноалфавитный шифр (шифр Цезаря). К ней применяется частотный анализ: сравнивается распределение частот символов в группе с распределением частот букв в языке открытого текста (например, в русском языке самые частые буквы — «о», «е», «а», «и»). По наиболее частому символу в группе определяют сдвиг (ключевую букву) для этой позиции.
6. Восстановление ключа и открытого текста. Собрав все сдвиги, получают ключевое слово. Затем, используя таблицу Виженера или формулу, расшифровывают весь текст.

Пример

Рассмотрим упрощённый пример на русском языке. Пусть зашифрованный текст (без пробелов) содержит повторяющийся блок «РПТ» на расстоянии 12 символов. Другие повторы дают расстояния 6, 18, 24. Наибольший общий делитель этих чисел — 6. Следовательно, длина ключа, вероятно, равна 6. После разделения текста на 6 групп и частотного анализа каждой группы можно определить, что ключевое слово, например, «КЛЮЧ». После расшифровки получается осмысленный текст.

Ограничения и особенности

• Длина ключа. Метод эффективен только при относительно коротких ключах (до нескольких десятков символов). При очень длинных ключах, сопоставимых с длиной текста, повторяющиеся блоки встречаются редко, и метод становится неприменим.
• Язык текста. Для успешного частотного анализа необходимо знать язык открытого текста. Если текст короткий или содержит нестандартную лексику, точность снижается.
• Случайные совпадения. Повторяющиеся блоки могут возникать случайно, что приводит к ложным кандидатам длины ключа. Для повышения надёжности используют блоки длиной 4–5 символов и статистическую обработку.
• Автоматизация. Метод легко алгоритмизируется и реализован во многих программах криптоанализа, включая утилиты командной строки и онлайн-сервисы.

Применение

Метод Казиски применяется в учебных целях для демонстрации уязвимости многоалфавитных шифров, а также в историческом криптоанализе для взлома архивных шифровок. В современных криптосистемах (например, AES, RSA) подобные атаки невозможны из-за использования принципиально иных математических принципов.

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

• Фридрих Казиски (1805–1881) был не только криптографом, но и археологом-любителем, участвовавшим в раскопках в Малой Азии.
• Метод Казиски иногда называют «тестом Казиски» или «методом повторяющихся пар».
• Чарльз Бэббидж, создатель аналитической машины, разработал аналогичный метод на 9 лет раньше, но его работа осталась неопубликованной и была обнаружена только в XX веке в его архивах.

Источники

• Kahn, David. The Codebreakers: The Story of Secret Writing. Scribner, 1967.
• Singh, Simon. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Doubleday, 1999.
• Казиски, Фридрих. Die Geheimschriften und die Dechiffrir-Kunst. 1863.
• Schneier, Bruce. Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, 1996.