P(s--1), P(s`-1), P(s*-1)

Для решения этой задачи подсчитывают взаимные индексы совпадения MIC(Á(s),Á(s`)), MIC(Á(s),Á(s*)) выборок Á(s), Á(s`) и Á(s), Á(s*) и определяют по ним приближенные значения величин MIc(P(s-1),P(s`-1)) и MIc(P(s-1),P(s*-1)). Откуда узнают и неизвестные s` и s*.

Метод Симпсона. Перейдем теперь к изложению метода дешифрования шифра последовательной замены при известном периоде ключевой последовательности.

Пусть b₁,b₂,…,b_N – известный шифртекст, d – период ключевой последовательности.

Для всех возможных пар (s,s`) из КхК подсчитывается значение вероятности МIc(P(s<sup>-1</sup>), P(s`^-1)). Проводится разбиение множества К на классы kÌК эквивалентности так, что пары из одного класса имеют одинаковое значение вероятности, а из разных классов k, k` – разное значение вероятности.

Выписывают шифртекст в следующем виде:

Á(1) b₁, b_1+d, b_1+2d,…,b_1+jd,…

Á(2) b₂, b_2+d, b_2+2d,…,b_2+jd,…

……………………………..

Á(d) b_d, b_d+d, b_d+2d,…,b_d+jd…

Пусть s₁,s₂,…,s_d – начальный отрезок неизвестной ключевой последовательности. Тогда первая строка букв – последовательность Á(1) результат шифрования букв открытого текста по простой замене s₁, вторая – Á(2) – по s_2, …d-тая – по s_d. Далее предполагают, что каждая последовательность Á(j) является реализацией выборки из неизвестного вероятностного распределения . Подсчитываются значения взаимных индексов совпадения MI_C(Á(1),Á(j)), jÎ{1,…,d}. Опробуют в качестве неизвестной подстановки s₁ все подстановки s из К. Для опробуемого варианта s при каждом фиксированном jÎ{1,…,d} проводят сравнение значения взаимного индекса совпадения MI_C(Á(1),Á(j)) с вероятностями: MIс(P(s^-1),P(s`<sup>-1</sup>)), s`ÎК. Для каждого jÎ{1,…,d} находят наиболее близкое значение MIс(P(s^-1),P(s`^-1)). Этому значению отвечает некоторый класс эквивалентности к(j). Опробуемому варианту s ставят в соответствие множество {s,k(2),…,k(d)} значений вариантов начального отрезка s₁,s₂,…,s_d ключевой последовательности. Первый элемент любого такого варианта есть s, второй – произвольный элемент из класса k(2), и т. д. Промежуточным этапом решения задачи является получение объединения множеств вариантов по всем sÎК. Далее, поставленная задача дешифрования решается опробованием вариантов этого множества.

Отметим, что опробование неизвестной подстановки s₁ диктуется неоднозначностью решения уравнения = P относительно пары подстановок (s,s*). Так, если (s,s*) – решение этого уравнения, то пара (ss^,s*s^) также будет решением рассматриваемого уравнения при любой подстановке s^. Если же ищутся решения (s,s*) с заданной первой компонентой s, то неоднозначность решения значительно уменьшается.

Модернизированный метод Симпсона. Если известно, что первая подстановка s₁ начального отрезка s₁,s₂,…,s_d ключевой последовательности равна тождественной подстановке, то Á(1)=b₁, b_1+d, b_1+2d,…,b_1+jd является выборкой из неизвестного открытого текста и, по предположению, она трактуется как выборка из распределения Po. В этом случае по значениям вероятностей MIc(Po,P(s-1)), sÎК с помощью вычисленных значений взаимных индексов совпадения MIC(Á(1), Á(j)), jÎ{1,…,d } определяются остальные значения ключевой последовательности.

При неизвестной же первой подстановке в качестве выборки из неизвестного открытого текста (выборки из распределения P _o=(P₁,P₂,…,P_|I|)) может быть взят произвольный содержательный текст Á(0), т.е. можно ввести дополнительную вспомогательную последовательность Á(0) и считать, что ее буквы шифровались по тождественной подстановке. Следовательно, в общем случае имеется возможность сведения данной задачи к задаче дешифрования при известной первой подстановке. Практически же предлагается провести вычисления модернизированного взаимного индекса МВЗ(P _o,Á(j)) по формуле

ВЗ(P _o,Á(j))= ,

где N_j – длина последовательности Á(j), F – частота буквы i в Á(j). В качестве искомой подстановки s_j предлагается брать подстановки s, для которых

ВЗ(P _o,Á(j))= »MI_c(P _o,P(s^-1))= .

Глава 8.