stringtranslate.com

обследование Касиски

В криптоанализе проверка Касиски ( также известная как тест Касиски или метод Касиски ) — это метод атаки на шифры многоалфавитной замены , такие как шифр Виженера . [1] [2] Впервые он был опубликован Фридрихом Касиски в 1863 году, [3] но, похоже, был независимо обнаружен Чарльзом Бэббиджем еще в 1846 году. [4] [5]

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

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

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

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

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

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

abcdef abcdefabcdefab cdefab cdefabc crypto — сокращение от шифрования .

первый экземпляр « crypto » соответствует « abcdef », а второй — « cdefab ». Два экземпляра будут зашифрованы разными зашифрованными текстами, и проверка Касиски ничего не покажет. Однако с помощью 5-значного ключевого слова « 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. Найдя длину ключа, криптоанализ продолжается, как описано выше, с использованием частотного анализа .

Внешние ссылки

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

  1. ^ Родригес-Кларк, Дэниел, Анализ Касиски: Взлом кода , получено 30 ноября 2014 г.
  2. ^ Р. Морелли, Р. Морелли, Историческая криптография: шифр Виженера, Тринити-колледж Хартфорд, Коннектикут , получено 4 июня 2015 г.
  3. ^ Касиски, FW 1863. Die Geheimschriften und die Dechiffrir-Kunst. Берлин: ES Mittler und Sohn
  4. ^ Франксен, О.И., 1985. Секрет мистера Бэббиджа: история шифра - и APL. Прентис Холл
  5. ^ Сингх, Саймон (1999), Кодовая книга: наука о секретности от Древнего Египта до квантовой криптографии , Лондон: Четвертое сословие, стр. 78, ISBN 1-85702-879-1
  6. ↑ Метод Касиски, Мичиганский технологический университет , получено 1 июня 2015 г.