Метод Касиски

В 1863 году Фридрих Вильгельм Касиски опубликовал свой 95-страничный труд «Die Geheimschriften und die Dechiffrirkunst»(«Тайнопись и искусство дешифрирования», оригинал рукописи находится в библиотеке в Мюнхене). Это была книга об атаках на шифры, созданные с помощью полиалфавитной замены. В этой книге Касиски описывает своё крупное открытие в криптоанализе, а именно — алгоритм, известный всем как «Тест Касиски»[2] или «Тест Казисского»[3]. Этот алгоритм позволял взламывать шифр Виженера, взлом которого считался невозможным на протяжении 400 лет. Открытие Касиски уступает по важности только работе Аль-Кинди, известного как «философ арабского мира».[4], который открыл метод частотного анализа для дешифрования текста.

Однако за десять лет до Касиски успеха во взломе шифра Вижинера добился Чарльз Бэббидж. Бэббидж сделал своё открытие в 1854 году, но о нём так никто и не узнал, потому что Бэббидж так и не опубликовал его. Это обнаружилось только в двадцатом веке, когда ученые принялись разбирать его многочисленные заметки. Так почему же Бэббидж не сообщил о том, что сумел взломать этот имеющий столь важное значение шифр? Несомненно, была у него такая привычка — бросать незавершенными значительные и многообещающие начинания и не сообщать о своих открытиях. Имеется, однако, и другое объяснение. Бэббидж сделал своё открытие вскоре после того, как разразилась Крымская война, и в одной из теорий было выдвинуто предположение, что оно давало Британии явное преимущество над Россией, её противником. Вполне возможно, что британская секретная служба потребовала от Бэббиджа сохранить свою работу в секрете, тем самым обеспечив себе девятилетнюю фору перед остальным миром.[2] Так или иначе, взлом шифра Виженера закреплен за Касиски. «Метод Касиски» открыл путь и к другим полиалфавитным решениям, которые до сих пор используют правительства разных стран. Его труд признан величайшей книгой криптологии.

Достижения Чарльза Бэббиджа и Фридриха Касиски показали, что шифр Виженера небезопасен. Это открытие повлекло смятение у криптографов того времени, ведь они теперь не могли гарантировать секретность. И почти на полвека криптоанализ обрел контроль в коммуникационной войне. Криптографы не могли придумать ничего нового, что повлекло рост интереса у широкой публики к шифрам. В конце концов был найден шифр на замену шифра Виженера — так называемый шифр Бейла.[2]

Идея метода основана на том, что ключи являются периодическими, а в естественном языке существуют часто встречающиеся буквосочетания: биграммы и триграммы. Это наводит на мысль, что повторяющиеся наборы символов в шифротексте — повторения популярных биграмм и триграмм исходного текста.

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

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

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

Иллюстрация идеи метода Касиски.

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

Расстояние между двумя повторяющимися подстроками в зашифрованном тексте g. Ключевое слово длиной k повторяется, чтобы заполнить длину зашифрованного текста, расстояние g кратно длине ключевого слова k. Таким образом, если мы видим две повторяющиеся подстроки с расстоянием g, то один из делителей g может быть длиной ключевого слова. Например, если расстояние равно g = 18, поскольку делители g равны 2, 3, 6, 9 и 18, один из них может быть длиной неизвестного ключевого слова.[5]

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

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

Было построено специальное устройство для определения совпадений в тексте и расстояния между ними. Устройство работало с пятью лентами, замыкающимися в петлю, и могло находить повторяющиеся биграммы и триграммы в тексте.

Устройство было довольно быстрым: для обработки набора 10 000 символов, требовалось менее трех часов. Оно служило в основном для получения быстрой информации о текстах, которые были зашифрованы одним и тем же ключом. Устройство было уничтожено в конце войны.[6]

Пример 1

Рассмотрим следующий пример, зашифрованный ключевым словом ION. Подстрока BVR в зашифрованном тексте повторяется три раза. Первые два зашифрованы с помощью ION. Так как ключевое слово ION сдвигается вправо несколько раз, расстояние между B в первом вхождении BVR и вторым кратно длине ключевого слова 3. Второе и третье вхождения BVR зашифровываются как THE и NIJ, используя разные части ключевого слова (то есть ION и ONI), а расстояние между двумя B во втором и третьем BVR может не быть кратным длине ключевого слова. Поэтому даже мы находим повторяющиеся подстроки, расстояние между ними может быть или не быть кратным длине ключевого слова, а повторения могут быть просто случайными.

Пример 2

В длинном зашифрованном тексте больше шансов найти повторяющиеся подстроки. Короткий текст, зашифрованный относительно длинным ключевым словом, может создать зашифрованный текст, в котором не будет повторения. Кроме того, подстроки, повторяющиеся много раз, в зашифрованном тексте вряд ли будут случайными, тогда как короткие повторные подстроки могут появляться чаще и некоторые из них могут быть исключительно случайными. В данном примере показано шифрование Michigan Technological University с ключевым словом boy. Нет повторной подстроки длиной не менее 2. В данном случае метод Касиски терпит неудачу.

Пример 3

Рассмотрим более длинный открытый текст. Ниже приводится цитата Чарльза Энтони Ричарда, победителя премии ACM Turing 1980 года по разработке программного обеспечения:

После удаления пробелов и пунктуации и преобразования в верхний регистр получается следующее:

Затем полученный текст шифруется с помощью 6 буквенного ключевого слова SYSTEM следующим образом:

Сравним текст, ключевое слова и зашифрованный текста. Выделенный в таблице текст означает повторяющиеся подстроки длиной 8. Это самые длинные подстроки длиной менее 10 в зашифрованном тексте. Строка открытого текста THEREARE появляется три раза в позициях 0, 72 и 144. Расстояние между двумя вхождениями равно 72. Повторяющееся ключевое слово и зашифрованный текст представляют собой SYSTEMSY и LFWKIMJC соответственно. Следовательно, эти три события не случайны, а 72 кратно длине ключевого слова 6.

Следующая самая длинная повторяющаяся подстрока WMLA в зашифрованном тексте имеет длину 4 и встречается в положениях 108 и 182. Расстояние между этими двумя положениями равно 74. В позиции 108 не зашифрованный EOTH зашифрован для WMLA с использованием SYST. В позиции 182 открытый текст ETHO шифруется WMLA с использованием STEM. В этом случае, даже если мы найдем повторяющиеся подстроки WMLA, они не зашифрованы одной и той же частью ключевого слова, и они поступают из разных разделов открытого текста. В результате это повторение является чистой случайностью, и расстояние 74 вряд ли будет кратным длине ключевого слова.

Существует пять повторяющихся подстрок длины 3. Они являются MJC в положениях 5 и 35 с расстоянием 30, ISW в позициях 11 и 47 (расстояние = 36), KMK в положениях 28 и 60 (расстояние = 32), VMQ в положениях 99 и 165 (расстояние = 66) и DAV в положениях 163 и 199 (расстояние = 36). Следующая таблица представляет собой сводку. Повторяющийся зашифрованный текст KWK зашифрован из двух разделов открытого текста GAS и SOS с частями ключевого слова EMS и SYS, соответственно. Поэтому это чистый шанс.

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

В следующей таблице указаны расстояния и все факторы, не превышающие 20. Последняя строка таблицы имеет общее количество каждого фактора. Ясно, что факторы 2, 3 и 6 встречаются чаще всего со счетами 6, 4 и 4 соответственно. Поскольку длина ключевого слова 2 слишком мала, чтобы эффективно использоваться, длины 3 и 6 более разумны. В результате мы можем использовать 3 и 6 в качестве исходных оценок для восстановления ключевого слова и расшифровки зашифрованного текста.

Если мы убеждены, что некоторые расстояния, вероятно, не будут случайными, мы можем вычислить наибольший общий делитель (НОД) этих расстояний и использовать его как возможную длину ключевого слова. Как упоминалось ранее, расстояния 74 и 32 могут быть случайными, а оставшиеся расстояния равны 72, 66, 36 и 30. Их НОД - это НОД(72, 66, 36, 30) = 6. Поскольку мы знаем ключевое слово SYSTEM, 6 - правильная длина. Если у нас есть только зашифрованный текст, мы должны выполнить некоторые предположения.

[5]

Пример 4

АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ   - чистый алфавит
ЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЖЗИ   - 1-й алфавит
ГАЭЪЧФСОЛИЕВЯЬЩЦУРНКЗДБЮЫШХТПМЙЖ   - 2-й алфавит
БФЗЪНАУЖЩМЯТЕШЛЮСДЧКЭРГЦЙЬПВХИЫО   - 3-й алфавит
ПЪЕРЫЖСЬЗТЭИУЮЙФЯКХАЛЦБМЧВНШГОЩД   - 4-й алфавит

• Полиалфавитный шифр
• Автокорреляционный метод (криптоанализ)
• Метод индекса совпадений
• Частотный анализ

• Габидулин Э. М., А. С. Кшевецкий, А. И. Колыбельников. Защита информации. — МФТИ, 2011. — 262 с.
• Н. Смарт. Криптография. — Техносфера, 2005. — 526 с.
• С. Сингх. Тайная история шифров и их расшифровки. — Астрель, 2006. — 447 с.
• Tilborg H.C.A. Fundamentals of Cryptography. A Professional Reference and Interactive Tutorial. — Kluwer, 1999. — 503 с.
• Menezes A.J., Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 с.
• Beutelspacher A. Cryptology
• Kahn D. The Codebreakers – The Story of Secret Writing - 1968
• Bishop M., Wesley A. Computer Security - 2003