Автокорреляционный метод

Автокорреляционный метод — это метод криптоанализа полиалфавитных шифров, например таких как шифр Виженера.

Описание метода

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

Данный метод позволяет отыскать длину ключевого слова с лучшей точностью, чем метод Касиски.

Сам метод состоит в том, что исходный шифротекст $(c_{1},c_{2},\dotsc ,c_{L})$ выписывается в строку, а под ней выписываются строки, полученные сдвигом вправо на $t=1,2,3,\dotsc$ позиций. Для каждого $t$ подсчитывается число $n_{t}$ совпадений $c_{i}=c_{i+t}$, где $i\in \left[1,L-t\right]$ и вычисляются автокорреляционные коэффициенты $\gamma _{t}$:

$\gamma _{t}={\dfrac {n_{t}}{L-t}}$

Для сдвигов, кратных периоду, коэффициенты $\gamma _{t}$ должны быть заметно больше, чем для сдвигов, не кратных периоду, и иметь значение близкое к индексу совпадений используемого языка (для русского языка ~ 0.0553). Это объясняется следующим образом. Когда величина сдвига кратна длине ключевого слова, символы $c_{i}$ и $c_{i+t}$ шифруются одинаковым моноалфавитным шифром, что не изменяет факт их совпадения. А так как индекс совпадений вводится как вероятность совпадения двух произвольных букв в строке, то для сдвигов, кратных или равных периоду, автокорреляционные коэффициенты, при достаточно большой длине текста, будут близки к индексу совпадений естественного языка.

Пример использования

Пусть шифруется следующий текст без учета знаков препинания и различия строчных и прописных букв (буквы И и Й также не различаются).

Все, чему мне случилось быть здесь свидетелем, не было мне совершенно незнакомым, о подобных случаях я где-то что-то читал и теперь вспомнил, что поведение людей, попадавших в аналогичные обстоятельства, всегда представлялось мне необычайно, раздражающе нелепым. Вместо того чтобы полностью использовать увлекательные перспективы, открывшиеся для них счастливым случаем, они пугались, старались вернуться в обыденное. Какой-то герой даже заклинал читателей держаться подальше от завесы, отделяющей наш мир от неведомого, пугая духовными и физическими увечьями. Я ещё не знал, как развернутся события, но уже был готов с энтузиазмом окунуться в них. Бродя по комнате в поисках ковша или кружки, я продолжал рассуждать. Эти пугливые люди, думал я, похожи на некоторых ученых-экспериментаторов, очень упорных, очень трудолюбивых, но начисто лишенных воображения и поэтому очень осторожных. Получив нетривиальный результат, они шарахаются от него, поспешно объясняют его нечистотой эксперимента и фактически уходят от нового, потому что слишком сжились со старым, уютно уложенным в пределы авторитетной теории. Я уже обдумывал кое-какие эксперименты с книгой-перевертышем (она по-прежнему лежала на подоконнике и была теперь «Последним изгнанником» Олдриджа), с говорящим зеркалом и с цыканьем. У меня было несколько вопросов к коту Василию, да и русалка, живущая на дубе, представляла определённый интерес, хотя временами мне казалось, что она-то мне все-таки приснилась. Я ничего не имею против русалок, но не представляю себе, как они могут лазить по деревьям… хотя, с другой стороны, чешуя?..

— А.Н. и Б.Н. Стругацкие «Понедельник начинается в субботу»

Воспользуемся шифром Виженера с ключевым словом КЛЮЧ. Зашифрованное сообщение:

МЫГОПЦСВЦРПБЬБЖБЧЫЪШДЬЪЮОРПУЪНЖЫПЬГБПЦЛЬЛЕИДХЧГЗЧНГЖБРЛГЧЧГЮ
ЦЛЗДХЕКДШШВДЛЧЩМЪХСОККУЦНПГИЧБРДЫШХЯЫЛИЯЫРНЬЩЖАЗШШКГТХХИЧЩМЩ
ППГГТРИХОРЖЕЧЩЮЫКНЦЯЮНЮГКХМЪТБЛТПШЯЗЫШЭИПХЪЗЫНЮЩЪРБЫКЩОЬОЫРЧ
МХЭБЧЫЪВЦРЛЬЧМЩОКУЛДЩЛЕЫЩЛДЧЗГГГПХГЕДЦАВПЫРДЫШБДАЬМШДЩМБЦШПИ
ЕИЖЗШШИУСШАЧЫЖСЩФРЗЧЫРИУЦЕГЕПЪПЕПФРЯМЕМИУЪЩЩБУГЗИПИЦЦУУЗАЛПИ
ФУАТХЫИКАЛГВЧЧЖЕЬОЮБТЫЪЗЫЛОЧФУПУМРОГЬЬЪЗИНМШДПГГЦШГАКФМЯЫШБЬ
ЩШЖЫКСГЮКФИЯЦЛИОТЬЮИПХГЯОРОЭКЬЪЗИЩМЫКХЪППШРЮКНГЗДШРЫПХЭХВРЖГ
КВКЯЩШРГПНГЫЧЦМЪЧЩСЪККВКЮШАГДЦЖЯЭУЕЯАРПАТЦЖКМРХУИЦЖЦПГГГПТЛЧ
ФФЮАЩЛЕЩПЪЛКЫЫЭЗЧМЩИТКЛДЬСГШДХБДЫШАЗЖЧРКСУЮЮХШКДУЭЛКЫЖПЦМЧЖМ
ЛЪМЫИЩМАЧЦЛЧЫРАЕЧУПАКЯЗДМВЮЯФУЗЖЬСЗЯИЩОДОШИЭКХОЧЪЫСЭОЛРУЖЬЖЕ
ЬОИЯМЕГБЗПЖЫЬЦЮБИЩММЧСЖГКЧГАЧЬМЖДЯСОПЧЩМЖФПЕПЪЖВПЧРЧЫШОДМШХЬ
ЦЖСЕЧЪЛТЮШХЬЦЖРЖЬПМБЗМЖЩДЯЛДЦЛХЯЪЬМБТВГГЦЕУЩЧШЯЖКСГГТКЖЕЧЗРД
ХЭМОПЧЪДЪЬМЖЧСЛТЮЩМБЬБЖЩЦРРЖТНЖЧФЖЛТТЪГЮЬХЪИКЬМГТВЮЖКЯЮХЫЫЭД
ЫЧГЪЧЩМЗШРЦГЧШЯСИЫЛЦЗЬГЪЧЧГОТЫРДЫШЖФУЫНЬЩУКЬЦЬЮЯЭЛЗИТБГЗУУСМ
ЧПЭИЧЬЛДМШБДШШРДХЭХИЧЫИЯБФМВЪСЖБТЫЪЗЧЫРЧЩЕККЗЬЛДЬХМЭПЧЛТХННЖ
ППГБДЛАИЧЪЖИПЬЛДТЬГДЩУЖЦЬСГДЛПСВДНЮБУШГАКФЖЬЖФПЕПЪЖВПЧРТЪФЛЯ
НШЖЕПЪГЩПЪРТБРКДЦЛНДШЪГЭЦРККФРДЧФЛЛЧШШВДУШЛГТФГЯЛЕИЧЫРНЬЩЖНД
ЪХГЫЦУКЯСОЛЧЦЧЖАЧЦМБОЪЖЫРЛПЪЧНМЖИГЖВСРОАКХМВТЫФТУЛЛУПЦСВПЧЭШ
ДХМГПЫЗДФЖЗДМШНЖЧЫМЩУФМИЬНЮЗТХЖХОЛЖЖЬЫЮБУЛДЯМЭЧЧИЧЮЫЬМГЕЩРВЗ
ЫЛАБИХЮДШЪГЫПХГГЦЕЖЯЦЬГЖПЫУДЫКАЖПЦГГКЦЖВЦРЗЧСЛИДЪЖХИЧШЛЧЫШКГ
ПНПЬЫЛЗЯШЪЖЗЦУИЧЪЖЭГТБГЪЧЧГЯХРЬЕЩШРЯМЪСЗКХМАЦШЛЬШЪГЫЪЬЮЩФКЬЗ
ПМГАКФМГТЦМЪЬЬИЧСУРУШШВЬЩРАУИЦУДЫКПЫЩЭБДТЫРДЩШЛТАРЦКИ

Автокорреляционные коэффициенты для сдвигов $t=1,\dotsc ,200$

Вычислим автокорреляционные коэффициенты для сдвигов $t=1,\dotsc ,200$ и построим график $\gamma (t)$. Среднее расстояние между пиковыми значениями функции равно 4, значит предполагаемая длина ключевого слова равна 4, что совпадает с использованной.

Далее необходимо найти частоты встречаемости букв для шифротекстов, полученных из $l=4$ колонок.

• Частоты встречаемости букв шифротекстов из различных колонок
• 
  Шифротекст 1
• 
  Шифротекст 2
• 
  Шифротекст 3
• 
  Шифротекст 4

Предположим, что при шифровании использовался шифр Виженера. Тогда для расшифровки всех четырёх шифротекстов необходимо сравнить распределения частот встречаемости букв в шифротекстах с распределением естественного языка. Наилучшим образом это можно сделать при помощи критерия согласия Пирсона. Найдем значения критерия $\chi ^{2}$ для распределений, получаемых циклическим сдвигом вправо из распределения частот встречаемости букв в русском языке.

Значения критерия $\chi ^{2}$ для различных шифротекстов
Тестируемый сдвиг	Шифротекст 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. Для выбранного алфавита это соответствует ключевому слову шифра Виженера КЛЮЧ. Текст расшифрован.

См. также

• Криптоанализ полиалфавитных шифров
• Шифр Виженера
• Метод Касиски
• Индекс совпадений

Литература

• Э. М. Габидулин. Защита информации. — Москва: МФТИ, 2011.
• Thomas Johansson. Lecture notes in cryptography. — 2005.

Ссылки

• Lecture notes in cryptogtaphy Thomas Johansson