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

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

История

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

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

Метод Касиски состоит из двух основных этапов:

1. Определение длины ключа.
2. Восстановление самого ключа.

Определение длины ключа

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

Процедура:

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

Пример: если в шифротексте встретились два одинаковых триграфа (три символа) на расстоянии 12 символов, то возможная длина ключа — 1, 2, 3, 4, 6 или 12. Анализ нескольких таких повторений позволяет сузить круг до наиболее вероятного значения.

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

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

Ограничения и критика

Метод Касиски эффективен только при определённых условиях:

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

Применение

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

Сравнение с другими методами

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

На практике оба метода часто комбинируются: сначала длина ключа оценивается по Касиски, затем уточняется индексом совпадений.

Пример работы

Пусть открытый текст: «HELLO WORLD» (без пробелов), ключ: «KEY». Зашифрованный текст (шифр Виженера): «RIJVS UYVJN» (без пробелов). В шифротексте встречается повторение «VU» на расстоянии 5 символов. Делители 5 — 1 и 5. Предположив длину ключа 5, разбиваем текст на 5 столбцов. Частотный анализ каждого столбца показывает, что сдвиги соответствуют буквам K, E, Y, K, E — что и даёт исходный ключ «KEY» (длина 3, но повторение дало ложное значение 5; на практике потребовался бы дополнительный анализ).

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

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

Источники

• Kahn, David. The Codebreakers: The Story of Secret Writing. — Macmillan, 1967.
• Kasiski, F. W. Die Geheimschriften und die Dechiffrir-Kunst. — Berlin, 1863.
• Singh, Simon. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. — Anchor Books, 2000.