Русская Википедия:Автокорреляционный метод
Автокорреляционный метод — это метод криптоанализа полиалфавитных шифров, например таких как шифр Виженера.
Описание метода
Автокорелляционный метод позволяет криптоаналитику найти длину <math>l</math> ключевого слова, используемого в полиалфавитном шифре. Как только длина ключевого слова обнаружена, криптоаналитик выстраивает зашифрованный текст в <math>l</math> колонках. При этом каждую колонку можно рассматривать как зашифрованный моноалфавитным шифром текст, который можно подвергнуть частотному анализу.
Данный метод позволяет отыскать длину ключевого слова с лучшей точностью, чем метод КасискиШаблон:Sfn.
Сам метод состоит в том, что исходный шифротекст <math>(c_1, c_2, \dotsc, c_L)</math> выписывается в строку, а под ней выписываются строки, полученные сдвигом вправо на <math>t = 1, 2, 3, \dotsc</math> позиций. Для каждого <math>t</math> подсчитывается число <math>n_t</math> совпадений <math>c_i = c_{i+t}</math>, где <math>i \in \left[ 1, L -t \right]</math> и вычисляются автокорреляционные коэффициенты <math>\gamma_t</math>:
- <math>\gamma_t = \dfrac{n_t}{L-t}</math>
Для сдвигов, кратных периоду, коэффициенты <math>\gamma_t</math> должны быть заметно больше, чем для сдвигов, не кратных периоду, и иметь значение близкое к индексу совпадений используемого языкаШаблон:SfnШаблон:Sfn (для русского языка ~ 0.0553). Это объясняется следующим образом. Когда величина сдвига кратна длине ключевого слова, символы <math>c_i </math> и <math>c_{i+t}</math> шифруются одинаковым моноалфавитным шифром, что не изменяет факт их совпадения. А так как индекс совпадений вводится как вероятность совпадения двух произвольных букв в строке, то для сдвигов, кратных или равных периоду, автокорреляционные коэффициенты, при достаточно большой длине текста, будут близки к индексу совпадений естественного языкаШаблон:Sfn.
Пример использования
Пусть шифруется следующий текст без учета знаков препинания и различия строчных и прописных букв (буквы И и Й также не различаются). Шаблон:Начало цитаты Все, чему мне случилось быть здесь свидетелем, не было мне совершенно незнакомым, о подобных случаях я где-то что-то читал и теперь вспомнил, что поведение людей, попадавших в аналогичные обстоятельства, всегда представлялось мне необычайно, раздражающе нелепым. Вместо того чтобы полностью использовать увлекательные перспективы, открывшиеся для них счастливым случаем, они пугались, старались вернуться в обыденное. Какой-то герой даже заклинал читателей держаться подальше от завесы, отделяющей наш мир от неведомого, пугая духовными и физическими увечьями. Я ещё не знал, как развернутся события, но уже был готов с энтузиазмом окунуться в них. Бродя по комнате в поисках ковша или кружки, я продолжал рассуждать. Эти пугливые люди, думал я, похожи на некоторых ученых-экспериментаторов, очень упорных, очень трудолюбивых, но начисто лишенных воображения и поэтому очень осторожных. Получив нетривиальный результат, они шарахаются от него, поспешно объясняют его нечистотой эксперимента и фактически уходят от нового, потому что слишком сжились со старым, уютно уложенным в пределы авторитетной теории. Я уже обдумывал кое-какие эксперименты с книгой-перевертышем (она по-прежнему лежала на подоконнике и была теперь «Последним изгнанником» Олдриджа), с говорящим зеркалом и с цыканьем. У меня было несколько вопросов к коту Василию, да и русалка, живущая на дубе, представляла определённый интерес, хотя временами мне казалось, что она-то мне все-таки приснилась. Я ничего не имею против русалок, но не представляю себе, как они могут лазить по деревьям… хотя, с другой стороны, чешуя?.. Шаблон:Конец цитаты
Воспользуемся шифром Виженера с ключевым словом КЛЮЧ. Зашифрованное сообщение:
МЫГОПЦСВЦРПБЬБЖБЧЫЪШДЬЪЮОРПУЪНЖЫПЬГБПЦЛЬЛЕИДХЧГЗЧНГЖБРЛГЧЧГЮ ЦЛЗДХЕКДШШВДЛЧЩМЪХСОККУЦНПГИЧБРДЫШХЯЫЛИЯЫРНЬЩЖАЗШШКГТХХИЧЩМЩ ППГГТРИХОРЖЕЧЩЮЫКНЦЯЮНЮГКХМЪТБЛТПШЯЗЫШЭИПХЪЗЫНЮЩЪРБЫКЩОЬОЫРЧ МХЭБЧЫЪВЦРЛЬЧМЩОКУЛДЩЛЕЫЩЛДЧЗГГГПХГЕДЦАВПЫРДЫШБДАЬМШДЩМБЦШПИ ЕИЖЗШШИУСШАЧЫЖСЩФРЗЧЫРИУЦЕГЕПЪПЕПФРЯМЕМИУЪЩЩБУГЗИПИЦЦУУЗАЛПИ ФУАТХЫИКАЛГВЧЧЖЕЬОЮБТЫЪЗЫЛОЧФУПУМРОГЬЬЪЗИНМШДПГГЦШГАКФМЯЫШБЬ ЩШЖЫКСГЮКФИЯЦЛИОТЬЮИПХГЯОРОЭКЬЪЗИЩМЫКХЪППШРЮКНГЗДШРЫПХЭХВРЖГ КВКЯЩШРГПНГЫЧЦМЪЧЩСЪККВКЮШАГДЦЖЯЭУЕЯАРПАТЦЖКМРХУИЦЖЦПГГГПТЛЧ ФФЮАЩЛЕЩПЪЛКЫЫЭЗЧМЩИТКЛДЬСГШДХБДЫШАЗЖЧРКСУЮЮХШКДУЭЛКЫЖПЦМЧЖМ ЛЪМЫИЩМАЧЦЛЧЫРАЕЧУПАКЯЗДМВЮЯФУЗЖЬСЗЯИЩОДОШИЭКХОЧЪЫСЭОЛРУЖЬЖЕ ЬОИЯМЕГБЗПЖЫЬЦЮБИЩММЧСЖГКЧГАЧЬМЖДЯСОПЧЩМЖФПЕПЪЖВПЧРЧЫШОДМШХЬ ЦЖСЕЧЪЛТЮШХЬЦЖРЖЬПМБЗМЖЩДЯЛДЦЛХЯЪЬМБТВГГЦЕУЩЧШЯЖКСГГТКЖЕЧЗРД ХЭМОПЧЪДЪЬМЖЧСЛТЮЩМБЬБЖЩЦРРЖТНЖЧФЖЛТТЪГЮЬХЪИКЬМГТВЮЖКЯЮХЫЫЭД ЫЧГЪЧЩМЗШРЦГЧШЯСИЫЛЦЗЬГЪЧЧГОТЫРДЫШЖФУЫНЬЩУКЬЦЬЮЯЭЛЗИТБГЗУУСМ ЧПЭИЧЬЛДМШБДШШРДХЭХИЧЫИЯБФМВЪСЖБТЫЪЗЧЫРЧЩЕККЗЬЛДЬХМЭПЧЛТХННЖ ППГБДЛАИЧЪЖИПЬЛДТЬГДЩУЖЦЬСГДЛПСВДНЮБУШГАКФЖЬЖФПЕПЪЖВПЧРТЪФЛЯ НШЖЕПЪГЩПЪРТБРКДЦЛНДШЪГЭЦРККФРДЧФЛЛЧШШВДУШЛГТФГЯЛЕИЧЫРНЬЩЖНД ЪХГЫЦУКЯСОЛЧЦЧЖАЧЦМБОЪЖЫРЛПЪЧНМЖИГЖВСРОАКХМВТЫФТУЛЛУПЦСВПЧЭШ ДХМГПЫЗДФЖЗДМШНЖЧЫМЩУФМИЬНЮЗТХЖХОЛЖЖЬЫЮБУЛДЯМЭЧЧИЧЮЫЬМГЕЩРВЗ ЫЛАБИХЮДШЪГЫПХГГЦЕЖЯЦЬГЖПЫУДЫКАЖПЦГГКЦЖВЦРЗЧСЛИДЪЖХИЧШЛЧЫШКГ ПНПЬЫЛЗЯШЪЖЗЦУИЧЪЖЭГТБГЪЧЧГЯХРЬЕЩШРЯМЪСЗКХМАЦШЛЬШЪГЫЪЬЮЩФКЬЗ ПМГАКФМГТЦМЪЬЬИЧСУРУШШВЬЩРАУИЦУДЫКПЫЩЭБДТЫРДЩШЛТАРЦКИ
Вычислим автокорреляционные коэффициенты для сдвигов <math>t = 1,\dotsc,200</math> и построим график <math> \gamma(t)</math>. Среднее расстояние между пиковыми значениями функции равно 4, значит предполагаемая длина ключевого слова равна 4, что совпадает с использованной.
Далее необходимо найти частоты встречаемости букв для шифротекстов, полученных из <math>l = 4</math> колонок.
- Частоты встречаемости букв шифротекстов из различных колонок
-
Шифротекст 1
-
Шифротекст 2
-
Шифротекст 3
-
Шифротекст 4
Предположим, что при шифровании использовался шифр Виженера. Тогда для расшифровки всех четырёх шифротекстов необходимо сравнить распределения частот встречаемости букв в шифротекстах с распределением естественного языка. Наилучшим образом это можно сделать при помощи критерия согласия Пирсона. Найдем значения критерия <math> \chi^2</math> для распределений, получаемых циклическим сдвигом вправо из распределения частот встречаемости букв в русском языке.
| Значения критерия <math>\chi^2</math> для различных шифротекстов | ||||
|---|---|---|---|---|
| Тестируемый сдвиг | Шифротекст 1 | Шифротекст 2 | Шифротекст 3 | Шифротекст 4 |
| 0 | 187,33 | 236,14 | 305,90 | 200,40 |
| 1 | 290,44 | 273,37 | 113,24 | 304,52 |
| 2 | 272,67 | 273,02 | 219,89 | 236,90 |
| 3 | 177,16 | 228,69 | 174,97 | 207,69 |
| 4 | 98,71 | 163,95 | 310,41 | 155,80 |
| 5 | 128,73 | 109,71 | 422,07 | 303,72 |
| 6 | 131,38 | 120,38 | 195,10 | 311,95 |
| 7 | 149,33 | 104,18 | 212,48 | 237,96 |
| 8 | 186,87 | 108,03 | 345,46 | 188,55 |
| 9 | 41,01 | 133,46 | 687,30 | 305,10 |
| 10 | 149,77 | 38,14 | 323,51 | 499,16 |
| 11 | 203,27 | 106,64 | 220,85 | 273,98 |
| 12 | 98,06 | 166,77 | 506,90 | 207,85 |
| 13 | 160,70 | 107,82 | 403,45 | 254,92 |
| 14 | 153,22 | 158,91 | 359,30 | 251,65 |
| 15 | 329,41 | 125,60 | 231,77 | 227,18 |
| 16 | 339,94 | 293,00 | 348,73 | 149,73 |
| 17 | 185,61 | 328,77 | 448,32 | 91,33 |
| 18 | 189,05 | 180,04 | 228,15 | 95,76 |
| 19 | 280,02 | 198,82 | 173,35 | 108,07 |
| 20 | 505,03 | 274,43 | 187,07 | 87,90 |
| 21 | 259,86 | 357,71 | 254,99 | 71,54 |
| 22 | 159,53 | 267,11 | 217,55 | 38,73 |
| 23 | 315,64 | 163,35 | 128,58 | 115,03 |
| 24 | 300,66 | 234,87 | 87,64 | 159,85 |
| 25 | 254,91 | 310,44 | 118,82 | 95,58 |
| 26 | 175,78 | 293,11 | 116,28 | 118,71 |
| 27 | 259,02 | 216,49 | 180,47 | 139,34 |
| 28 | 424,97 | 263,13 | 259,86 | 290,69 |
| 29 | 240,80 | 479,59 | 45,60 | 283,53 |
| 30 | 182,17 | 259,69 | 170,44 | 138,66 |
Итак, получили значения сдвигов, используемых в моноалфавитных шифрах каждой из колонок: 9,10,22,29. Для выбранного алфавита это соответствует ключевому слову шифра Виженера КЛЮЧ. Текст расшифрован.
См. также
Примечания
Литература
Ссылки
- Lecture notes in cryptogtaphy Thomas Johansson
