Введение

Метод криптоанализа
В криптоанализе, исследование Каски (также известное как тест Каски или метод Каски) — это метод взлома полиалфавитных шифров подстановки, таких как шифр Виженера. Он был впервые опубликован Фридрихом Каски в 1863 году, но, по-видимому, был независимо открыт Чарльзом Бэббиджем еще в 1846 году.

Как это работает

В полиалфавитных шифрах подстановки, где алфавиты подстановки выбираются с использованием ключевого слова, анализ Касиски позволяет криптоаналитику определить длину ключевого слова. Как только длина ключевого слова установлена, криптоаналитик выстраивает шифротекст в n столбцов, где n – длина ключевого слова. Затем каждый столбец можно рассматривать как шифротекст моноалфавитного шифра подстановки. Следовательно, каждый столбец можно подвергнуть частотному анализу. Аналогично, при использовании роторной шифровальной машины этот метод может позволить определить длину отдельных роторов. Анализ Касиски включает в себя поиск повторяющихся последовательностей символов в шифротексте. Для успешного проведения анализа последовательности должны быть длиной не менее трех символов. Затем расстояния между последовательными вхождениями этих последовательностей, вероятно, будут кратны длине ключевого слова. Таким образом, обнаружение большего количества повторяющихся последовательностей сужает возможные значения длины ключевого слова, поскольку можно вычислить наибольший общий делитель всех этих расстояний. Причина, по которой этот тест работает, заключается в том, что если повторяющаяся последовательность встречается в открытом тексте, а расстояние между соответствующими символами кратно длине ключевого слова, то буквы ключевого слова будут выстраиваться одинаково для обоих вхождений этой последовательности. Например, рассмотрим открытый текст:

crypto is short for cryptography.

"" является повторяющейся последовательностью, а расстояние между вхождениями составляет 20 символов. Если выровнять открытый текст с ключевым словом длиной 6 символов "" (6 не делится на 20):

crypto is short for cryptography. первое вхождение "" выравнивается с "" и второе вхождение выравнивается с "". Эти два вхождения будут зашифрованы в разные шифротексты, и анализ Касиски не даст никаких результатов. Однако, при использовании ключевого слова длиной 5 символов "" (5 делится на 20):

crypto is short for cryptography. оба вхождения "" выравниваются с "". Эти два вхождения будут зашифрованы в один и тот же шифротекст, и анализ Касиски будет эффективен.

Нападение на основе струн

Трудность применения исследования Касиски заключается в обнаружении повторяющихся строк. Это очень сложная задача для ручного выполнения, но компьютеры могут значительно упростить её. Однако всё равно требуется осторожность, поскольку некоторые повторяющиеся строки могут быть простым совпадением, и тогда некоторые расстояния между повторами будут вводящими в заблуждение. Криптоаналитику необходимо исключить совпадения, чтобы определить правильную длину ключа. Затем, конечно, полученные моноалфавитные шифротексты необходимо подвергнуть криптоанализу. Криптоаналитик ищет повторяющиеся группы букв и подсчитывает количество букв между началом каждой повторяющейся группы. Например, если шифротекст был , расстояние между группами составляет 10. Аналитик записывает расстояния для всех повторяющихся групп в тексте. Затем аналитик раскладывает каждое из этих чисел на множители. Если какое-либо число повторяется в большинстве этих разложений, вероятно, это и есть длина ключа. Это объясняется тем, что повторяющиеся группы с большей вероятностью возникают, когда одни и те же буквы шифруются одними и теми же буквами ключа, а не просто случайно; это особенно верно для длинных совпадающих строк. Буквы ключа повторяются через интервалы, кратные длине ключа, поэтому большинство расстояний, найденных на первом шаге, скорее всего, будут кратны длине ключа. Обычно можно выявить общий множитель. Как только длина ключа известна, вступает в силу следующее наблюдение Бэббиджа и Касиски. Если ключевое слово состоит из N букв, то каждая N-я буква должна быть зашифрована с использованием одной и той же буквы ключевого текста. Группируя каждую N-ю букву вместе, аналитик получает N "сообщений", каждое из которых зашифровано с помощью простой подстановки, и каждую часть можно атаковать с помощью частотного анализа. Используя расшифрованное сообщение, аналитик может быстро определить, каким было ключевое слово. Или, в процессе расшифровки отдельных частей, аналитик может использовать предположения о ключевом слове, чтобы помочь в разгадке сообщения. Как только перехватчик узнает ключевое слово, эти знания можно использовать для чтения других сообщений, зашифрованных тем же ключом.