Экзамен Касиски

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

• 1 Как это работает
• 2 Атака на основе строк
• 3 Суперпозиция
• 4 Ссылки

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

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

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

криптография - это сокращение от криптографии.

«криптография» - это повторяющаяся строка, а расстояние между вхождениями составляет 20 символов. Если мы выровняем открытый текст с ключевым словом из 6 символов «abcdef» (6 не делится на 20):

abcdef abcdefabcdefab cdefab cdefabc crypto является сокращением от крипто .

первый экземпляр «crypto» совпадает с «abcdef», а второй экземпляр совпадает с «cdefab». Эти два экземпляра будут зашифрованы с использованием разных зашифрованных текстов, и проверка Касиски ничего не покажет. Однако с пятисимвольным ключевым словом «abcde» (5 делится на 20):

abcdea bcdeabcdeabcde abcdea bcdeabc crypto - это сокращение от крипто .

оба вхождения «crypto» совпадают с «abcdea». Оба экземпляра будут зашифрованы с использованием одного и того же зашифрованного текста, и проверка Касиски будет эффективной.

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

1. Криптоаналитик ищет повторяющиеся группы букв и подсчитывает количество букв между началом каждой повторяющейся группы. Например, если зашифрованный текст был FGX THJAQWN FGX Q, расстояние между группами FGX равно 10. Аналитик записывает расстояния для всех повторяющихся групп в тексте..
2. Далее аналитик учитывает каждое из этих чисел. Если какое-либо число повторяется в большинстве этих факторинговых операций, скорее всего, это длина ключевого слова. Это связано с тем, что повторяющиеся группы более вероятны, когда одни и те же буквы зашифрованы с использованием одних и тех же ключевых букв, чем просто по совпадению; это особенно верно для длинных совпадающих строк. Ключевые буквы повторяются с кратной длиной ключа, поэтому большинство расстояний, найденных на шаге 1, скорее всего, будут кратны длине ключа. Обычно очевиден общий фактор.
3. Как только длина ключевого слова известна, в игру вступает следующее наблюдение Бэббиджа и Касиски. Если ключевое слово состоит из Nбукв, то каждая N-я буква должна быть зашифрована с использованием той же буквы ключевого текста. Группируя каждую N-ю букву вместе, аналитик имеет N«сообщений», каждое из которых зашифровано с использованием замены одного алфавита, и каждая часть затем может быть атакована с помощью частотного анализа.
4. Используя решенное сообщение, аналитик может быстро определить, что было за ключевое слово. Или, в процессе решения частей, аналитик может использовать догадки о ключевом слове, чтобы помочь в взломе сообщения.
5. Как только перехватчик узнает ключевое слово, это знание может быть использовано для чтения других сообщений, которые используют тот же ключ.

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

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

Современные аналитики используют компьютеры, но это описание иллюстрирует принцип, который реализуют компьютерные алгоритмы.

Обобщенный метод:

1. Аналитик сдвигает нижнее сообщение на одну букву влево, затем еще на одну букву влево и т. Д., Каждый раз просматривая все сообщение и подсчитывая, сколько раз одна и та же буква появляется в верхнем и нижнем сообщениях.
2. Количество "совпадений" резко возрастает, когда нижнее сообщение сдвигается на кратную длину ключа, потому что тогда соседние буквы на одном языке с использованием тот же алфавит.
3. После определения длины ключа криптоанализ выполняется, как описано выше, с использованием частотного анализа.

.

.