Тест Касиски

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

История

До появления метода Касиски многоалфавитные шифры, такие как шифр Виженера, долгое время считались практически невзламываемыми. Шифр Виженера, изобретённый в XVI веке, использовал ключевое слово для циклического сдвига алфавита, что делало его устойчивым к частотному анализу — основному инструменту криптоанализа того времени.

В 1863 году Фридрих Вильгельм Касиски, бывший прусский артиллерийский офицер, опубликовал книгу «Die Geheimschriften und die Dechiffrir-Kunst» («Тайнопись и искусство дешифровки»), в которой впервые описал метод определения длины ключа по повторяющимся фрагментам шифротекста. Это стало революционным прорывом, так как позволяло свести задачу взлома многоалфавитного шифра к серии простых одноалфавитных замен.

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

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

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

Алгоритм

Процесс применения теста Касиски состоит из нескольких этапов:

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

Пример

Допустим, зашифрованный текст содержит повторяющуюся триграмму «XYZ» на позициях 10 и 34. Расстояние между ними — 24 символа. Если длина ключа равна 6, то 24 делится на 6 без остатка (24 / 6 = 4). Если длина ключа равна 8, то 24 также делится на 8. Анализируя множество таких расстояний, криптоаналитик находит наиболее вероятную длину ключа.

Применение

Тест Касиски используется исключительно как первый этап криптоанализа многоалфавитных шифров. После того как длина ключа определена, дальнейший взлом осуществляется другими методами:

• Частотный анализ. Зашифрованный текст разбивается на группы символов, зашифрованных одним и тем же символом ключа (каждая позиция ключа образует свой «слой»). Каждый такой слой представляет собой шифр простой замены (шифр Цезаря) и может быть взломан стандартным частотным анализом.
• Метод перебора ключа. Если длина ключа невелика (например, до 10 символов), возможен полный перебор всех вариантов ключа с проверкой осмысленности полученного открытого текста.

Ограничения

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

• Длина текста. Для надёжного определения длины ключа требуется достаточно длинный зашифрованный текст. Чем длиннее ключ, тем больше текста необходимо. Для ключа длиной 10 символов требуется не менее 200–300 символов шифротекста.
• Повторяемость. Метод плохо работает, если открытый текст не содержит повторяющихся слов или если ключ не повторяется (например, при использовании одноразового блокнота).
• Случайные совпадения. Возможны ложные срабатывания, когда повторяющаяся последовательность в шифротексте образована разными фрагментами открытого текста и разными частями ключа. Для минимизации ошибок рекомендуется использовать повторы длиной не менее 3–4 символов.

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

Тест Касиски часто сравнивают с тестом Фридмана (индексом совпадений). Оба метода решают одну задачу — определение длины ключа, но подходят к ней по-разному:

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

Значение в криптографии

Тест Касиски сыграл ключевую роль в истории криптографии, продемонстрировав, что даже сложные многоалфавитные шифры уязвимы для систематического анализа. Его появление привело к развитию более надёжных методов шифрования, таких как роторные машины (например, «Энигма») и современные блочные шифры (AES, ГОСТ 28147-89).

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

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

• Фридрих Вильгельм Касиски не был профессиональным математиком или криптографом. Он служил в прусской армии, а после выхода в отставку занялся изучением шифров.
• Метод Касиски был независимо открыт ещё в XVI веке итальянским математиком Джованни Баттистой делла Порта, но его работа осталась незамеченной.
• Шифр Виженера, который взламывает тест Касиски, долгое время называли «неразгаданным шифром» (le chiffre indéchiffrable), пока Касиски не опроверг это название.

Источники

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