Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

151

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

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

Введение. Проблеме определения периода гаммы в шифре гамммиро-

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

Краткий исторический очерк. Под шифром Виженера ниже понима­

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

АВ С П Е Р О Н П К Ь М М О Р 0 К З Т Ц У ^ Х У 2

АА В С О Е Р О Н П К Ь М М О Р ( ) К 5 Т и У \ У Х У 2 В В С П Е Р О Н П К Е М Ы О Р ( З К . 5 Т Ц У \ У Х У г А

СС О Е Р О Н П К Ь М Н О Р ( З К . 5 Т 1 1 У \ У Х У 2 А В В П Е Р О Н П К Ь М М О Р ( З К . 5 Т Ц У :\ У Х У 2 А В С Е Е Р О Н П К Е М М О Р ( З К . 5 Т Ц У \ У Х У 2 А В С О

Р|	Р 0 Н П К Ь М М О Р ( З а З Т Ц У \ У Х У 2 А В С П Е
2	2 А В С О Е Р О Н П К Ь М Ы О Р д К З Т Ц У ^ Х У
Ключом шифра является последовательность букв у ь у г,- ••, У ^ • При
шифровании открытого текста аи& 2 каждая буква щоткрытого текста оп­

ределяет номер столбца, а соответствующая буква ключа у } определяет но­

мер строки, на пересечении которых будет находится шифрованная буква Ключ (лозунг) - это, как правило, легко запоминаемая фраза. Последующий

152

отрезок длины <1 открытого текста шифруется на том же ключе. Отождествляя буквы этого алфавита с их номерами (от 0 до 25) при расположении букв в стандартном порядке

«А В С 0 Е Р С Н П К Е М 1 4 0 Р д К З Т И У \ У Х У 2 » , уравнение шифрования )-той буквы представимо в виде Ъ}=щ + У] той 26,

)е{1,2,...й }.

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

ЪгагУ } то<126, ) е { 1 ,2,...й},

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

Ъу=&]- у ^= а^ +(26-у ]) той 26.

Отметим, что по К. Шеннону (/Шен/ стр. 345-346) шифром Бофора называется шифр с уравнением шифрования у ^- а^ = ^ той 26 и уравнением

расшифрования

?'^-Ъ^=а^ той 26.

Этот шифр также может быть представлен в виде шифра гаммирования для

зашифрования букв 26 - а;, ) е {1,2,...}

Иногда используют усложненный шифр Виженера с перемешанным исходным алфавитом первой строки (остальные строки - сдвиги первой стро­ ки, как и в исходном шифре Виженера). Перемешивание обычно производят с помощью ключа - лозунга. Например, при ключевой фразе «МЮК1Л5 ТКАОЕ СЕИТЕК.» образуют неповторяющуюся последовательность ее букв «\УСЖЬОТАЕСМ» и дополняют ее оставшимися не использованными буква­ ми по порядку «ВРОН ... ит. д.». Затем выбирают число п, взаимно простое с 26 (числом букв алфавита), и образуют выборочную последовательность ша­ га п. Например, при п=3, из последовательности «\УОКЬОТАЕСЫВРОН ...» получают выборочную последовательность «^ЕАМО ...и т. д», которую и используют в качестве нулевой строки (строки с номером А) в таблице Виженера (остальные строки - сдвиги первой).

В 1920 году У. Фридман опубликовал результаты своих научных ис­ следований по дешифрованию шифров типа шифра Виженера. Затем появи­ лось достаточно много работ, уточняющих результаты Фридмана, расширяю­ щие границы их применимости (см. литературу к данной главе). Фридман ввел в рассмотрение так называемый «индекс совпадения», на основе которо­ го он предложил алгоритм нахождения периода гаммы наложения по извест­ ному шифрованному тексту, полученному с помощью шифра Виженера. В

153

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

Понятие индекса совпадения.

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

Определение 1. Индексом совпадения последовательности 3 =11,12,... Ды е Iм называется величина

где Р| - частота встречаемости буквы 1 в последовательности 3 = цЛ2,---Лы (число мест, на которых стоит буква 1).

Из данного определения следует, что индекс совпадения последова­ тельности 3 =11,12,.• •Лк равен вероятности Р 3 ((р!,) совпадения букв данной

последовательности на случайно и равновероятно выбранных местах ^

Действительно, априори, буква ^=ч может принимать любое значение из I, следовательно, число Р;(Р}—1) есть число возможных благоприятных событий (^=^ ==1), а N (N -1) есть число всех возможных выборов пар упорядо­ ченных мест (]Л') в последовательности 11,12,...Лы-.

Далее будем предполагать, что I - алфавит открытого текста некоторо­ го языка. При необходимости, в дальнейшем, мы отождествляем буквы этого алфавита с их номерами (от 0 до |1|- 1) при расположении букв в стандартном порядке. Через Р0=(РьР2,...,Р|1|) обозначим вероятностное распределение на I, где Р| - вероятность буквы 1е I в содержательных открытых текстах; через А(Ы)=а1,а2„..,ам будем обозначать реализацию случайной выборки объема N из

генеральной совокупности распределения Р0 (далее будем говорить кратко -

выборка из распределения)

Покажем, что

при N —>00 (сходимость по вероятности, см. параграф 2.1)

154

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

Р: (К ) -	1	—> Р: .
—5	> П.В.
N		1

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

Г,(1V)	Р,{1У-1) + е(Ы)
N - 1	АГ-Ь	’ •
где 8(ТМ)€ {0,1}. Поэтому
РА(Ы)		при И —>00
------------ »П.В.—> Р:
N - 1

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

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

1С(0(Л)) —> п.в. —>

при N —> оо.

Для фиксированного содержательного текста а!,а2>...Дм мы полагаем,

что
	Р1(Ы)		при N —>00
	----------- > П.В.—» Р:
	N		.
в связи с чем 1С(а|,а2	111	'
	аы) —> п.в. —> У , Р; .
	1=1

При случайном выборе последовательности 3 =Ч1,12,...,1м индекс

совпадения 1С( 3 ) является случайной величиной, и представляет интерес подсчет его математического ожидания. При различных предположениях о вероятностном распределении на множестве II возможных гамм ниже бу­ дет подсчитано среднее значение индекса совпадения шифрованного тек­

ста В(П)=В(А(П),0(14))=ЬьЪ2,...Ък, где ЪГ а, + ^ (той Ш е Ц У .

155

Среднее значение индекса совпадения для открытых текстов.

Обозначим через Е(1С(А)) математическое ожидание случайной вели­ чины 1С(А(М)), вычисленной для случайной реализации А(Ы)=аьа2 ан вы­ борки из вероятностного распределения Р0=(РьР2,---.Р|1|)- Через Р0(^=^) обо­

значим вероятность совпадения букв в случайной выборке А(Н)=а|,а2>... ан на

случайно и равновероятно выбранных м е с т а х € 1, N , ^ ^ . Здесь мы счита­ ем, что вероятностная мера задана на выборках А(К) и на п а р а х <=\,М.

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

Е(1С(А))=Р„0Г 1г) = 2 > / ,

/

ДОКАЗАТЕЛЬСТВО. Вероятность совпадения двух букв в случайной реализации выборки А(Ы)=а|,а2 ак из распределения Р0на фиксированных

различных местах равна ^ Р (2 , и не зависит от выбора этих мест. Поэтому

I
Ро(г*г)=	/	•
С другой стороны,
Е(1С(А))= ^1С (А )Р (А )	= ]Г	Р А(1]=^ )Р(А) =
Ае1М	А
Ро(Ъ=»Л )= ^ Р, •
/

Обозначим через Е(1С(0)) математическое ожидание случайной величины

1С(0(Ы)), вычисленной для реализации 0=С(М)=?'1, у2 ы			выборки из
равномерного вероятностного распределения на I, а через Ра(=) - вероятность
совпадения букв в случайной выборке 0 (И)= у и		/ ы	на случайно и
равновероятнстно выбранных местах^^ е 1	, N , ]	я* у.
Аналогично доказательству леммы 1	легко доказывается равенство

Е(1С(0 ))=Рс(=)=уу!

156

Рассмотрим подмножество Хсвсех реализаций А(М)=аьа2>... аы выборки из вероятностного распределения Р0=(РьР2,...,Р|1|), состоящее из всех реализа­ ций А(М)=аьа2,... аы, для которых частота Р( 1еI приблизительно равна ЫР,.

Таким образом, Хс состоит из наиболее вероятных реализаций. Здесь, как и ранее, Р;=Е[(М) - частота встречаемости символа 1е 1.

ЛЕММА 2. Для любой последовательности А(М)=а1,а2,,...,аы из Хс ве­

роятность Рс(=) совпадения двух случайно и равновероятно выбранных букв последовательности А(И) (отметим, что индекс совпадения 1С(А(Ы)) равен Рс(=)) приблизительно равна

	N			2	1
	Н	•У		р 2	К - Г
		- 1	Й	'
ДОКАЗАТЕЛЬСТВО. Имеем
1С(А(1Ч))=Рс(=)----- -------У Р;(Р: -				1) *	------	У Р Щ Л М - 1 ) =
	N ( N - 1) ^	1	1		N ( N - 1 ) ^ '		'
=	В Д ^ - 1 ) = т т т Ц т Е ( ^ - ^ ) = т г т Е р? " Т т Ц -
( ^ - 1) ы	( N - 1 ) %					N - 1 ^	N - 1

Отметим, что в формулировке леммы 2 множество Хс определено не­ строго, в связи с чем и приближенное равенство некорректно. Устранить оп­ ределенную некорректность можно, определив множество Хс как множество,

состоящее из всех реализаций А(М)=аьа2	ам, для которых частоты Р|, 1е	1
удовлетворяют неравенствам ИР; - е < Р| <	+8. Утверждение леммы 2	в

этом случае будет состоять в указании верхней и нижней оценок 1С(А(М)). Так, например, несложно показывается, что

1С(А(Ь0) ^ —— У	Д 2	— +2е/Ы-1 +|1|е2- |1|е. .
N - 1 ^	‘	N - 1

Пусть II - некоторое подмножество множества Iм .Через Р у обозна­

чим равномерное вероятностное распределение на И. Элемент множества I) будем обозначать через 0 (1Я)=у \, у 2,..., у N

157

Для 0 (^ )= у и у г,---,У ы из II и А(Ы) из Iмобразуем последователь­

ность

В(И)=В(А^),С(Н))=ЬьЬ2,...Ьы,

где ^=аз+у ^(шоё|1|), ) € 1, IV. Последовательность В(Ы) будем трактовать

какшифрованный текст, полученный зашифрованием текста А(Ы) на клю­ че-гамме С(К) в шифре гаммирования

(Х=1М,К= II,У= Iм, 0, Да,,а2>...,аЫ; у ,, у 2„ . у ы)= ЬьЬ2,...,Ьы.

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

Пусть (Х=1М,К=11,У=1М,{) - шифр гаммирования. При заданных веро­ ятностных распределениях Р0, на I и 1? у на 11с Iм на X индуцируется вероят­

ностное распределение и на У индуцируется вероятностное распределение Ру и, следовательно, имеется и вероятностное распределение случайной величи­ ны 1С(В), где В - шифрованный текст, полученый в результате шифрования случайного текста А(14) при случайном и равновероятном выборе ключа 0(14) из IX Обозначим через Еи(1С(В)) математическое ожидание случайной величины 1С(В)- для случайного шифртекста В, а через Ру(Ъ^=Ъу) - вероят­ ность совпадения букв в шифртексте В(Ы)=ДА(Н),0(>1))=Ъ|,Ъ2>... Ьм на случай­

но и равновероятнстно выбранных местах^ ]' е \,М , ] Ф

ЛЕММА 3. Пусть ХМ141. Тогда справедливы равенства

Еи(1С(В))=Ру(ЬГ Ьг) = ^ .

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

Обозначим через К=(ХХ,М2,...,Мк) - произвольное разбиение множест­

ва {1,2; ,N1, а через П=( П (=),П( Ф)) разбиение множества пар

{1,2,... ,1Я}х {1,2,... ,14}, индуцированное разбиением К. Именно, 0 о'} € П(=), тогда и только тогда, когда ] иодновременно принадлежат одному классу (блоку) разбиения К; (у'} е П(э*), когда) и)' принадлежат разным классам разбиения К.. Разбиению П поставим в соответствие подмножество 11(П) мно­ жества ключей К=1ы. Это подмножество II(П) определим так: последова­ тельность у 1,у 2 ,■ ■■,у ыпринадлежит 11(П) тогда и только тогда, когда У\=У\-

для любой пары О,)'} е П (=).

158

ЛЕММА 4. Пусть последовательность у иУ г,-• •, Уыслучайно и равно­

вероятно выбирается из множества 11(П), Тогда: а)	= / )=1/|1| длялюбо-
п^€{1,...,М } и 1е1; б) Р(^=уг)=1/|1| д л я (У '}е Щ *).

ДОКАЗАТЕЛЬСТВО. По определению, множество П(П) состоит из тех и только тех последовательностей у= у иу г , - У ы> Для которых значения элементов одинаковы на позициях, принадлежащих одному блоку разбиения К.. Таким образом, каждой такой последовательности у соответствует после­ довательность значений у(Ь^) из I , то есть у - функция на множестве блоков {МьИг,...,^}. Очевидно, что |ЩП)|=|1|к и существует взаимно-однозначное соответствие между последовательностями из 1ДП) и множеством всех слов 1к, откуда и вытекают утверждения леммы.

В множестве П (=) выделим подмножество П(=) всех пар различ­ ных элементов ( у '),

Величина Р(П(=))=		^ равна вероятности случайного и равно­
вероятного выбора пары индексов (У'} из множества П(=), аналогично,
Р(П(^ ))=	равна вероятности случайного и равновероятного выбора

пары индексов (У') из множества П (^ ).

Теорема 1. Пусть шифртекст В=В(Т4) получается шифрованием слу­ чайного текста А(Ы) (выборки из распределения Р0) с помощью равноверо­

ятного выбора ключа О(Ы) из 1ДП). Тогда справедливы равенства

Е„(1С(В))=РУ(ЬГ Ь	,) = - Ъ М -	У Р ,!	+ |<Я (* )! — .
}	N ( N - 1)	^ '	N ( N - 1 ) 1 1 1

ДОКАЗАТЕЛЬСТВО. Пусть В(М)=В(А(М),0(Ы))=ЪьЪ2,...,Ъы. Ранее

отмечалось, что индекс совпадения 1С(В(1\[)) последовательности Ь|,Ь2,...,Ьм совпадает с вероятностью Рв0^=Ъу) совпадения шифрованных букв на слу­

чайно и равновероятно выбранных двух различных местах. Пользуясь опре­ делением математического ожидания случайной величины, получаем

Е(1С(В(Н))= X

Р(А)Р(С)Рв (Ь з= Ь г ).

Ае1м,Ое11

159

Последняя величина совпадает с РУ(Ь]=^ ). Определим события С(1), С(2). Событие С(1) состоит в выборе пары индексов (3,_)') из П(=), а С(2) - в

выборе (], ]') из П( * ). Тогда

Е Р(А )Р (0)Р В(Ь) = Ь;-) —

Ае1м,Об11

X Р(А)Р(С)|р в (Ь; = Ь у /С(1))Р(С(1)) + Р(Ъ; =Ь,-/С(2))Р(С(2))]=

Ае1к ,Се11

-2 Р(А)Р(С)[р в (Ь; = Ь Г /С(1))Р(С(1))|+-

Ае1м,Ое11

+2 Р(А)Р(С)1р в (Ъ ^= Ь г /С(2))Р(С(2))] =

Ае1к ,Се11

-

X Р (А )Р (0)|?в (а, +

= а,- + у,- / С(1))Р(С(1))]+

А€1ы,Оеи

+2 Р(А)Р(С)[рв (а, + у^ =а,- +уу/С (2))Р(С (2))] =

Ае^.СеО

= Р(С(1))	X	Р(А )Р(0)[рв ( а з = а у /С(1))]+
	Ае1М,ОеГ1
+ Р(С(2))	2	Р(А)Р(С)|рв (а} + у ; = а у + у,- /С (2 ))].
	Ае1ы ,Се11
Первое слагаемое преобразуем следующим образом:

Р(С(1))	X	Р(А)Р(О)|рв (а] = а г /С 0))Ь
А€1м,Оби
-Р(С(1))	2	2 Р (А )Р(0)|рв ( а з = а г /С<1))]=
	Ае1м ОбЦ
-Р(С(1)) 2		Р(А)[рв{а1= а г 1С(Я)}'^Р(_в)-

Ае!ы

Сй/

	160
-Р(С(1)) 2	/>(Л)[Л(<>у = « , /€(1))]=
=Р(С(1))2]	Р(А)[РА(а} = « ..)]=
А*1"

=Р(С(1) ) 2 Х .

16/

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

При случайном и равновероятном выборе С из И и выполнении усло­

вия С(2) значения	у ., у у		в О случайны и равновероятны (см. лемму 4). С
учетом этого факта преобразуем теперь второе слагаемое.
Р(С(2))	2	Р(А)Р(С)|рв (а, +у^ = а^- + у,-/С (2))]=
= Р(С(2))	^		р(А )р(УгУ)')|.Рв(а ) + У) = а Г + У)')]=
Аб1ы ^ ,у Г б1х1
= Р(С(2))	^	р( А ) ^ р(У.|>У.г)[р в (а) + 4$ = а) +У) ' ) ] =
Ае1ы,			У;,?;'
= Р(С(2))	^	р(А)[р(а ^ + у . = а у + уг )],
А61ы,
где Р(а ] + у у		= ау + у у ) =		- вероятность события

(а ] + у у = ау + у у ) при случайном и равновероятном выборе

Г у ’У у

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

Р(С(2)) X	Р(А)[?(а] + Г ] = а г +у у ) ] =
А * 1 \
= Р(С(2))-5-		X	Р(А) = Р ( С ( 2 ) ) .
I 1	I	А <= 1\	V1 I

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