Метод Каси́ски (Метод Кази́ского) — метод криптоанализа полиалфавитных шифров, таких как шифр Виженера. Основан на факте того, что повторяющиеся части открытого текста, зашифрованные одним и тем же ключевым словом, приводят к идентичным сегментам шифрованного текста. Разработан независимо криптоаналитиками Фридрихом Касиски и Чарльзом Бэббиджем.
История
В 1863 году Фридрих Вильгельм Касиски опубликовал свой 95-страничный труд «Die Geheimschriften und die Dechiffrirkunst»(«Тайнопись и искусство дешифрирования», оригинал рукописи находится в библиотеке в Мюнхене). Это была книга методах дешифровки кодов, созданных с помощью полиалфавитной замены. В этой книге Касиски описывает алгоритм, получивший название «метод Касиски» или «метод Казисского». Этот алгоритм позволял взламывать шифр Виженера, что считалось невозможным на протяжении 400 лет. Метод основан на частотном анализе кода. Открытие Касиски уступает по важности только работе Аль-Кинди, известного как «философ арабского мира», который открыл метод частотного анализа для дешифрования текста.
Однако за десять лет до Касиски шифр Вижинера раскрыл Чарльз Бэббидж. Бэббидж сделал своё открытие в 1854 году, но о нём так никто и не узнал, потому что Бэббидж так и не опубликовал его. Это обнаружилось только в двадцатом веке, когда ученые принялись разбирать его многочисленные заметки. Так почему же Бэббидж не сообщил о том, что сумел взломать этот имеющий столь важное значение шифр? Несомненно, была у него такая привычка — бросать незавершенными значительные и многообещающие начинания и не сообщать о своих открытиях. Имеется, однако, и другое объяснение. Бэббидж сделал своё открытие вскоре после того, как разразилась Крымская война, и в одной из теорий было выдвинуто предположение, что оно давало Британии явное преимущество над Россией, её противником. Вполне возможно, что британская секретная служба потребовала от Бэббиджа сохранить свою работу в секрете, тем самым обеспечив себе девятилетнюю фору перед остальным миром. Так или иначе, взлом шифра Виженера закреплен за Касиски. «Метод Касиски» открыл путь и к другим полиалфавитным решениям, которые до сих пор используют правительства разных стран. Его труд признан величайшей книгой криптологии.
Достижения Чарльза Бэббиджа и Фридриха Касиски показали, что шифр Виженера небезопасен. Это открытие повлекло смятение у криптографов того времени, ведь они теперь не могли гарантировать секретность. И почти на полвека криптоанализ обрел контроль в коммуникационной войне. Криптографы не могли придумать ничего нового, что повлекло рост интереса у широкой публики к шифрам.
Идея Идея метода основана на том, что ключи являются периодическими, а в естественном языке существуют часто встречающиеся буквосочетания: биграммы и триграммы. Это наводит на мысль, что повторяющиеся наборы символов в шифротексте — повторения популярных биграмм и триграмм исходного текста.
Метод Касиски позволяет криптоаналитику найти длину ключевого слова, используемого в полиалфавитном шифре. Как только длина ключевого слова обнаружена, криптоаналитик выстраивает зашифрованный текст в n колонках, где n — длина ключевого слова. Тогда каждую колонку можно рассматривать как зашифрованный моноалфавитным шифром текст, который можно подвергнуть частотному анализу.
Метод Касиски заключается в поиске групп символов, которые повторяются в зашифрованном тексте. Группы должны состоять из не менее чем трех символов. Тогда расстояния между последовательными возникновениями групп, вероятно, будут кратны длине ключевого слова. Предполагаемая длина ключевого слова кратна наибольшему общему делителю всех расстояний.
Причина, по которой метод работает — это то, что если две группы символов повторяются в исходном тексте и расстояние между ними является кратным длине ключевого слова, то буквы ключевого слова выровняются с обеими группами.
Описание
Если повторяющаяся подстрока в открытом тексте зашифровывается одной и той же подстрокой в ключевом слове, тогда шифрованный текст содержит повторяющуюся подстроку, а расстояние между двумя вхождениями кратно длине ключевого слова.
Расстояние между двумя повторяющимися подстроками в зашифрованном тексте g. Ключевое слово длиной k повторяется, чтобы заполнить длину зашифрованного текста, расстояние g кратно длине ключевого слова k. Таким образом, если мы видим две повторяющиеся подстроки с расстоянием g, то один из делителей g может быть длиной ключевого слова. Например, если расстояние равно g = 18, поскольку делители g равны 2, 3, 6, 9 и 18, один из них может быть длиной неизвестного ключевого слова.
Свойства Сложность метода Касиски состоит в необходимости поиска повторяющихся строк. Это сложно сделать вручную, но значительно проще на компьютере. Однако метод требует вмешательства человека, так как некоторые совпадения могут оказаться случайными, что приведет к тому, что наибольший общий делитель всех расстояний будет равен 1. Криптоаналитик должен выяснить, какие длины являются подходящими. И, в конечном итоге, человек должен проверить правильность подобранного периода исходя из осмысленности расшифрованного текста.
Применение Несмотря на свою слабость, метод Касиски использовался в качестве вспомогательного во Второй мировой войне.
Было построено специальное устройство для определения совпадений в тексте и расстояния между ними. Устройство работало с пятью лентами, замыкающимися в петлю, и могло находить повторяющиеся биграммы и триграммы в тексте.
Устройство было довольно быстрым: для обработки набора 10 000 символов, требовалось менее трех часов. Оно служило в основном для получения быстрой информации о текстах, которые были зашифрованы одним и тем же ключом. Устройство было уничтожено в конце войны.
Примеры Пример 1
Рассмотрим следующий пример, зашифрованный ключевым словом ION. Подстрока BVR в зашифрованном тексте повторяется три раза. Первые два зашифрованы с помощью ION. Так как ключевое слово ION сдвигается вправо несколько раз, расстояние между B в первом вхождении BVR и вторым кратно длине ключевого слова 3. Второе и третье вхождения BVR зашифровываются как THE и NIJ, используя разные части ключевого слова (то есть ION и ONI), а расстояние между двумя B во втором и третьем BVR может не быть кратным длине ключевого слова. Поэтому даже мы находим повторяющиеся подстроки, расстояние между ними может быть или не быть кратным длине ключевого слова, а повторения могут быть просто случайными. Текст......THE................THE.....................NIJ...........Ключевое слово......ION................ION....................IONI...........Зашифрованный текст......BVR................BVR.....................BVR...........
Пример 2
В длинном зашифрованном тексте больше шансов найти повторяющиеся подстроки. Короткий текст, зашифрованный относительно длинным ключевым словом, может создать зашифрованный текст, в котором не будет повторения. Кроме того, подстроки, повторяющиеся много раз, в зашифрованном тексте вряд ли будут случайными, тогда как короткие повторные подстроки могут появляться чаще и некоторые из них могут быть исключительно случайными. В данном примере показано шифрование Michigan Technological University с ключевым словом boy. Нет повторной подстроки длиной не менее 2. В данном случае метод Касиски терпит неудачу. MICHI GANTE CHNOL OGICA LUNIV ERSIT YBOYBO YBOYB OYBOY BOYBO YBOYB OYBOY BNWAIW EBBRF QFOCJ PUGDO JVBGW SPTWR Z
Пример 3
Рассмотрим более длинный открытый текст. Ниже приводится цитата Чарльза Энтони Ричарда, победителя премии ACM Turing 1980 года по разработке программного обеспечения: There are two ways of constructing a software design:One way is to make it so simple that there are obviouslyno deficiencies, and the other way is to make it so complicatedthat there are no obvious deficiencies.The first method is far more difficult. После удаления пробелов и пунктуации и преобразования в верхний регистр получается следующее: THERE ARETW OWAYS OFCON STRUC TINGA SOFTW AREDE SIGNO NEWAYISTOM AKEIT SOSIM PLETH ATTHE REARE OBVIO USLYN ODEFI CIENC IESAN DTHEO THERW AYIST OMAKE ITSOC OMPLI CATED THATT HEREARENOO BVIOU SDEFI CIENC IESTH EFIRS TMETH ODISF ARMOR EDIFFICULT Затем полученный текст шифруется с помощью 6 буквенного ключевого слова SYSTEM следующим образом: LFWKI MJCLP SISWK HJOGL KMVGU RAGKM KMXMA MJCVX WUYLG GIISWALXAE YCXMF KMKBQ BDCLA EFLFW KIMJC GUZUG SKECZ GBWYM OACFVMQKYF WXTWM LAIDO YQBWF GKSDI ULQGV SYHJA VEFWB LAEFL FWKIMJCFHS NNGGN WPWDA VMQFA AXWFZ CXBVE LKWML AVGKY EDEMJ XHUXDAVYXL Сравним текст, ключевое слова и зашифрованный текста. Выделенный в таблице текст означает повторяющиеся подстроки длиной 8. Это самые длинные подстроки длиной менее 10 в зашифрованном тексте. Строка открытого текста THEREARE появляется три раза в позициях 0, 72 и 144. Расстояние между двумя вхождениями равно 72. Повторяющееся ключевое слово и зашифрованный текст представляют собой SYSTEMSY и LFWKIMJC соответственно. Следовательно, эти три события не случайны, а 72 кратно длине ключевого слова 6. THERE ARETW OWAYS OFCON STRUC TINGA SOFTW AREDE SIGNO NEWAYSYSTE MSYST EMSYS TEMSY STEMS YSTEM SYSTE MSYST EMSYS TEMSYLFWKI MJCLP SISWK HJOGL KMVGU RAGKM KMXMA MJCVX WUYLG GIISWISTOM AKEIT SOSIM PLETH ATTHE REARE OBVIO USLYN ODEFI CIENCSTEMS YSTEM SYSTE MSYST EMSYS TEMSY STEMS YSTEM SYSTE MSYSTALXAE YCXMF KMKBQ BDCLA EFLFW KIMJC GUZUG SKECZ GBWYM OACFVIESAN DTHEO THERW AYIST OMAKE ITSOC OMPLI CATED THATT HEREAEMSYS TEMSY STEMS YSTEM SYSTE MSYST EMSYS TEMSY STEMS YSTEMMQKYF WXTWM LAIDO YQBWF GKSDI ULQGV SYHJA VEFWB LAEFL FWKIMRENOO BVIOU SDEFI CIENC IESTH EFIRS TMETH ODISF ARMOR EDIFFSYSTE MSYST EMSYS TEMSY STEMS YSTEM SYSTE MSYST EMSYS TEMSYJCFHS NNGGN WPWDA VMQFA AXWFZ CXBVE LKWML AVGKY EDEMJ XHUXDICULTSTEMSAVYXL Следующая самая длинная повторяющаяся подстрока WMLA в зашифрованном тексте имеет длину 4 и встречается в положениях 108 и 182. Расстояние между этими двумя положениями равно 74. В позиции 108 не зашифрованный EOTH зашифрован для WMLA с использованием SYST. В позиции 182 открытый текст ETHO шифруется WMLA с использованием STEM. В этом случае, даже если мы найдем повторяющиеся подстроки WMLA, они не зашифрованы одной и той же частью ключевого слова, и они поступают из разных разделов открытого текста. В результате это повторение является чистой случайностью, и расстояние 74 вряд ли будет кратным длине ключевого слова. IESAN DTHEO THERW AYIST OMAKE ITSOC OMPLI CATED THATT HEREAEMSYS TEMSY STEMS YSTEM SYSTE MSYST EMSYS TEMSY STEMS YSTEMMQKYF WXTWM LAIDO YQBWF GKSDI ULQGV SYHJA VEFWB LAEFL FWKIMRENOO BVIOU SDEFI CIENC IESTH EFIRS TMETH ODISF ARMOR EDIFFSYSTE MSYST EMSYS TEMSY STEMS YSTEM SYSTE MSYST EMSYS TEMSYJCFHS NNGGN WPWDA VMQFA AXWFZ CXBVE LKWML AVGKY EDEMJ XHUXDICULTSTEMSAVYXL Существует пять повторяющихся подстрок длины 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, соответственно. Поэтому это чистый шанс. Позиция5351147286099165163199Расстояние3036326636ТекстAREAREWAYWAYGASSOSCIECIEFICFICКлючевое словоMSYMSYMSYMSYEMSSYSTEMTEMYSTYSTШифрованный текстMJCMJCISWISWKMKKMKVMQVMQDAVDAV В следующей таблице указаны расстояния и их факторы. Поскольку расстояние может быть кратным длине ключевого слова, фактором расстояния может быть длина ключевого слова. Если совпадение по чистой случайности, факторы этого расстояния могут не быть факторами длины ключевого слова. В общем, хороший выбор - самый большой, который появляется чаще всего. Более длинные повторяющиеся подстроки могут предлагать лучший выбор, потому что эти совпадения с меньшей вероятностью случайны. ДлинаРасстояниеФакторы8722 3 4 6 8 9 12 18 24 36 724742 37 743662 3 6 11 22 33 66362 3 4 6 9 12 18 36322 4 8 16 32302 3 5 6 10 15