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

161

ЕЦ(1С(В))= Ру(ЬГ Ьг)=

|Я (

^ > 2 + 1 (77^ )|

— .

7 ■ N ( N - 1 ) Т

N ( N - 1 ) | / |

Укажем и второй способ доказательства теоремы 1. Представим ве­

роятность

РУ(^=Ь] ) в следующем виде:

Ру(ЬГ Ьз-)=

X ру (ь}= ъ г

1^л р0\ Л

=

^

^

) ^

Р У (®у + ^

= аГ +

УГ) =

лу

- 1

= -----------

V

Р у (а, + у ,

= а г + у г ) +

^ - 1) Л,4

=)

;

7

7 7

+-----------

V

Р у ( а , - + г , = а г + г г ) =

Щ М - 1) Л,6 ?(.) У

У

7

7

7

=------------

У 1

Р у ( а , = а г ) +

V

Ру

(а ■+ у : —о. г + У г ) •

Щ м - 1 ) Л, 4

(=)

7

7

л г ( ; у - 1 ) Лу4

, )

у

7

7

7

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

|Л ( = ) 1	2 > ,2 + -1( Я ( * ) 1 ' 1
Л^(Л^ - 1)	V '	N ( N - 1 ) \1\

СЛЕДСТВИЕ ТЕОРЕМЫ 1. Если К. - разбиение множества {1,2,...,И} на од­

ноэлементные подмножества (к=1Ч, |П(=)| = 0), то есть рассматривается мно­ жество 1ДП)=1 то

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

Если К - одноэлементное разбиение (к=1), то

Еи(1С (В ))=Ру(ЪГ Ьг) = У > 2 .

I

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

б З а к . 5

162

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

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

Определение 2. Назовем конечную последовательность ц,1 2 ,..., ло­

кально-периодической (или, кратко-периодической), если найдется натураль­ ное число <1, 26 <Н, при котором для любого ), в случае )+б <И, выполняется

равенство ^ =(+а. Число б с указанным свойством назовем локальным перио­ дом, или, короче, периодом данной последовательности. (Период конечной последовательности определен данным определением, вообще говоря, неод­ нозначно).

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

Обозначим через 1 ыа	-	множество всех локально-периодических
последовательностей периода		<1,	^ к й + г	и рассмотрим разбиение
К а = (^ ^ 2,...,^ ) множества номеров {1,2,...,N1, где
N ,={1,	1+4		...	,1+ к б}
И2={2,	2 + 4		...	, 2+к<1}
К ={г,	г+4		....	, г+кб}
Н+г={г+1, г+1+4			.... ,г+1+(к-1)б}
Мг+2= {г+2, г+2+4			........, г+2+(к-1 )б}
N „ = {4		24	...	,б+(к-1)<1}.
Любая последовательность из			такава, что ее элементы, стоящие на

местах с номерами из одного блока номеров, одинаковы. Разбиению Ка соот­

ветствует рзбиение Па =( П а (=),Па(^ )) множества различных пар номеров.

При этом ясно, что /^=Щ П), так как, очевидно, любую последовательность

длины N с периодом б можно получить случайно и равновероятно, выбирая б-грамму в алфавите I и повторяя ее необходимое число раз до получения по­

следовательности длины N. Следовательно, \1 ыа|=|1|с1, и для подмножества Па

(=) пар различных элементов из П а(=) получаем

163

|ПД=)|=(к+1)кг + к(к-1)(д-г),

где к и г определены равенством Н=кё+г (г - остаток от деления N на ё). Ис­ пользуя последнее равенство, получаем

|Ц |(* )Н*(Ы-1 ) - (к+1)кг - к(к-1)(ё-г).

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

СЛЕДСТВИЕ 2 ТЕОРЕМЫ 1. Пусть шифртекст В=В(Ы) получается шифрованием случайного текста А^М) (выборки из распределения Р0) с по­

мощью равновероятного выбора ключа 0 (>1) из множества I ^ всех периоди­

ческих последовательностей периода ё, М=кё+г. Тогда справедливы равенства

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

_ (* + 1)*г + * ( * - 1Х</^г) у р2					(* + 1)*г+ * (* -!)(< /- г )			1
N ( N - 1 )			Т	'	N ( N - 1 )			| / | '
В частности, при г=0
			Еи(1С(В))=Ру(Ь]=Ь]-)=
_ Щ - \ ) а	у	р2	к (к -\)<1	1	_ N - 4 у	р2	| N(4 —1)	1
N ( N - 1 )	^	1	N ( N - 1 ) 1 1 1		< / ( # - 1) ^	'	(ЛГ- 1)йГ| / Г

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

Определение 3. Назовем конечную последовательность 11,12,---Ды К -

приближенной к локально-периодической последовательности г*, С2,---, пе­
риода ё, если расстояние Хэмминга р (11Д2,... I*, г 2»■••,*	*у ) межДУ данными
последовательностями равно К. Последовательность	--Лы назовем после­
довательностью с К-приближенным периодом ё, если она является К-

приближенной к некоторой локально-периодической последовательности пе­ риодаё.

ЗАМЕЧАНИЕ 1. Пусть 1=2/|1| - кольцо вычетов по модулю |1|. Из оп­
ределения следует, что каждую	последовательность	с

6*

164

К-приближенным периодом периодом б можно представить в виде суммы по модулю |1| некоторого вектора - последовательности 11,12,...Ды периода <1 из компонент, принадлежащих 2 /|1|, и некоторого вектора «помех» С(Ы,К)=С1,С2,...,сыс числом К ненулевых компонент. Очевидно, верно и об­

ратное утверждение: сумма такого вида будет последовательностью с К- приближенным периодом <1.

Следовательно, процесс шифрования открытого текста А(М)=аьа2,... ам гаммой

0(Т4)= г[Хг ,—Хн с К-приближенным периодом (1 можно представить в виде

последовательного выполнения двух процессов: наложения на открытый текст А(И) вектора помех С(Ы,К) и затем зашифрования результата гаммой 1|,12,...Дн периода <1.

ЛЕММА 5. Пусть а:,а2 амвыборка из распределения Р0=(РьР2,. • -,Р|1|), а С(Ы,К)=С1,с2,...,См - равновероятно выбранный вектор из

множества всех векторов, имеющих ровно К ненулевых компонент. Тогда по­ следовательность аД,а'2,... а'ы.где а^ =а^ (шос!(|1|) является выборкой из рас­ пределения Р'о=(Р' 1,Р'2,. • .,Р'|1|),

где

Р - . - ИО-	........ * .............		I ' 1. . ) *	1
	Щ Ы - К + Х) ( \ 1\ - 1)			| / | - 1 Щ М - К + 1)
ДОКАЗАТЕЛЬСТВО.
Р(а] +^=п) = Р(а} =1Л^=0)Р(С|=0) + Р ^ +03=1/^					^ 0)Р(с] ^ 0)=
	г. к-1	+ Щ	+сгУс}	)Р(сх * 0) Р(а, *!) =
Р, (1 -
	^лг	у~,К-1	,	у-'К-1
	=Р1 (1-----	ёт - ) + ~ --------		пг-(1-Р0=
		С*	| / | - 1	С*
=Р| (1______ * ---------			)+ ^ ----------	^ --------	(1-Р;)=
	Щ Ы - К + 1)		\ 1 \ - 1 Щ Ы - К + 1)

I

165

=Р, (1----------------------------------	^ Р , +
Щ Ы - К + 1)	| / 1-1 Щ И - К + Г)
+- 1	К
| / | —1 Щ Ы - К + 1)

- р , (. ______* ---------------			!------------	* --------	) +
Щ Ы - К + 1)			| / 1-1 Ы ( Ы - К + 1)
+-	1		К
	1 1 - 1	Щ И - К + 1)
- Ы 1 - . , - К ................	/ ' .	. ) +	‘	*	+ 1)
М ( Ы - К + 1) ( | / | - 1 )			| / | -1	М(Ы - К

Пусть последовательность а'ьа'2,...а'л, получена зашифрованием слу­ чайной выборки из распределения Рр=(Р1 ,Р2 ,...,Р|1|) наложением случайно и

равновероятно выбранной гаммы из множества всех гамм с К-приближенным периодом <1.

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

решенной задаче для гаммирования случайной последовательностью периода <1.

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

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

фиксированного ключа С(Ы)=у{, у 2,...,уц. Тогда среднее значение Е(1С(В))

индекса совпадения случайного шифртекста совпадает с вероятностью Р(Ьр=Ъу) совпадения букв на случайно выбранных различных местах в случай­

ном шифртексте, и это значение равно

I П(=) | у „2	1	V	V	Р Я
N ( N - 1 ) % 1	N ( N - 1 ) ^ ^			1 , + №
где П(=) - множество всех различных позиций 3,			для которых у . = у г , а

П(* ) - множество всех остальных позиций (операции в индексах по модулю |1|).

						166
ДОКАЗАТЕЛЬСТВО.
Р(ЪГ Ъ;)=Е(1С(В))=
ф ,						. , 2	р <	«	,	+ » ) -
~ -----------	У	Р	(а 1+Х,- = а г + 7 г)				+
Щ М - 1) ,„ 4 =)		7 7			7	7
+ -----------	У	Р(а,		+ у ,	= а г + у г ) =
М(Ы- 1)л,4 (*)		7		7	7	7
= -----------	У	Р ( а , = а г) + .					У Р	{ а , + у ,		= а г + у г ).
Щ М - 1) л,4 =)				' '	А ( ^ - 1) 7,,4 #) к ' ' '
Вероятность	Р (а] + у ]		= а ~ + у г )			представляется в виде
Р (а} + у } = а г			+ Г / ) = Е			Р|Р.+/ ,	- / г .
					/е /
в частности,	Р (ау. = а,..) = У /* 2 . Поэтому
				/е /
Р(Ь3=ЬГ)=Е(1С(В)= -- Я У -				У	Р]	+ -----------		У	У Р1Р1+у_у..

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

Пусть (Х=1Ы,К= 11,У= Iм, 1), IIС I м - шифр гаммирования

Да^аг

ьУ 2,---,Уи)= ЬьЪ2,...Ъм.

Здесь А(КГ)= а|,а2 ан - открытый текст, 0 (Ы)=у, ,у 2,...,ум - гамма из И, В=

Ь|,Ь2 Ьн - шифрованный текст.

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

/

Статистические методы.

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

167

тии»- установления факта того, что два заданных шифртекста получены за­ шифрованием двух открытых текстов одной гаммой.

Пусть Ь1,Ь2,...,Ьы - известный шифртекст, полученый зашифрованием неизвестного открытого текста а!,а2,...,аы на ключе - гамме у\,у2 ,...,уы- Для проверяемого периода с1 образуется вспомогательная последовательность

ЪгЪ,+<ь Ь2-Ь2+<1, ...,ЪгЪ]+сЬ...,Ь(к.|)а+г-Ьы+г , И=кб+г.

Наномним, что вычитание и сложение проводится по модулю |1| номе­ ров букв, упорядоченных в естественном расположении. Так как ^ = а ^ , то, в случае истинного периода (1 гаммы, получаем

длялюбого ) е {1 ,... ,(к-1)с1+г}, то есть вспомогательная последовательность

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

равно Р.=(р!,р2,...,Р|ц) (ГИПОТЕЗА Н(0)), где р]= ^ РСРС' >сумма берется по

с-с'=)

всем с,с': с-с'=) (тоб |1|) .

Если б не является истинным периодом гаммы, то Ь г^+ ^+ у^+а-у^ .

Естественно предположить, что знаки у^+а выбирались при шифро­ вании независимо. Вспомогательная последовательность в этом случае не яв­ ляется «разностью двух открытых текстов». При случайном выборе открытых текстов аьа2,..., а(к.1)а+г; а1+а,а2-щ,...,ака+г нередко предполагают, что вспомога­

тельная последовательность является случайной независимой выборкой из равновероятного распределения на I (ГИПОТЕЗА Н(1)).

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

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

168

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

Первый метод Уильяма Фридмана. Первый метод Уильяма Фрид­ мана состоит в том, что для данного шифртекста В вычисляют индекс совпа­ дения 1С(В) и сравнивают его с величинами

</ (ЛГОи (Л Г-1) < / | / |

При достаточной близости 1С(В) к одной из этих величин при некото­ ром б, предполагают, что период равен этому б. Согласно открытым публика­ циям (см., например, ФЬп С. Кш§. 1994. Ап А1§опфт 1ог Фе Сотр1е*е АиЮта(ес1 Спр1апа1уз15 о!- РепоФс Ро1уа1рЬаЬеис ЗиЬзйШНоп С1рЬег5. СгурЮ1о§1а.

18 (4), 332-355) данный метод удовлетворительно работает при использова­ нии для зашифрования локально-периодических последовательностей перио­ да не более 5. С точки зрения обоснованности применения данного метода лучше сравнивать 1С(В) с более точным выражением

	Еи(1С(В))=Ру(ЪГ Ъг)=
_ (к + \)кг + к(к —1)(с? —г)	•у'рг +,^	(к + 1)кг + к ( к - г)	1
N ( N - 1 )	,	N ( N - 1 )	| 7 | ’

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

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

вом, что значение
N - 4 у р2 ^N { 4 - 1)	1
1) & ' ( А - \)с1	1 1 1

математического ожидания индекса совпадения шифрованного текста для класса И периодических гамм фиксированного периода (1 совпадает со значе­

нием целого ряда различных классов гамм. Это следует из теоремы 1, где до­ казано, что это среднее значение

Еи(1С(в))= рУ(Ь|=ф)=	Щ Ы - 1 ) \ 1 \
' 1 N ( N - 1 ) Т

определено разбиением К=(МЬМ2,...,Н;) множества 1, . В частности, из это­

го факта следует, что значение Еи(1С(В))= Ру(к^=Ъ;) для класса гамм периода <1 остается инвариантным относительно одновременной перестановки знаков во всех периодических гаммах - ключах.

Второй метод Уильяма Фридмана.

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

Ь|01,Ь01+<нЬ1,01+2<Ь Ь2,Ь2+(1,Ъ2+2<Ь

Ьа,Ьа+а,Ьа+2а,...

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

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

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

Метод БШ.

Предлагаемый метод определения периода гаммы в шифре гаммиро­ вания по известному шифртексту В= ЬьЬ2 Ък состоит в следующем.

Выписываются все пары номеров ],р , для которых Ь, = Ъ,-. Пусть П(В,=) - множество таких пар. Очевидно, |П(В,=)|= ^ Р; (Р; —1), где Р; - час­

тота встречаемости буквы 1 в шифртексте В.

Каждой паре (ьГ) из ЩВ,=) ставится в соответствие расстояние р(]о ), равное абсолютной величине разности между] и]'. Ищется максимальное по мощности подмножество П(В,с1,=) пар в П(В,=) такое, что их расстояния р(У') имеют некоторый общий наибольший делитель <1, отличный от 1. Подсчиты­ вается величина

170

ИБШ (В,ё) = !П(В,с1’ ^

'N ( N - 1)

и сравнивается с величиной
Ец(ИБШ(В,<|))= ^ + 1)кг + к ( к - 1 у а - г )	^ ,
.ЛД(У-1)	т*

где к, г определены равенством М=кё+г. Если эти величины близки, принима­ ется гипотеза о том, что шифрование проводилось гаммой периода <1. В про­ тивном случае, эта гийотеза отвергается.

Обоснование метода БШ.

Для шифрованного текста В= ЪьЪг,...^ величина

ИБШ(В,с1) = |П(-В’с1,=)|

N ( N - 1)

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

боре различных позиций] и]' с расстоянием, кратным <1 элементы Ъ, и Ь,- сов­ падут. Действительно, по определению множества П(В,(!,=), ему принадлежат те и только те пары (], ]'), при которых <1 |р(У') ц ^ = Ъу , а N(N-1) - число всех

пар различных позиций в последовательности В= Ьм.

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

Теорема 3. Пусть шифртекст В=В(М)=Ъ1,Ь2>... Ьм получается шифрова-

. нием случайного текста А(Ы) (выборки из распределения Р0) с помощью

равновероятного выбора ключа 0(Л) из 1%. Тогда вероятность Ру(Ц=^,ё)

/

того, что при случайном и равновероятном выборе различных позиций] и^ с расстоянием, кратным <1, элементы ^ и Ъу случайного шифртекста В совпадут (имеется в виду вероятность совместного события: равенство букв на местах], ]' и кратность расстояния между ними величине <1), равна величине

(к + 1)кг + к ( к - 1 ) ( с 1 - г )	у	р2
N ( N - 1 )	V	' ‘

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

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

К(ё)=(Ль множества {1,2,...,М}, где {)о+сУ+2<1,...},]е {1 ,2, . .