Касиски экспертиза - Kasiski examination

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

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

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

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

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

crypto is short for cryptography.

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

abcdefabcdefabcdefabcdefabcdefabc
crypto is short for cryptography.

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

abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto is short for cryptography.

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

Атака на основе строк

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

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

Наложение

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

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

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

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

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

Рекомендации