Криптоанализ классических шифров (стр. 11 из 27)
, (4)Взяв за основу значения вероятностей рiдля открытых текстов на английском языке, получаем приближение
. Тем самым для английских текстов х можно пользоваться следующим приближением для индекса совпадения:Iс(x) ≈ 0,066.
Аналогичные приближения можно получить и для других языков. Так, для русского языка получаем приближение:
Iс(x) ≈ 0,053.
Приведем значения индексов совпадения для ряда европейских языков:
Таблица 7. Индексы совпадения европейских языков
| Язык | Русский | Алгл. | Франц. | Нем. | Итал. | Испан. |
 | 0,0529 | 0,0662 | 0,0778 | 0,0762 | 0,0738 | 0,0775 |
Рассуждения, использованные при выводе формулы (4), остаются, очевидно, справедливыми и в случае, когда х результат зашифрования некоторого открытого текста простой заменой. В этом случае вероятности рi переставляются местами, но сумма
остается неизменной.Предположим, что х — реализация независимых испытаний случайной величины, имеющей равномерное распределение на Zn. Тогда индекс совпадения вычисляется по формуле
Вернемся к вопросу об определении числа µ.
Пусть y = y1 y2 …yn — данный шифр-текст. Выпишем его с периодом µ:
и обозначим столбцы получившейся таблицы через Y↓1,..., Y↓µ . Если µ это истинная длина ключевого слова, то каждый столбец Y↓i, i 
1, µ, представляет собой участок открытого текста, зашифрованный простой заменой, определяемой подстановкой
(5)для некоторого s 0,n-l (числа берутся по модулю n).
В силу сказанного выше, (для английского языка) Iс(Y↓i) ≈ 0,066 при любом i. С другой стороны, если µ отлично от длины ключевого слова, то столбцы Y↓i будут более "случайными", поскольку они являются результатом зашифрования фрагментов открытого текста некоторым многоалфавитным шифром. Тогда Iс(Y↓i) будет ближе (для английского языка) к числу1/28 ≈ 0,038
Заметная разница значений Iс(x) для осмысленных открытых текстов и случайных последовательностей букв (для английского языка — 0,066 и 0,038, для русского языка — 0,053 и 0,030) позволяет в большинстве случаев установить точное значение µ.
Предположим, что на первом этапе мы нашли длину ключевого слова µ. Рассмотрим теперь вопрос о нахождении самого ключевого слова. Для его нахождения можно использовать так называемый взаимный индекс совпадения.
Пусть х = (х],...,хп),у = (у1,...,ут)— две строки букв алфавита А. Взаимным индексом совпадения х и у, обозначаемым МIс(х, у), называется вероятность того, что случайно выбранная буква из х совпадает со случайно выбранной буквой из у.
Пусть f0 f1 …fn и f10f11 …f1n-1 — числа вхождений букв алфавита в х и у
соответственно.
Теорема. Взаимный индекс совпадения в х и у вычисляется по формуле (эта теорема доказывается точно так же, как и предыдущая теорема.)
, (6)
Пусть k = (k1,..., kµ,) — истинное ключевое слово. Попытаемся оценить индексы MIc(Y↓i, Y↓j)
Для этого напомним, что Y↓3 является результатом зашифрования фрагмента открытого текста простой заменой, определяемой подстановкой (5) при некотором s. Вероятность того, что Y↓i и Y↓j произвольная пара букв равна 0, имеет вид pn-si*pn-sj (где ра— вероятность появления буквы а в открытом тексте); вероятность того, что обе буквы есть 1, равна pn-si+1*pn-sj+1 и так далее. На основании этого получаем:
Заметим, что сумма в правой части последнего равенства зависит только от разности (si – sj)mod n , которую назовем относительным сдвигом Y↓i и Y↓j. Заметим также, что
, (7)поэтому Y↓i и Y↓j с относительными сдвигами s и п-s имеют одинаковые взаимные индексы совпадения. Приведем таблицу значений сумм (7) для английского языка:
Таблица 8. Взаимный индекс совпадения при сдвиге s
| Сдвиг s | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
 | 0,066 | 0,039 | 0,032 | 0,034 | 0,044 | 0,033 | 0,036 |
| Сдвиг s | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| | 0,039 | 0,034 | 0,034 | 0,038 | 0,045 | 0,039 | 0,043 |
Обратим внимание на то, что ненулевые "сдвиги" дают взаимные индексы совпадения, изменяющиеся в пределах от 0,032 до 0,045, в то время как при нулевом сдвиге индекс MIc(x,y) близок к 0,066. Это наблюдение позволяет определить величины относительных сдвигов si – sj столбцов Y↓i и Y↓j. Для этого заметим, что при некотором значении s(i,j) 0, n-1столбец Ys(i,j)↓j, полученный из Y↓j прибавлением к каждому его элементу числа S(i,j) (по модулю n), имеет нулевой относительный сдвиг с Y↓j.
Пусть Y0↓j , Y1↓j,…, Yn-1↓j – результаты зашифрования Y↓j каждой из простых замен (5). Несложно вычислить взаимные индексы
(всего, таким образом, имеется С2µn значений). Для этого воспользуемся формулой, полученной из (6):
Если s равно si – sj - (относительному сдвигу Y↓i и Y↓j), то взаимный индекс впадения должен быть (для английского языка) близок к 0,066, так как относительный сдвиг Y↓i и Y↓j равен нулю. Если же s не равно si – sj то взаимный индекс совпадения должен колебаться в пределах 0,032 - 0,045.
Используя изложенный метод, мы сможем связать системой уравнений относительные сдвиги различных пар столбцов Y↓i и Y↓j. В результате останется 26 (для английского языка) вариантов для ключевого слова, из которых можно выбрать наиболее предпочтительный вариант (если ключевое слово является осмысленным).
Следует отметить, что предложенный метод будет эффективным для не слишком больших значений µ. Это объясняется тем, что для хороших сближений индексов совпадения требуются тексты достаточно большой длины.
Пример криптоанализа текста:
Задан некоторый текст зашифрованный шифром Виженера, требуется определить ключевое слово и прочитать открытый текст .
Шифрованный текст:
влцдутжбюцхъяррмшбрхцэооэцгбрьцмйфктъъюьмшэсяцпунуящэйтаьэдкцибрьцгбрпачкъуцпъбьсэгкцъгуущарцёэвърюуоюэкааэбрняфукабъарпяъафкъиьжяффнйояфывбнэнфуюгбрьсшьжэтбэёчюъюръегофкбьчябашвёэуъъюаднчжчужцёэвлрнчулбюпцуруньъшсэюъзкцхъяррнрювяспэмасчкпэужьжыатуфуярюравртубурьпэщлафоуфбюацмнубсюкйтаьэдйюнооэгюожбгкбрънцэпотчмёодзцвбцшщвщепчдчдръюьскасэгъппэгюкдойрсрэвоопчщшоказръббнэугнялёкьсрбёуыэбдэулбюасшоуэтъшкрсдугэфлбубуъчнчтртпэгюкиугюэмэгюккъъпэгяапуфуэзьрадзьжчюрмфцхраююанчёчюъыхьъцомэфъцпоирькнщпэтэузуябащущбаыэйчдфрпэцъьрьцъцпоилуфэдцойэдятррачкубуфнйтаьэдкцкрннцюабугюуубурьпйюэъжтгюркующоъуфъэгясуоичщщчдцсфырэдщэъуяфшёчцюйрщвяхвмкршрпгюопэуцчйтаьэдкцибрьцыяжтюрбуэтэбдуящэубъибрювъежагибрбагбрымпуноцшяжцечкфодщоъчжшйуъцхчщвуэбдлдъэгясуахзцэбдэулькнъщбжяцэьрёдъьвювлрнуяфуоухфекьгцчччгэъжтанопчынажпачкъуъмэнкйрэфщэъьбудэндадъярьеюэлэтчоубъцэфэвлнёэгфдсэвэёкбсчоукгаутэыпуббцчкпэгючсаъбэнэфъркацхёваетуфяепьрювържадфёжбьфутощоявьъгупчршуитеачйчирамчюфчоуяюонкяжыкгсцбрясшчйотъъжрсщчл
Для определения числа букв в данном ключевом слове применяется так называемый тест Казиски. Тест основан на простом наблюдении о том, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном µ (количество букв в слове), будут одинаково зашифрованы. В силу этого в шифр-тексте ищутся повторения длины, не меньшей трех, и расстояния между ними. Необходимо обратить внимание на то, что случайно такие одинаковые отрезки могут появиться в тексте с достаточно малой вероятностью