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

171

Пусть П(<1)=( П (<!,=),П(<1,(Ф)) - разбиение множества пар {1,2,...,М}х{1,2,...,Ы}, индуцированное разбиением К.(с1). Введем обозначе­

ние: П(а=)=|{Оо'}бП(а,=),

Положим, Р (П (ф ))= ^ ^ ^ —^ - вероятность случайного и равнове­

роятного выбора пары индексов (У'}из множества П(<1,=).

Ранее отмечалось, что величина ИБШ(В(ЪГ)) последовательности ЬьЬг,...,Ьк совпадает с вероятностью Рв(Ц=^-,ё) совпадения шифрованных букв на случайно и равновероятно выбранных двух различных местах, рас­ стояние между которыми кратно <1. Поэтому

Е(ИБШ(В(Н)) = Ру(ЪГ Ъ,,с1)= ^ Р(А)Р(О)Рв 0 у =Ъ г ,с!) =

Ае1м,Ое11

=х Р(А)Р(0)^в(ь] =ьг /а |р а г » Р (< ||р а л Ь

Ае1м,Се11

- Е Р(А)Р(0)[рв(а;+Т)			= аг + Т г /ё|рЦГ))Р((1|рО,з'))]=
АеУ,Ое11
= Р(Л|РОо'))	Е	Р(А)Р(С)[Рв (а) = а г /<1|раТ)]=
	Ае1ы,0б11
- р(Ф Щ '))	Е Е р(А )р(0 )1р в ( а , = а г /<1 |р ( Ш ] -
	А «1" ОвЦ
-В Д р О Л )	Е р(А)[р в ( а ,= а г / а | р ( ш ] 2 ; Р (С ).
	А еУ		Оец

= Р(Ф 0,Л ) X Р{А)[рв {а} = аг 1а I р 0 \ л ] =

Ае 1ы

=р(ФСЛ) X р(А)[рв(а] =«/)]=

Ае1"

- в д р о л у Е ^ - 1-" -^ - 2	N ( N - 1 )	у р * .
У ' N ( N - 1 ) % '		У '
Теорема доказана.

172

Обозначим через К.'=(М' ьМ'г,...,N'0 - произвольное разбиение мно­

жества {1,2,...,М}, а через П(К.')=(П (К.',=),П(К.',*)), разбиение множества пар (1.2......N1x11.2......N1. индуцированное разбиением К.’ (данное понятие определено выше). Разбиению П(Р') поставим в соответствие подмножество

1ДП(К.')) множества ключей К=1к. Последовательность	у \, у 2,. • •, УN из Iм
принадлежит 1ДП(В')) тогда и только тогда, когда у г у	для любой пары
(У } е П (К.',=). Рассмотрим пересечение К.' п К(б) разбиения

Р'=(К'ьЫ'2,...,Н'к) и введенного при доказательстве теоремы 3 разбиения

К(б)=(Ы|,И2,...,N,0 множества {1 ,2,...,И}, где	0 о+б,]'+2б,...}, )е {1 ,2,...,б}.
Разбиение К.' п В(б)~(п1,П2,...,п,) состоит из непустых блоков вида N^ 0 ^ ,

где)' е {1Д ... ,к}У е {1 ,2,... ,6}. Этому разбиению соответствует разбиение

П(К' Г\ К(б))=(П((К.' О К(б),=)),П((К.' п К.(б), Ф)) множества пар

{1,2,...,Ы}х{1,2,...,М}\{(У)у€ 1,И }. Напомним, что разбиению К.(б) соответ­ ствует П(б)=(П(б,=),П(б,( Ф)) - разбиение множества пар

{1 ,2,...,М}х{1,2,...,М}\{(У)у€ 1, N }, индуцированное разбиением К.(б).

Положим Р(п (а . . ) ) . № У	- у	-	1 ^ 1 (| ^ 1 - -0 , -
N ( N - 1 )	“		N ( N - 1)

вероятность случайного и равновероятного выбора пары индексов {У'}из

множества П(б,=), а Р (С /,/) е П(К'пК(с1) = ^	•
с	N ( N - 1 )

Пусть шифртекст В=В(Л) получается шифрованием случайного текста А=А(М) (выборки из распределения Р0) с помощью равновероятного выбора ключа <3=0(М) из ЩЩР')). Подсчитаем вероятность Ру(Ъ|=Ь|,б) совместного события: при случайном и равновероятном выборе различных позиций) и)' с

расстоянием, кратным б, элементы Ц и	случайного шифртекста В совпадут.
Имеем
Е(ИБШ(В(Ы)) = РУ(Ъ;=М) = X	Р(А )Р (0)Р в (Ь] = Ь г ,ё ),
Ае1м,Ое1Г
где Рв(Ь,,Ъ|,б) - вероятность совпадения шифрованных букв		в шифртек­

сте В=ЬьЬ2,...,Ьы, на случайно и равновероятно выбранных двух различных

местах У ', расстояние между которыми кратно б. Шифртекст В получен из открытого текста А с помощью гаммы О.

Последние равенства можно продолжить:

2 Р(А)Р(С)рв (Ъ; = ъ г ,а)=

Аб1м,с еи

г

173

-

2

Р(А)Р(0)Р в(Ъ; = Ьу, а, а Л е П (Г ,=)) +

Ае1ы,ОеО

+2 р(А)Р(0)Рв(ь, = ьг ,а, а ,г ) е п (к -,* » -

Аб1ы,Оеи

X р(А)р<а)рв(Ь; =ьг /а|рС|,|),аГ)бП(К',=)жа|ра1).а1)еП(к-,=))+

Ае1ы,Ски

+^ т т р,щ =ь,м\ш )и,т т ,*Ж А& ,пил)ьт ,*))

леЛса/

Напомним, что Ь^=а^ур Ъу=ау+уу и при выполнении условия (Ц')е П(К.',=) все ключи - гаммы из 11(П(К')) таковы, что уу=уу. Следователь­ но, первую сумму предыдущего выражения можно преобразовать так:

^Р(А)Р(0)Рв(^ =ат /ё|раХШ )еЩ Я\=)]Р(д|раХШ )еЩ Я\=))=

Ае1м,Сёи

‘ К Л \ М , Л Ш ' ) е Л ( К , = ) ) ' Е	= ^ ( А / . Л .О .Л е Д Я > ))=
Ае1"

=ру | /чл/ш.л6 ж*»)Е р*,

/е/ Для случайно и равновероятно выбранной гамме из ЩЩР')) вероятность со­ бытия

(у,=1, уу=Г) равна Р(у)=1)Р(уу=Г) для любых 1,Г, причем Р(УйО= у у | Для

любого 1 е I (см. лемму 4). Поэтому вторую сумму рассматриваемого выра­

жения можно привести к виду

ВДр(Ш Ш >Ц К >)) X Р(А)В(0(Рв(а,+у;=а,.+г,./а|рйОШ')€ПД',=‘)).

Ае^ОеП

Кроме того,

т ш )и л еЩ д )Т ,^ р ,(а 1+г1=агп г1л\ыл)ил*т,*)>

,сш

~Р(<11р О . Г Ш Л € Л (Л \* ))А

174

Получаем промежуточный результат:
Е<ИБШ(В(М)) = Ру(ЪГ М )=	Р(с11р и , Г ) , и , Л е Щ К ' = ) ) ^	Р> +
	/е /
		1
	+ Р{4 I Р и , Г Ш Л е Я(Д',*))— .
	!	' *
Продолжим выкладки:
н а I м . п и , л е щ я \= ) ) = р ( и ,г е
_ ^	I п с I (I I “ 1 )
с = 1	Я ( Я - 1)

Для подсчета вероятности Р(й? | р 0 , / ) , 0 \ Л е П ( К ' Л ) переобозначим разбиение К' г»К.(<1)= (пьП2,...,п(), состоящее из непустых блоков ви­ да п % где | 'е {1,2,... ,к}, зе {1,2, . Именно, пусть ( п ( п 2], . . и/а )) -

семейство непустых блоков пт> из системы (П|,п2,...,п()входящие в блок N3,

)<= {1,2,...,б}. Тогда .

Р{41рО\Л,и,Л е я(Д > ))= Р(О о')еп(вд=), 0 0 ')€П(К',^))=

4 \

Окончательно получаем			г	\
Е(ИБШ(В(Ы)) = РУ(ЬГ Ъ>А)= Р(й | р ( Ш		,( Ш € П (К \= ))	2
			I ? !	у
			^161
	+ Р ( < ) |р ( Ш , ( Ш е П ( Я > ) / ‘
			ч Л /
_ у	I П с I (I П с I ~~0 ( у р2	V
%	N ( N - 1 )	'
+- 1	1	чл
/ |	щ м -	с- 1

175

Таким образом доказана

Теорема 4. Пусть шифртекст В=В(Л) получается шифрованием слу­

чайного текста А=А(И) (выборки из распределения Р0) с помощью равнове­ роятного выбора ключа 0=0(М) из 11(П(К.')). Тогда вероятность РУ(^=Ь],(1) того, что при случайном и равновероятном выборе различных позиций] и]' у них расстояние будет кратно с! и элементы Ъ, и Ъу случайного шифртекста В совпадут, равна величине

1	N ( N - 1 )
1	1	а	((Л
+т т ; . , , . ,		, ' Е (	" /( " / - ! ) )•
| / | Щ М - 1) #			с = 1

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

Из полученного выражения для вероятности Ру(^=Ъ^,с1) следует, чхо она зависит не только от мощностей блоков разбиения К' (как это имело ме­ сто для вероятности РУ(Ъ|=Ъ^), но и от мощностей блоков пересечения разбие­ ний К' и К.(<1). Поэтому такая большая многозначность определения периода в шифре гаммирования по шифртексту, как в первом методе Вольфа Фридмана,

впредлагаемом методе БШ отсутствует.

Вслучае К.'=К.(с1) имеем к=с1=1, Ы'!==Ы|=^, 1}=1. Формула для Ру(Ц=Ь},с1) принимает вид

где Н=кс1+г. Ранее эта формула была получена в теореме 3.

Возможности использования т-грамм шифрованного текста.

Основная идея одного из направлений повышения надежности пред­ ставленных методов определения периода гаммы в шифре гаммирования со­ стоит в представлении последовательностей алфавита I в виде последователь­ ностей т-грамм алфавита I.

176

Через Р0(ш) обозначим вероятностное распределение на 1ш, опреде­ ленное вероятностями РОьЬ,...Дш) появления т-грамм 11,12,. • •Дт =М в со­ держательных открытых текстах; через А(Ы,ш)=М|,М2 Ммбудем обозначать реализацию случайной выборки объема N из распределения Р0(т). Последо­ вательность т-грамм М|,М2 Мыпри необходимости мы будем рассматри­ вать и как последовательность А(№п)=М1М2.. Мы=а1,а2,...,аыт символов алфа­ вита I длины №п (Ц Ц +1 - конкатенация слов М] и М^+1). Пусть

В(Ы)=В(А(Ы),0(К))=ЬьЬ2>...ЬЫт,

где Ъ}=щ+ у ^(то<111|), ] е {1 ,2,... ,№п}.

Последовательность В(Ы) будем трактовать как шифрованный текст, полученный зашифрованием текста А(1Ч) на ключе-гамме С(Ы) в шифре гам­ мирования (Х=1Ыт,К= II,У= 1Мт, 1),

®[Э1,а2>...ал т; У \ , У 2, -■ Nт ):=3ЬI ,Ь2 Ьмт .

Представляя гамму 0(Ыт)= у \,у г,...,у цткак последовательность т - грамм Г1,Г2,...,Гм, а шифртекст Ь,,Ь2 Ьыт как последовательность т-грамм

В ЬВ 2, . . .,Вм, можно говорить теперь о том, что мы зашифровали выборку М„М2,.. Мына ключе Г|,Г2,...,Гы, получив шифрованный текст - последова­ тельность т-грамм ВьВ2,...,Вм. Задача определения периода последователь­ ности т-грамм Г=Г1,Г2,...,Гы может решаться теперь полностью аналогично

рассмотренной ранее задаче определения периода гаммы при т=1. При этом надо иметь в виду, что если период последовательности Г равен Б, то период <1 последовательности О(N01) является делителем числа пЮ.

Очевидно, модель получения содержательных текстов в виде выборки т-гамм является значительным уточнением начальной модели получения со­ держательных текстов. Но надо иметь в виду, что, имея текст длины N (вы­ борку объема N1) в алфавите I, при переходе к т-граммам нам приходится ра­

ботать с длиной текста И /т (объем выборки уменьшается в т-раз) и, следова­ тельно, уменьшается степень приближения значения индекса совпадения (ин­ декса БШ) шифртекста к значениям теоретических расчетов (аналогично тому как уменьшается точность приближения относительной частоты встречаемо-

177

сти буквы в содержательном тексте к ее вероятности с уменьшением длины текста).

Определенным выходом из этой ситуации является рассмотрение всех ш-грамм 1^ +1,...,^+(т-1) последовательности 1Ь12, ..Ды длины N в алфавите I (таких ш-грамм всего N-(111-1). При этом нам ниже придется проводить расче­

ты впредположении, что эти т-граммы получены независимо друг от друга, что не соответствует действительности (например, очевидно, что ш=граммы

..,1|+(т-|)и ^+|,...,^+(т-1),1|+т зависимы). Тем не менее, такая неразумность

объяснима тем, что при большом N и небольшом ш большинство пар ш-грамм состоит из независимых ш-грамм. И остается надежда, что такой слабой зави­ симостью можно пренебречь. Проверка же применимости получаемых при этом предположении теоретических результатов осуществляется в таких слу­ чаях экспериментальным путем.

Обозначим через /% множество всех локально периодических после­ довательностей периода <1.

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

0=С(Ы) из 1^ . Причем, <1>ш. Тогда вероятность

Ру(Ь^+|,...,Ьз+т=^ ^ +1,...,^ +т;<1) того, что при случайном и равновероятном выборе различных позиций) и)' с расстоянием кратным (1 т-граммы Ь^+1,...,1}+т; ЪрЪр+1,...,Ър+т случайного шифртекста В совпадут, равна вели­

чине

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

ДОКАЗАТЕЛЬСТВО. Множеству /% =11 соответствует разбиение

ЩНМ,, N2,...,N<0множества {1 ,2,...,N 1 , где Ц)+сУ+2с1,...} ,)е {1,2,. .

Пусть П(ф=(П(с1,=),П(с1,( Ф)) - разбиение множества пар

{1,2,...,М}х{1,2,...,М}\ {(У),,)’б 1, N }, индуцированное разбиением К(ф.

178

Положим, Р(П(<1,=))=-^^— - вероятность случайного и равнове­

роятного выбора пары индексов (У'} из множества П(<1,=).

Ранее отмечалось, что индекс БШ(В(гп,Н)) последовательности ЪьЪг,...,Ьм совпадает с вероятностью Рв(Ь^+ь...,Ъ^т=Ъ^чь...,Ь^ +т;<1) совпа­

дения шифрованных букв на случайно и равновероятно выбранных двух раз­ личных местах, расстояние между которыми кратно <1. Поэтому

Е(ИБШ(В(т,К)) = Ру(Ь^+1,...,Ь]+<т.1)=Ь^-+1,...,Ьг+(т-1);Ф =

X р(А)р(^)рв(^	=Ьу,...,Ьу+(т_1),ё),
Аб1ы ,Се11

где Рв(Ь^+1,... ,^+т = ЪуЪу+1,... ,Ъ; +т ><1) - вероятность совпадения шифрованных

т-грамм в шифртексте В=ЪьЪ2,...,Ьк на случайно и равновероятно выбран­ ных двух различных местах У ', расстояние между которыми кратно <1. Шиф­

ртекст В получен из открытого текста А на ключе - гамме Ое\]=1% .

Последние равенства можно продолжить:

X Р(А)Р(0)Рв(Ьр...,ЬЖт_1) =Ьг,...,Ьг+(т_1),ё)=

Ае1м,Сеи

^р(А)Р(а)Рв(^,...,ьМт 1) =ь|,...,Ь;Ч<т_1),/а|рО,|))Р(>)|раО=

Ае1м,Об11

р(4|р(Ш	X	р(А)Р(С)РА(а^,...,а^т 1)	с1| р(У'))=
Ае1к ,Сеи
т р и л	Т .	р м р л	Се(/
	АеГр

Так как по условию <1 > т то при случайном выборе т-грамм

X р ( А ) р л ( ^ , . . . , а М т _п = а/,...,а/+(т_1),/^|/ЧЛЛ)=

Ае1\

X , Р(А)Р а (з 9”*>*у+(т —1) —а у,..., а	1)) —	р (а12>а2»**’»аш)
Ае1ы,	(а12,а2,...,ат ) е Г

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

179

Ру(Ъ^+1,... Д^+(т_1) Ь^Ь^+1,...9Ъ^+(т_1),(1)

_ № ■ = ) ! .. V Р 2,

~ К ф - 1 )		,	^		<а,г'*2"
4	’	(а12.а2,-,ат)б1
	_ (к + 1 )кг + к(к -			1)(с( - г )		^	п2
			м ы - п			^	- (а|2’“2’-"а”)•
			^			(а12,а2,...,ат)е/

Доказательство теоремы 3' закончено.

Возможности переноса изложенных результатов на шифры поточ­ ной замены (ПЗ).

В данном пункте, как и ранее, под открытым текстом мы будем пони­ мать выборку из распределения Р0=(РьР2,...,Р|1|), где Р; - вероятность буквы) (ее номера) в содержательном тексте.

Пусть К - некоторое множество подстановок на I. Рассмотрим шифр ПЗ (Х=1м, Км, У, 1), где шифрованный текст В=(ЬьЬ2,...,Ьы)=ДА,ст) получается из открытого текста А=аьа2,...,аыс помощью ключа а=стьст2,...,амбКм сле­

дующим образом: Ь]=а](а]),)е{1,...,Ы }.

Пусть <1 - период последовательности 0=01,02,.. .,стн (см. определение 2), в

случае ее локальной периодичности. Задача состоит в определении периода (1 последовательности а или же установления его отсутствия по известному шифрованному тексту В. Легко проверить, что значение индекса совпадения

(Ю) последовательности 3 = 11,12,...,1ц е Iм •

1)

1С(3>

^N ( N - 1 )

(?1 - частота встречаемости буквы 1 в последовательности 3 = 11,12,...,1ы)

совпадает с индексом совпадения последовательностй

сг(3 )=а(11),а(12),...,а(1н) при любой подстановке а на I. Предположим допол­

нительно, что |К|=|1| и нижние строки множества К подстановок образуют ла­ тинский квадрат, т. е. множества переходов любых двух различных подстано­ вок не пересекаются (это условие обеспечивает несложное доказательство аналога леммы 4 для рассматриваемого здесь шифра). Тогда полученные ра­ нее результаты по применению индекса совпадения для определения периода гаммы шифра гаммирования полностью переносятся и на рассматриваемый шифр поточной замены. Несложно проверяется и совпадение индекса БШ по­ следовательности 3 =11,12,-..Ды с индексом БШ последовательности

180

ст(3 )=ст(11),а(12),...,ст(1ы), откуда следует справедливость полученных ранее

утверждений для индекса БШ и для шифра ПЗ. Трактуя уравнение а+у=Ь как уравнение Тт(а)=Ь, где Т - подстановка вида Т(|)=з+1 (то<1(|1|), заключаем, что шифр гаммирования является частным случаем шифра ПЗ с множеством клю­ чей Км, где К=(Т, Т2,...,Т|11), Т1'1 - тождественная подстановка на I.

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

Рассмотрим шифр ПЗ (Х=1М,КЬ1,У,1), где шифрованный текст В=(Ъ|,Ъ2,...,Ъы)=Г(А,ст) получается из открытого текста А=а1,а2,...,ак с помо­ щью ключа - последовательности ст=аьСТ2,...,сты периода <1. Мы будем пред­

полагать, что нижние строки множества К подстановок образуют латинский квадрат |К|=|1|. Задача состоит в определении открытого текста А по извест­ ному шифрованному тексту В и известному периоду с! ключа о.

Метод протяжки вероятного слова. Пусть Ъ1,Ь2,...,Ъм - известный

шифртекст, ИНссН-г. Рассмотрим две его подпоследовательности.

Ь(, Ьг... ,Ь|,...	,Ь{к-1)(]+г,-
^1+л, Ьз+а,*• ■*Ь|+с),...	, Ь^+г

Выберем так называемое «множество вероятных слов» - слова, кото­ рые по нашему мнению, могут быть началом искомого открытого текста. Для опробуемого такого слова а'ьа'2,.:.,а',, предполагая, что оно является нача­ лом искомого открытого текста, находим первые а|,СТ2,...,ог, подстановок

ключа (пользуясь тем, что множество К известно и тем, что нижние строки этого множества образуют латинский квадрат. Действительно, уравнение ст(а)=Ь при известных а и Ь однозначно разрешимо относительно ст из К. Пра­ вильность угадывания вероятного слова а'ьа'2,...,а\ проверяется теперь на

«читаемости» расшифрованного текста сгГЧЬц-а), СТ2'1(Ъ2+(1),..., стг'сь.+а).

Если последовательность этих букв принимается как случайный (не­ читаемый) текст, то опробуется следующее вероятное слово. В случае же «чи­ таемости» этой последовательности полагают, что

СчСЬнсО, 0*2(62+01)5••-5 ^(Ъ +кО ^ &1+(1, 3 .2 +сЬ• • •5 а 1+с! 5 —

и стараются построить возможные продолжения	этого отрезка
открытого текста по смыслу первых его Xбукв а ^	а2+С1,..., а^. Затем опробо­

вать каждое такое продолжение а^+ь.-.^+а+с, т. е. найти с помощью Ъж1+1,...,Ъ1+с1+си этого продолжения последовательность подстановок

~ аж, -• - ,с*1+с, а затем для нее и расшифрованный отрезок текста