Дешифрование шифра Виженера

Основное внимание в данном параграфе уделено вопросам определения периода гаммы наложения в шифре гаммирования по известному шифрованному тексту. Основным инструментом решения этой задачи выступает метод Фридмана, основанный на введенном им понятии «индекса совпадения».

Проблеме определения периода гаммы в шифре гамммирования по шифрованному тексту посвящено много работ в открытой литературе, из которых мы отмечаем работы Фридмана (W.F. Fridman). Целью данного параграфа является математическая проработка открытых научных работ с единых методологических позиций. То есть доказательное изложение известного материала с математической проработкой гипотез и приведенных там утверждений.

Краткий исторический очерк. Под шифром Виженера ниже понимается шифр гаммирования с использованием периодической гаммы малого периода. Обычно ключ такого шифра выбирается с помощью легко запоминаемых приемов. Например, с помощью таблицы Виженера со стандартным расположением алфавита.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

--------------------------------------------------------------------------------

A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F| F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

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

Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Ключом шифра является последовательность букв ₁, ₂,…, d. При шифровании открытого текста а₁,а_2,…,а_d каждая буква а_j открытого текста определяет номер столбца, а соответствующая буква ключа определяет номер строки, на пересечении которых будет находится шифрованная буква b_j. Ключ (лозунг) – это, как правило, легко запоминаемая фраза. Последующий отрезок длины d открытого текста шифруется на том же ключе. Отождествляя буквы этого алфавита с их номерами (от 0 до 25) при расположении букв в стандартном порядке

«A B C D E F G H I J K L M N O P Q R S T U V W X Y Z»,

уравнение шифрования j-той буквы представимо в виде b_j=а_{j + j} mod 26, jÎ{1,2,…d}.

Напомним, что шифром Бофора (Beaufort) нередко называют шифр гаммирования, использующий замену

b_j=а_j - _j mod 26, jÎ{1,2,…d},

то есть шифр «расшифрования» Виженера. Очевидно, шифр Бофора представим в виде шифра Виженера

b_j=а_j - _j = а_j +(26- _j) mod 26.

Отметим, что по К. Шеннону шифром Бофора называется шифр с уравнением шифрования _j – а_j = b_j mod 26 и уравнением расшифрования

_j-b_j=а_j mod 26.

Этот шифр также может быть представлен в виде шифра гаммирования для зашифрования букв 26 – а_j, jÎ{1,2,…}

Иногда используют усложненный шифр Виженера с перемешанным исходным алфавитом первой строки (остальные строки – сдвиги первой строки, как и в исходном шифре Виженера). Перемешивание обычно производят с помощью ключа – лозунга. Например, при ключевой фразе «WORLD TRADE CENTER» образуют неповторяющуюся последовательность ее букв «WORLDTAECN» и дополняют ее оставшимися не использованными буквами по порядку «BFGH … и т. д.». Затем выбирают число n, взаимно простое с 26 (числом букв алфавита), и образуют выборочную последовательность шага n. Например, при n=3 из последовательности «WORLDTAECNBFGH …» получают выборочную последовательность «WLANG …и т. д», которую и используют в качестве нулевой строки (строки с номером A) в таблице Виженера (остальные строки – сдвиги первой).

В 1920 году W. Фридман опубликовал результаты своих научных исследований по дешифрованию шифров типа шифра Виженера. Затем появилось достаточно много работ, уточняющих результаты Фридмана, расширяющие границы их применимости Фридман ввел в рассмотрение так называемый «индекс совпадения», на основе которого он предложил алгоритм нахождения периода гаммы наложения по известному шифрованному тексту, полученному с помощью шифра Виженера. В 1950–х годах появились публикации, в которых излагались другие алгоритмы определения периода гаммы по шифрованному тексту, так называемый метод Казиского, разработанный им в 1863 году. Последний метод был заново открыт и советским криптографом Михаилом Ивановичем Соколовым в районе 50-х годов. Для решения той же задачи позднее появился в печати и так называемый метод Регрессии-Ковариации (Кэрол и Робинс, 1986 г.).

Понятие индекса совпадения. Пусть I – некоторый конечный алфавит.

ОПРЕДЕЛЕНИЕ 1. Индексом совпадения последовательности =i₁,i₂,…,i_N I^N называется величина

IC()= ,

где F_i – частота встречаемости буквы i в последовательности = i₁,i₂,…,i_N (число мест, на которых стоит буква i).

Из данного определения следует, что индекс совпадения последовательности =i₁,i₂,…,i_N равен вероятности P_Á(i_j=i<sub>j`</sub>) совпадения букв данной последовательности на случайно и равновероятно выбранных местах j, j` , j j`.

Действительно, априори, буква i_j=i может принимать любое значение из I, следовательно, число F_i (F_i –1) есть число возможных благоприятных событий (i_j=i<sub>j`</sub>=i), а N(N–1) есть число всех возможных выборов пар упорядоченных мест (j,j`) в последовательности i₁,i₂,…,i_N._.

Далее будем предполагать, что I – алфавит открытого текста некоторого языка. При необходимости, в дальнейшем, мы отождествляем буквы этого алфавита с их номерами (от 0 до |I|–1) при расположении букв в стандартном порядке. Через Р _о=(Р₁,Р₂,…,Р_|I|) обозначим вероятностное распределение на I, где Р_i – вероятность буквы i I в содержательных открытых текстах; через А(N)=а₁,а_2,…,а_N будем обозначать реализацию случайной выборки объема N из генеральной совокупности распределения Р _о (далее будем говорить кратко– выборка из распределения Р_о).

Покажем, что

IC(А(N))=

при N (сходимость по вероятности).

Докажем этот факт, предварительно уточнив обозначения. Именно положим: F_i=F_i(N). Имеем

.

Второй сомножитель слагаемого в сумме может быть преобразован так

,

где e(N)Î{0,1}. Поэтому

при N ,

откуда и вытекает указанное выше утверждение.

Аналогично, для реализации G(N) выборки объема N из равномерного распределения на I

IС(G(N)) при N .

Для фиксированного содержательного текста а₁,а_2,…,а_N мы полагаем, что

при N ,

в связи с чем IC(а₁,а_2,…,а_N) .

При случайном выборе последовательности =i₁,i₂,…,i_N индекс совпадения IC() является случайной величиной, и представляет интерес подсчет его математического ожидания. При различных предположениях о вероятностном распределении на множестве U возможных гамм ниже будет подсчитано среднее значение индекса совпадения шифрованного текста B(N)=B(А(N),G(N))=b₁,b_2,…,b_N, где b_j=а_{j + j} (mod |I|), j .

Среднее значение индекса совпадения для открытых текстов. Обозначим через Е(IC(A)) математическое ожидание случайной величины IC(A(N)), вычисленной для случайной реализации А(N)=а₁,а_2,…,а_N выборки из вероятностного распределения Р _о=(Р₁,Р₂,…,Р_|I|). Через Р _о(i_j=i<sub>j`</sub>) обозначим вероятность совпадения букв в случайной выборке А(N)=а<sub>1</sub>,а<sub>2,…,</sub>а<sub>N</sub> на случайно и равновероятно выбранных местах j, j` , j j`. Здесь мы считаем, что вероятностная мера задана на выборках А(N) и на парах j, j` .

ЛЕММА 1. Справедливы равенства

Е(IC(A))= Р _о(i_j=i_j`)= ,

ДОКАЗАТЕЛЬСТВО. Вероятность совпадения двух букв в случайной реализации выборки А(N)=а₁,а_2,…,а_N из распределения Р _о на фиксированных различных местах равна , и не зависит от выбора этих мест. Поэтому

Р _о(i_j=i_j`)= .

С другой стороны,

Е(IC(A))= = (i_j=i_{j`</sub>)Р(А) = Р <sub>о</sub>(i<sub>j</sub>=i<sub>j`})= .

Обозначим через Е(IC(G)) математическое ожидание случайной величины IC(G(N)), вычисленной для реализации G=G(N)= выборки из равномерного вероятностного распределения на I, а через Р_G(=) – вероятность совпадения букв в случайной выборке G(N)= ₁, ₂,…, _N на случайно и равновероятно выбранных местах j, j` , j j`.

Аналогично доказательству леммы 1 легко доказывается равенство

Е(IC(G))=P_G(=) = .

Рассмотрим подмножество Х_с всех реализаций А(N)=а₁,а_2,…,а_N выборки из вероятностного распределения Р _о=(Р₁,Р₂,…,Р_|I|), состоящее из всех реализаций А(N)=а₁,а_2,…,а_N, для которых частота F_i iÎI приблизительно равна NP_i. Таким образом, Х_с состоит из наиболее вероятных реализаций. Здесь, как и ранее, F_i=F_i(N) – частота встречаемости символа iÎI.

ЛЕММА 2. Для любой последовательности А(N)=а₁,а₂,_,…,а_N из Х_с вероятность P_c(=) совпадения двух случайно и равновероятно выбранных букв последовательности А(N) (отметим, что индекс совпадения IC(А(N)) равен P_c(=)) приблизительно равна

.

ДОКАЗАТЕЛЬСТВО. Имеем

IC(А(N))= P_с(=) =

= = = .

Отметим, что в формулировке леммы 2 множество Х_с определено нестрого, в связи с чем и приближенное равенство некорректно. Устранить определенную некорректность можно, определив множество Х_с как множество, состоящее из всех реализаций А(N)=а₁,а_2,…,а_N, для которых частоты F_i, iÎI удовлетворяют неравенствам NP_i – e £ F_i £ NP_i +e. Утверждение леммы 2 в этом случае будет состоять в указании верхней и нижней оценок IC(А(N)). Так, например, несложно показывается, что

IC(А(N)) £ +2e/N–1 +|I|e² – |I|e.

Пусть U – некоторое подмножество множества I^N .Через Р обозначим равномерное вероятностное распределение на U. Элемент множества U будем обозначать через G(N)= ₁, ₂,…, _N

Для G(N)= ₁, ₂,…, _N из U и А(N) из I^N образуем последовательность

B(N)=B(А(N),G(N))=b₁,b_2,…,b_N,

где b_j=а_{j+ j} (mod|I|), j . Последовательность B(N) будем трактовать как шифрованный текст, полученный зашифрованием текста А(N) на ключе-гамме G(N) в шифре гаммирования

(Х=I^N,К= U,У= I^N, f), f(а₁,а_2,…,а_{N; 1}, ₂,…, _N)= b₁,b_2,…,b_N.

Среднее значение индекса совпадения для шифрованных текстов. Пусть (Х=I^N,К=U,У=I^N,f) – шифр гаммирования. При заданных вероятностных распределениях Р _o, на I и Р на U I^N на Х индуцируется вероятностное распределение и на У индуцируется вероятностное распределение Р _У и, следовательно, имеется и вероятностное распределение случайной величины IC(B), где В – шифрованный текст, полученный в результате шифрования случайного текста А(N) при случайном и равновероятном выборе ключа G(N) из U. Обозначим через Е_U(IC(B)) математическое ожидание случайной величины IC(B) для случайного шифртекста B, а через Р _У(b_j=b<sub>j`</sub>) – вероятность совпадения букв в шифртексте B(N)=f(А(N),G(N))=b<sub>1</sub>,b<sub>2,…,</sub>b<sub>N</sub> на случайно и равновероятно выбранных местах j, j` , j j`.

ЛЕММА 3. Пусть U=I^N. Тогда справедливы равенства

Е_U(IC(B))= Р _У(b_j=b_j`)= .

ДОКАЗАТЕЛЬСТВО. Справедливость утверждения леммы 3 вытекает из индуцированного на множестве шифртекстов равновероятного вероятностного распределения и утверждения леммы 1.

Обозначим через R=(N₁,N₂,…,N_k) – произвольное разбиение множества {1,2,…,N},
а через П=( (=),П()) разбиение множества пар {1,2,…,N}х{1,2,…,N}, индуцированное разбиением R. Именно, {j,j`} П(=), тогда и только тогда, когда j и j` одновременно принадлежат одному классу (блоку) разбиения R; {j,j`} П(), когда j и j` принадлежат разным классам разбиения R. Разбиению П поставим в соответствие подмножество U(П) множества ключей К=I^N. Это подмножество U(П) определим так: последовательность ₁, ₂,…, _N принадлежит U(П) тогда и только тогда, когда <sub>j= j`</sub> для любой пары {j,j`} (=).

ЛЕММА 4. Пусть последовательность ₁, ₂,…, _N случайно и равновероятно выбирается из множества U(П), Тогда: а) P()=1/|I| для любого jÎ{1,…,N} и iÎI; б) P(g_j=g<sub>j`</sub>)=1/|I| для {j,j`}Î П().

ДОКАЗАТЕЛЬСТВО. По определению, множество U(П) состоит из тех и только тех последовательностей g= ₁, ₂,…, _N, для которых значения элементов одинаковы на позициях, принадлежащих одному блоку разбиения R. Таким образом, каждой такой последовательности g соответствует последовательность значений g(N_j) из I, то есть g – функция на множестве блоков {N₁,N₂,…,N_k}. Очевидно, что |U(П)|=|I|^k и существует взаимнооднозначное соответствие между последовательностями из U(П) и множеством всех слов I^k, откуда и вытекают утверждения леммы.

В множестве (=) выделим подмножество П(=) всех пар различных элементов (j,j`), j¹j`.

Величина Р(П(=))= равна вероятности случайного и равновероятного выбора пары индексов {j,j`} из множества П(=), аналогично, Р(П())= равна вероятности случайного и равновероятного выбора пары индексов (j,j`) из множества П().

ТЕОРЕМА 1. Пусть шифртекст B=B(N) получается шифрованием случайного текста А(N) (выборки из распределения Р _о) c помощью равновероятного выбора ключа G(N) из U(П). Тогда справедливы равенства

Е_U(IC(B))= Р _У(b_j=b_j`)= + .

ДОКАЗАТЕЛЬСТВО. Пусть B(N)=B(А(N),G(N))=b₁,b₂,…,b_N. Ранее отмечалось, что индекс совпадения IC(B(N)) последовательности b₁,b₂,…,b_N совпадает с вероятностью Р_В(b_j=b_j`) совпадения шифрованных букв на случайно и равновероятно выбранных двух различных местах. Пользуясь определением математического ожидания случайной величины, получаем

Е(IC(B(N)) = .

Последняя величина совпадает с Р _У(b_j=b<sub>j`</sub>). Определим события С(1), С(2). Событие С(1) состоит в выборе пары индексов (j, j`) из П(=), а С(2) – в выборе (j, j`) из П(). Тогда

= =

=

+ =

=

+ =

= Р(С(1))

+ P(C(2)) .

Первое слагаемое преобразуем следующим образом:

Р(С(1) = =Р(С(1)) =

=Р(С(1)) =

=Р(С(1)) = Р(С(1)) =

=Р(С(1)) .

При получении последнего равенства использована лемма 1.

При случайном и равновероятном выборе G из U и выполнении условия С(2) значения в G случайны и равновероятны (см. лемму 4). С учетом этого факта преобразуем теперь второе слагаемое.

P(C(2)) =

= P(C(2)) =

= P(C(2)) =

= P(C(2)) ,

где Р( = – вероятность события ( при случайном и равновероятном выборе .

Следовательно,

P(C(2)) =

= Р(С(2)) =Р(С(2)) .

Объединяя результаты преобразований двух слагаемых, получаем

Е_U(IC(B))= Р _У(b_j=b_j`)= + .

Укажем и второй способ доказательства теоремы 1. Представим вероятность Р _У(b_j=b_j`) в следующем виде:

Р _У(b_j=b_j`)= =

= + =

= + .

Используя теперь технику доказательства леммы 1, предыдущее выражение преобразуется к виду

+ .

СЛЕДСТВИЕ ТЕОРЕМЫ 1. Если R – разбиение множества {1,2,…,N} на одноэлементные подмножества (k=N, |П(=)| = 0), то есть рассматривается множество U(П)=I ^N, то

Е_U(IC(B))= Р _У(b_j=b_j`)= .

Если R – одноэлементное разбиение (k=1), то

Е_U(IC(B))= Р _У(b_j=b_j`)= .

Утверждения следствия вытекают из теоремы 1; они также могут быть доказаны исходя из утверждений лемм 3, 1.

Среднее значение индекса совпадения шифрованных текстов в шифре Виженера. Напомним, что шифром Виженера называют шифр гаммирования, множеством ключей которого являются коротко-периодические лозунги. Имея дело с гаммами конечной длины, понятие периодичности конечной последовательности и ее периода требует математической формализации.

ОПРЕДЕЛЕНИЕ 2. Назовем конечную последовательность i₁,i₂,…,i_N локально-периодической (или, кратко - периодической), если найдется натуральное число d, 2d N, при котором для любого j, в случае j+d N, выполняется равенство i_j =i_j+d. Число d c указанным свойством назовем локальным периодом, или, короче, периодом данной последовательности. (Период конечной последовательности определен данным определением, вообще говоря, неоднозначно).

Говоря ниже о том, что некоторая последовательность имеет локальный период мы, не оговаривая это, считаем, что рассматриваемая последовательность локально-периодическая.

Обозначим через – множество всех локально-периодических последовательностей периода d, N=кd+r и рассмотрим разбиение R_d=(N₁,N₂,…,N_d) множества номеров {1,2,…,N}, где

N₁={1, 1+d, …,1+kd }

N₂={2, 2+d, …, 2+kd }

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

N_r={r, r+d, …., r+kd}

N_r+1={r+1, r+1+d, …., r+1+(k-1)d}

N_r+2={r+2, r+2+d, …., r+2+(k-1)d}

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

N_d ={d, 2d, …,d+(k-1)d}

Любая последовательность из такова, что ее элементы, стоящие на местах с номерами из одного блока номеров, одинаковы. Разбиению R_d соответствует разбиение П_d =( _d (=),П_d )) множества различных пар номеров. При этом ясно, что =U(П), так как, очевидно, любую последовательность длины N c периодом d можно получить случайно и равновероятно, выбирая d-грамму в алфавите I и повторяя ее необходимое число раз до получения последовательности длины N. Следовательно, | |=|I|^d, и для подмножества П_d (=) пар различных элементов из _d(=) получаем

|П_d (=)|= (k+1)kr + k(k-1)(d-r),

где k и r определены равенством N=kd+r (r – остаток от деления N на d). Используя последнее равенство, получаем

|П_d ()|=N(N-1) – (k+1)kr – k(k-1)(d-r).

Из полученных значений мощностей |П_d (=)| и |П_d ()| и утверждения теоремы 1 непосредственно вытекает

СЛЕДСТВИЕ 2 ТЕОРЕМЫ 1. Пусть шифртекст B=B(N) получается шифрованием случайного текста А(N) (выборки из распределения Р _о) c помощью равновероятного выбора ключа G(N) из множества всех периодических последовательностей периода d, N=kd+r. Тогда справедливы равенства

Е_U(IC(B))= Р _У(b_j=b_j`)=

= +(1– ) .

В частности, при r=0

Е_U(IC(B))= Р _У(b_j=b_j`)=

= +(1- ) = + .

Среднее значение индекса совпадения шифрованных текстов, зашифрованных почти периодическими гаммами.

ОПРЕДЕЛЕНИЕ 3. Назовем конечную последовательность i₁,i₂,…,i_N К–прибли-женной к локально-периодической последовательности периода d, если расстояние Хэмминга (i₁,i₂,…,i_N; ) между данными последовательностями равно К. Последовательность i₁,i₂,…,i_N назовем последовательностью с К-приближенным периодом d, если она является К-приближенной к некоторой локально-периодической последовательности периода d.

ЗАМЕЧАНИЕ 1. Пусть I=Z/|I| – кольцо вычетов по модулю |I|. Из определения следует, что каждую последовательность с К-приближенным периодом d можно представить в виде суммы по модулю |I| некоторого вектора – последовательности i₁,i₂,…,i_N периода d из компонент, принадлежащих Z/|I|, и некоторого вектора «помех» С(N,К)=с₁,с₂,…,с_N с числом К ненулевых компонент. Очевидно, верно и обратное утверждение: сумма такого вида будет последовательностью с К-приближенным периодом d.

Следовательно, процесс шифрования открытого текста А(N)=а₁,а_2,…,а_N гаммой G(N)= с К-приближенным периодом d можно представить в виде последовательного выполнения двух процессов: наложения на открытый текст А(N) вектора помех С(N,К) и затем зашифрования результата гаммой i₁,i₂,…,i_N периода d.

ЛЕММА 5. Пусть а₁,а_2,…,а_N – выборка из распределения Р _о=(Р₁,Р₂,…,Р_|I|), а С(N,К)=с₁,с₂,…,с_N – равновероятно выбранный вектор из множества всех векторов, имеющих ровно К ненулевых компонент. Тогда последовательность а`<sub>1</sub>,а`_2,…,а`<sub>N,</sub> где а`_j =а_j +c_j (mod(|I|) является выборкой из распределения Р` <sub>о</sub>=(Р`₁,Р`<sub>2</sub>,…,Р`_|I|), где

Р`_i = P_i (1- ) + .

ДОКАЗАТЕЛЬСТВО.

Р(а_j +c_j=i) = P(а_j =i/c_j=0)P(c_j=0) + P(а_j +c_j=i/c_j 0)P(c_j 0)=

P_i + P(а_j +c_j=i/c_j 0, а_j i)P(c_j 0) P(а_j i) =

=P_i + (1-P_i )=

=P_i (1- )+ (1-P_i)=

=P_i (1- ) – P_i + =

= P_i (1- – ) + =

= P_i (1- ) + .

Пусть последовательность а`<sub>1</sub>,а`_2,…,а`_N, получена зашифрованием случайной выборки из распределения Р _о=(Р₁,Р₂,…,Р_|I|) наложением случайно и равновероятно выбранной гаммы из множества всех гамм с К-приближенным периодом d.

Замечание 1 и утверждение данной леммы сводит задачу подсчета вероятности совпадения двух букв на случайно и равновероятно выбранных различных местах в случайной последовательности а`<sub>1</sub>,а`_2,…,а`_N к аналогичной решенной задаче для гаммирования случайной последовательностью периода d.

Среднее значение индекса совпадения для шифра Виженера с фиксированным ключом.

ТЕОРЕМА 2. Пусть шифртекст B=B(N) получается шифрованием случайного текста А(N) (выборки из распределения Р _о=(P₁,P₂,…,P_N)) c помощью фиксированного ключа G(N)= . Тогда среднее значение Е(IC(B)) индекса совпадения случайного шифртекста совпадает с вероятностью Р (b_j=b_j`) совпадения букв на случайно выбранных различных местах в случайном шифртексте, и это значение равно

+ ,

где П(=) – множество всех различных позиций j, j`, для которых , а П() – множество всех остальных позиций (операции в индексах по

модулю |I|).

ДОКАЗАТЕЛЬСТВО.

Р (b_j=b_j`)=E(IC(B))= =

= + =

= +. .

Вероятность представляется в виде

= P_iP_{i+ ,}

в частности, = . Поэтому

Р (b_j=b_j`)=E(IC(B)= + .

.

Задача определения периода гаммы в шифре гаммирования по заданному шифртексту

Пусть (Х=I^N,К= U,У= I^N, f), U – шифр гаммирования

f(а₁,а_2,…,а_{N; 1}, ₂,…, _N)= b₁,b_2,…,b_N.

Здесь А(N)= а₁,а_2,…,а_N – открытый текст, G(N)= – гамма из U, В= b₁,b_2,…,b_N – шифрованный текст.

Задача состоит в определении периода гаммы по известному шифртексту (либо установления факта ее непериодичности).

Статистические методы определения периода гаммы в шифре гаммирования по заданному шифртексту. Определение статистическими методами периода гаммы в шифре гаммирования по заданному шифртексту основано на переборе возможных значений периода и решения для каждого значения периода задачи «о перекрытии» – установления факта того, что два заданных шифртекста получены зашифрованием двух открытых текстов одной гаммой.

Пусть b₁,b₂,…,b_N – известный шифртекст, полученый зашифрованием неизвестного открытого текста a₁,a₂,…,a_N на ключе – гамме g₁,g₂,…,g_N. Для проверяемого периода d образуется вспомогательная последовательность

b₁-b_1+d, b₂-b_2+d, …,b_j-b_j+d,…,b_(k-1)d+r-b_kd+r, N=kd+r.

Напомним, что вычитание и сложение проводится по модулю |I| номеров букв, упорядоченных в естественном расположении. Так как b_j=a_j+g_j, то, в случае истинного периода d гаммы, получаем

b_j-b_j+d=a_j-a_j+d

для любого jÎ{1,…,(k-1)d+r}, то есть вспомогательная последовательность является, как говорят, «разностью двух открытых текстов». При случайном выборе этих «открытых текстов» вспомогательная последовательность тоже является случайной, вероятностное распределение букв (номеров), которой равно Р_-=(р₁,р₂,…,р_|I|) (ГИПОТЕЗА H(0)), где р_j= , сумма берется по всем c,c`: c-c`=j (mod |I|).

Если d не является истинным периодом гаммы, то

b_j-b_j+d=a_j+g_j-a_j+d-g_j+d.

Естественно предположить, что знаки g_j,g_j+d выбирались при шифровании независимо. Вспомогательная последовательность в этом случае не является «разностью двух открытых текстов». При случайном выборе открытых текстов a₁,a₂,…, a_(k-1)d+r; a_1+d,a_2+d,…,a_kd+r нередко предполагают, что вспомогательная последовательность является случайной независимой выборкой из равновероятного распределения на I (ГИПОТЕЗА H(1)).

Относительно вспомогательной последовательности решают статистическую задачу – принятия гипотезы H(0) или H(1). Принятому решению в статистической задаче соответствует решение криптографическое: истинным периодом является d или d – не истинный период. Основными характеристиками изложенного метода являются: N и ошибки критерия.

Метод Фридриха Казиского. Метод Фридриха Казиского, представленный в 1863 году, анализирует повторения в шифртексте. Этот же метод независимо от Казиского был разработан советским криптографом Соколовым. Метод основан на том, что если гамма локально периодическая, то две одинаковые m-граммы открытого текста, отстоящие друг от друга на расстояние, кратное периоду гаммы, будут одинаково зашифрованы в некоторые одинаковые m-граммы, находящиеся на том же расстоянии друг от друга.
Появление же одинаковых m-грамм в шифрованном тексте по другим причинам маловероятно (при некоторых разумных ограничениях на величину m и на длину шифртекста N). Следовательно, большинство расстояний между одинаковыми m-граммами шифртекста делится на минимальный период. Поэтому на практике в качестве предполагаемого периода гаммы рассматривают наибольший общий делитель длин большинства расстояний между повторениями m-грамм. Эксперименты показали хорошую надежность этого метода, если в шифртексте имеются повторения триграмм и m-грамм при m, большим трех.

Первый метод W. Фридмана. Первый метод W. Фридмана состоит в том, что для данного шифртекста B вычисляют индекс совпадения IC(B) и сравнивают его с величинами

+ , d=1, 2, 3, …

При достаточной близости IC(B) к одной из этих величин при некотором d, предполагают, что период равен этому d. Согласно открытым публикациям см., например, [John C. King. 1994. An Algorithm for the Complete Automated Criptanalysis of Periodic Polyalphabetic Substitution Ciphers. Cryptologia. 18 (4), 332–355] данный метод удовлетворительно работает при использовании для зашифрования локально-периодических последовательностей периода не более 5. С точки зрения обоснованности применения данного метода лучше сравнивать IC(B) c более точным выражением

Е_U(IC(B))= Р _У(b_j=b_j`)=

= +(1– ) ,

полученным ранее для N=kd+r и представленным в начале формулировки следствии 2 теоремы 1.

Слабая эффективность этого метода объясняется, тем обстоятельством, что значение

+

математического ожидания индекса совпадения шифрованного текста для класса U периодических гамм фиксированного периода d совпадает со значением целого ряда различных классов гамм. Это следует из теоремы 1, где доказано, что это среднее значение

Е_U(IC(B))= Р _У(b_j=b_j`)= + .

определено разбиением R=(N₁,N₂,…,N_c) множества . В частности, из этого факта следует, что значение Е_U(IC(B))= Р _У(b_j=b_j) для класса гамм периода d остается инвариантным относительно одновременной перестановки знаков во всех периодических гаммах – ключах.

Второй метод W. Фридмана. Второй метод W. Фридмана также основан на вычислении индекса совпадения. Он состоит в опробовании возможных периодов по следующей схеме. Для предполагаемого периода d выписываются d подпоследовательностей

b₁,b_1+d,b_1+2d,…

b₂,b_2+d,b_2+2d,…

……………….

b_d,b_d+d,b_d+2d,…

Для каждой подпоследовательности подсчитывается ее индекс совпадения. Если все индексы совпадения в среднем близки к значению

,

то есть к среднему значению индекса совпадения случайных шифртекстов, полученных с помощью гамм периода 1 (см. следствие 2 теоремы1), то принимают величину d за истинный период, в противном случае опробуют следующую величину периода. Приведенный способ нахождения периода гаммы по шифрованному тексту удовлетворительно работает для периодов, не превышающих 30.

Метод БШ. Предлагаемый метод определения периода гаммы в шифре гаммирования по известному шифртексту В= b₁,b_2,…,b_N состоит в следующем.

Выписываются все пары номеров j, j`, для которых b<sub>j</sub> = b<sub>j`.</sub> Пусть П(В,=) – множество таких пар. Очевидно, |П(В,=)|= , где F_i – частота встречаемости буквы i в шифртексте В.

Каждой паре (j, j`) из П(В,=) ставится в соответствие расстояние r(j,j`), равное абсолютной величине разности между j и j`. Ищется максимальное по мощности подмножество П(В,d,=) пар в П(В,=) такое, что их расстояния r(j,j`) имеют некоторый общий наибольший делитель d, отличный от 1. Подсчитывается величина

и сравнивается с величиной

Е_U(ИБШ(B,d))= ,

где k, r определены равенством N=kd+r. Если эти величины близки, принимается гипотеза о том, что шифрование проводилось гаммой периода d. В противном случае, эта гипотеза отвергается.

Обоснование метода БШ. Для шифрованного текста В= b₁,b_2,…,b_N величина

равна вероятности Р_В(b_j=b<sub>j`</sub>, d) того, что при случайном и равновероятном выборе различных позиций j и j` с расстоянием, кратным d элементы b_j и b_{j`</sub> совпадут. Действительно, по определению множества П(В,d,=), ему принадлежат те и только те пары (j, j`), при которых d|r(j,j`) и b<sub>j</sub> = b<sub>j`}, а N(N-1) – число всех пар различных позиций в последовательности В= b₁,b_2,…,b_N.

Обозначим через множество всех локально-периодических последовательностей периода d.

ТЕОРЕМА 3. Пусть шифртекст B=B(N)=b₁,b_2,…,b_N получается шифрованием случайного текста А(N) (выборки из распределения Р _о) c помощью равновероятного выбора ключа G(N) из . Тогда вероятность Р _У(b_j=b_j,d) того, что при случайном и равновероятном выборе различных позиций j и j` с расстоянием, кратным d, элементы b<sub>j</sub> и b<sub>j`</sub> случайного шифртекста В совпадут (имеется в виду вероятность совместного события: равенство букв на местах j, j` и кратность расстояния между ними величине d), равна величине

.

При указанной вероятностной модели получения шифртекста данная вероятность совпадает с математическим ожиданием E(ИБШ(В,d)) случайной величины ИБШ(В,d).

ДОКАЗАТЕЛЬСТВО. Множеству =U соответствует разбиение R(d)=(N₁, N₂,…,N_d) множества {1,2,…,N}, где N_j={j,j+d,j+2d,…}, jÎ{1,2,…,d}. Пусть П(d)=( (d,=),П(d,()) – разбиение множества пар {1,2,…,N}х{1,2,…,N}, индуцированное разбиением R(d). Введем обозначение: П(d,=)= |{(j,j`}Î (d,=), j¹j`}|.

Положим, Р(П(d,=))= – вероятность случайного и равновероятного выбора пары индексов {j,j`}из множества П(d,=).

Ранее отмечалось, что величина ИБШ(B(N)) последовательности b₁,b₂,…,b_N совпадает с вероятностью Р_В(b_j=b_j`,d) совпадения шифрованных букв на случайно и равновероятно выбранных двух различных местах, расстояние между которыми кратно d. Поэтому

Е(ИБШ(B(N)) = Р _У(b_j=b_j,d)= =

= =

= =

= Р(d|r(j,j`)) =

= Р(d|r(j,j`)) =

= Р(d|r(j,j`)) =

= P(d|r(j,j`)) =

= P(d|r(j,j`)) =

= P(d|r(j,j`)) = = .

Теорема доказана.

Обозначим через R`=(N`₁,N`<sub>2</sub>,…,N`_k) – произвольное разбиение множества {1,2,…,N}, а через П(R`)=( (R`,=),П(R`, )), разбиение множества пар {1,2,…,N}х{1,2,…,N}, индуцированное разбиением R` (данное понятие определено выше). Разбиению П(R`) поставим в соответствие подмножество U(П(R`)) множества ключей К=I^N. Последовательность ₁, ₂,…, _N из I^N принадлежит U(П(R`)) тогда и только тогда, когда <sub>j= j`</sub> для любой пары {j,j`} (R`,=). Рассмотрим пересечение R` R(d) разбиения R`=(N`<sub>1</sub>,N`₂,…,N`<sub>k</sub>) и введенного при доказательстве теоремы 3 разбиения R(d)=(N<sub>1</sub>,N<sub>2</sub>,…,N<sub>d</sub>) множества {1,2,…,N}, где N<sub>j</sub>={j,j+d,j+2d,…}, jÎ{1,2,…,d}. Разбиение R` R(d)=(n₁,n₂,…,n_t) состоит из непустых блоков вида N`<sub>j`</sub> N_j, где j`Î{1,2,…,k}, jÎ{1,2,…,d}. Этому разбиению соответствует разбиение П(R` R(d))=(П((R` R(d),=)),П((R` R(d), )) множества пар {1,2,…,N}х{1,2,…,N}\{(j,j):jÎ }. Напомним, что разбиению R(d) соответствует П(d)=(П(d,=),П(d,()) – разбиение множества пар {1,2,…,N}х{1,2,…,N}\{(j,j):jÎ }, индуцированное разбиением R(d).

Положим Р(П(d,=))= = , – вероятность случайного и равновероятного выбора пары индексов {j,j`}из множества П(d,=), а

---

---

Дата публикования: 2015-02-22; Прочитано: 2151 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!

---

---

studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.009 с)...