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

211

самблю возможных последовательностей (причем вероятность расхождения равна нулю).

Параграф 4.2 Стационарные эргодические, модели содержатель­

ных сообщений

В этой модели открытые (содержательные) сообщения Аь= а ,а 2... а ь

представляются отрезками реализаций стационарной эргодической случай­ ной последовательности. Случайная последовательность называется стацио­ нарной, если распределение вероятностей отрезка этой последовательности а1+1а|+2...а !+к не зависит от 1 при любом конечном значении к. Если на отк­

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

Зададим распределение вероятностей Р(А1.) на последовательностях Аь=а,а2...а ь для всех Ь>0 с учетом заданных условных вероятностей

Р(а/Ац)= Р(Аца)/Р(Ац).

Всоответствии с формулами (1) и (2) (см. параграф 4.1) можно ввести

врассмотрение энтропию объединенной схемы А(Ь,= А ,А 2... А ь

Н(А (Ь))= - ]Г Р (А ь)1оё 2 Р(А ь),

которую называют энтропией отрезка последовательности длины Ь.

Из рассмотренных ранее свойств энтропии имеем

0< Н( А (Ь) )<1о§2п1=Ыо§2п.

Отношение Н( А (Ь) )/Ь называют средней энтропией, приходящейся на

одну букву набора а ,а 2... а ь . При этом всегда 0< Н( А (Ь) )/Ь<1о§2П

ДОКАЖЕМ теперь, что существует предел

' {	Н(А) = Н т — Н( А (Ь)).

Ь—юо

212

Рассмотрим условную энтропию

Ж А /А "-»)— Е р ( А ,- ,) Е Р ( а /А 1._|)1о8г Р С а/А ,..,).

Аналогично доказательству неравенства (3) (параграф 4.1), можно по­ казать, что для любого Ь

Н(А/Аа ) )<Н(А/Аа_1)).

Далее, легко убедиться, что Н( А (Ь+1) )=Н( А (Ь) )+Н(А/Аа) )<Н( А (М )+Н(А/Аа_1))

И

Н( А (Ь) )=Н( А 1)+Н(А/А,)+Н(А/А1А2)+...+Н(А/ А (Ь~1) )> Ш (А /А а_1)).

Отсюда следует, что

Н( А (Ь+1) )<Н( А (Ь) )+-^-Н( А (Ь)			Н( А а ) )
1	Н( А (ь+|) )< “ Н( А а ) ).
Ь + 1	'	'~ Ь

Таким образом, последовательность — Н (А(Ь)) при Ь —>оо является

невозрастающей последовательностью, ограниченной снизу нулем. Следова-

тельно, существует предел Н(А)(л - Н т — Н( А (Ь)). ь->«> 1^

Определение. Предел

Н(А) = 1 т Д Н (А(Ь)).

Ь —>оо

называется энтропией эргодического источника сообщений на одну букву или энтропией, приходящейся на одну букву в бесконечных наборах (с уче­

том стационарной эргодичности их получения).

Свойство «равнораспределенности» для эргодиче(:ких источников.

Это свойство формулируется следующим образом. Для любого 8>0

С

Р 1-1082 Р (А ,.)-Н (А ) > 8 —» 0 при Ь —> со .

Иными словами, утверждается, что при больших Ь все множество по­ следовательностей Аь, также, как и в независимом случае, можно разбить на два непересекающихся подмножества (А1-)* и (А1")**, которые обладают сле­

дующимисвойствами:	.	_
- для любой Аье(Аь)* вероятность Р(Аь)*2‘ь		,
- суммарная вероятность Р((А1')**)—> 0 при Ь —» оо.

Таким образом, распределение Р(АЬ) оказывается фактически сосредо­ точенным лишь на множестве (Аь)‘, причем входящие вДА1")* последователь­

ностипочти равновероятны, а их число почти равно 2Ь .

Отдельно стоит вопрос об оценке величины Н(А) . В некоторых уче­ бныхкурсах теории информации доказывается, что для стационарных слу­ чайных последовательностей предел Н(А) совпадает с условной энтропией знакапоследовательности, при условии, что известна вся предыдущая после­ довательность, то есть с «неопределенностью» очередной буквы последова­ тельности. Формально, последняя неопределенность записывается как

Нш Н(аь/а1,а2,...,ац) при Ь-»ос.

Все вышеизложенное (в частности, формулы) для абстрактной ста­ ционарной последовательности ИСПОЛЬЗУЕТСЯ для последовательности букв открытых (содержательных) текстов. При этом не учитываются нестационарности в их началах и концах. Из вероятностных свойств открытых тек­ стов следует, что непосредственный расчет значений Н( А (Ь)) и Н(а^аьа2,...,а1__1) возможен для небольших значений Ь. Для больших значений

I известны лишь косвенные методы их оценок. Например, К. Шеннон предла­ гал метод оценки Н(а^а1,а2,...,ац) основанный на задании случайно выбран­

ных Ь-значных отрезков открытого текста и отгадывании Ы-1 буквы. При это»! замечено, что с увеличением Ь до 20-30 величина Н(аь/аьа2,...,ац) за­

метно убывает. Другой метод оценки предельной энтропии связан с некото­ рой характеристикой языка, называемой его избыточностью. Этот термин возник в связи с тем, что каждая буква сообщения, при условии что буквы по­ являются в нем случайно, равновероятно, независимо могла бы нести инфор­ мацию, равную Нтах=1о§2п, где п - число букв в алфавите. В это же время сре­

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

нтах-н

214

называют избыточностью языка, а величину Н/Нщах - коэффициентом сжа­ тия.

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

п - мощность алфавита открытых текстов.

Представление о величине энтропии и избыточности различной инфо­ рмации на русском (Нтах=1о§232=5) и французском (Нтах=1о§226=4,7) языках дает следующая таблица.

	Н бит/буква	Н бит/буква	Б в процен­	И в процен­
	Русский язык	Французский	тах	тах
		язык	Русский язык	Французский
Язык в целом		1,40		язык
	1,37		72,6	70,6
Разговорная	1,40	1,50	72,0	68,4
речь
Литературные	1,19	1,38	76,2	71,0
тексты
Деловые	0,83	1,22	83,4	74,4
тексты

Принято считать, что для литературного текста Н=1 дв.ед, для деловой переписки Н=0.5-0.7 дв.ед.

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

Параграф 4.3 Энтропии шифртекста и ключей. Расстояния един­

ственности для открытого текста и ключа. Теоретическая стойкость шифров

I

Ненадежности открытого текста и клю ча.

Шифр шифрования (М,К,Е,1) включает в себя два вероятностныхвы­ бора: выбор открытого сообщения хеМ сХ и выбор ключа х^К. Тем самым

215

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

Н(М )=- ^ р (т )1 о § 2 р (т ).

шеМ

Аналогично, неопределенность, связанная с выбором ключа, дается выраже­ нием

Н (К )= -^ р (х )1 о § 2 р(х)-

ХеК

Неопределенность сообщения, так же как и неопределенность ключа могут изменяться, когда имеется возможность наблюдать криптограмму - шифрованный текст ееЕ=Р(МхК)сУ (Е - образ МхК при отображении 1) . Эту условную неопределенность естественно измерять условной энтропией.

Н(М/Е)= -	^ р(ш, е) 1о§2 р (т / е ) ,
	(т,е)еМхЕ
Н(К/Е)= -	^ р(е, X) 1о82 Р(Х / е) •
	(е.х)еЕхК

Введенные условные энтропии Шеннон назвал ненадежностью от­ крытого сообщения и ключа. Эти ненадежности используются в качестве теоретической меры секретности. В качестве обоснования такого использо­ вания можно привести следующие рассуждения. Если ненадежность сообще­ ния (ключа) равна нулю, то отсюда следует, что лишь одно сообщение (один ключ) имеет единичную апостериорную вероятность, а все другие - нулевую. Этот случай соответствует полной осведомленности дешифровальщика о со­ общении (ключе). Действительно, пусть

Н(М/Е)= - 2 Р ( т ’е) 1о82Р(т / е ) =0-

(т,е)еМхЕ

Тогда при любых (т,е)еМ хЕ

р(т,е)1о§2р(т/е)=0.

Выберем такие (т,е) для которых существует ключ Х(ш,е)=Х6 К такой, что ут=е. Для таких пар имеем р(т,е)>0, следовательно, из предыдущего ра­ венства получаем 1 о § 2 Р (т /е )= 0 , то есть р(ш/е)=1. Таким образом, по шифртек-

сту т открытый текст е восстанавливается однозначно.

Приведем некоторые формулы для ненадежности ключа и открытых сообщений. Рассмотрим вероятностные схемы, определенные на М, К, Е и совместную энтропию Н(М,К,Е). По правилам сложения энтропий имеем

Н(М,К,Е)=Н(МДС)+Н(Е/М,К)=Н(Е,К)+Н(М/Е,К).

216

Но Н(Е/М,К)=0, так как условия полностью определяют событие Е, Кроме того, Н(М/Е,К)=0, так как в шифре выполняется свойство однозначного рас­ шифрования. В связи с чем

Н(М,К,Е)=Н(М,К)=Н(Е,К).

Так как ключ и открытое сообщение в вероятностной модели шифра выбира­ ются независимо, получаем

Н(М,К)=Н(М)+Н(К).

Кроме того,

Н(Е,К)= Н(Е)+Н(К/Е).

Отсюда получаем формулу для ненадежности ключа Н(К/Е)=Н(М)+Н(К)-Н(Е).

Из этой формулы следует: если Н(М)=Н(Е), то Н(К/Е)=Н(К) и наобо­ рот. Формула для ненадежности сообщения получается аналогичным образом. Именно, имеем

Н(М,Е)= Н(Е)+Н(М/Е)=Н(М)+Н(Е/М),

откуда

Н(М/Е)=Н(М)+Н(Е/М)-Н(Е).

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

Н(М/Е)<Н(М,К/Е)=Н(К/Е)+Н(М/Е,К)=Н(К/Е)<Н(К). В последнем равенстве Н(М/Е,К)=0.

Ниже мы покажем, что для совершенных шифров, то есть шифров, для которых р(т/е)=р(т) при любых (т,е) (см. параграф 1.3) выполняется равен­ ство Н(М/Е)=Н(М), и полученное выше неравенство говорит о том, что для них неопределенность секретного ключа всегда не меньше неопределенности шифруемого текста.

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

Напомним, что примером совершенного шифра является шифр гам­ мирования. При шифровании двоичного сообщения т=ш 1,т 2,... ,Шьпри слу­

чайном и равновероятном выборе ключа - двоичной гаммы длины Ь имеем р(ш/е)=2"ь при всех т,е.

Теорема. Шифр (М,К,Е,1), где Е=ДМхК) является совершенным тогда и только тогда, когда Н(М/Е)=Н(М).

ДОКАЗАТЕЛЬСТВО. Имеем Н(М/Е)-Н(М)= - ^ р(ш, е)1о§2р (т / е) + ^ р(т)1о§2р (т ) =

ш,е

ш

217

ч = “ Е р ( т ’е)1о82Р(т / е) + Е			Х р (т ’е) 1о§2р (т ) =
т,е		т	[_ е
= - Е		Р (т, е)1о§2р ( т / е) + ^	^	р(т,е)1о§2р (т ) =
т,е		т	е
= -	2	2 Р(Ш’е)(1оё 2 Р(т / е) -		1о§2 Р(т »	=
	т	е
= Е	Е	Р(т >е)( 1о§2 р ( т » - 1о § 2 Р ( т / е))-=
т	е
= Е Х р ( т ’е) 1 о8 2 ( - 7 т \ ) =				Е	Р(т >е) 1оё 2 ^ т г -
т	е	р(т/е)	(т,е):р(т,е)^0		р(ш/б)

Если шифр совершенный, то р(т/е)=р(т) при всех парах (т,е). В част­ ности, для пар (т,е), при которых р(т,е)*0, выполняется равенство

1О8 2 Л М _ = 0 .

'. р(т/е)

Следовательно, Н(М/Е)=Н(М). .

Предположим теперь, что Н(М/Е)=Н(М), то есть

^	р(ш,е)1о§2 ^	-0.
(т,е):р(т,6)*0	Р (^е)

Тогда

р(т)=р(т/е) для пар (т,е): р(т,е)*0.

Для доказательства совершенности шифра достаточно показать, что р(т,е)*0 при любой паре (т,е)еМ хЕ. Докажем это. Для любого птоМ найдется е=е(ш) сусловием р(т,е)*0. Имеем

р(ш) = ^	р(ш, е) = ^ р (е)р(т / е) =	Е) р(е)р(т/е) =
е	е	е:р(т,е)*0
= р (т )	Е Р ( е>’

е:р(т,е)*0

так как р(т)=р(ш/е) для пар (т,е): р(т,е)*0. Откуда получаем: 2>(е)=1. Это равенство возможно лишь при суммировании по всем

е:р(т,е)*0

ееЕ, так как, по условию теоремы: Е=€(МхК), и поэтому р(е)*0 при любом ееЕ.

218

Следовательно, р(т,е)^0 при всех ееЕ, а так как ш выбиралось про­ извольным, то р(т,е)*0 при любой паре (т,е)еМхЕ, что и оставалось нам показать для завершения доказательства необходимости условий теоремы.

Расстояния единственности для открытого текста и ключа.

Ниже в данном разделе будут рассматриваться лишь поточные шифры (М,К,Е,1) с заданными вероятностными распределениями на М и К.

Напомним, что поточный шифр определен опорным шифром и соот­ ветствием между ключами и ключевыми последовательностями. Будем пред­ полагать. что М=1к. где I - алфавит открытого текста, а Г: МхК-»Е - сюрьек­ тивное отображение ЕсОь. где О - алфавит шифрованного текста.

Наряду с текстом т е М длины N и шифрованным текстом ееЕ длины N мы будем рассматривать их начальные отрезки гш и е^длины Ь<Ы. Будем считать, что вероятностное распределение на множестве М инлуцирует веро­ ятностное распределения на начальных отрезках гщ еМ^ сообщений ш из М. Последнее распределение и вероятностное распределение на ключах К инду­ цируют вероятностные распределения на начальных отрезках е^еЕ^ крипто­ грамм е из Е и другие совместные и условные распределения. П р и изучении

свойств рассматриваемого шифра будем считать, что N всегда больше рас­ сматриваемых нами значений Ь.

В связи со сказанным выше корректно введение и соответствующих энтропий:

Н(М1/Е0=- ^р(ть,еь)1о§2р(ть/еь),

т ь ,еь

Н(К/ЕЬ)= - X Р(еЬ’ X) 1о§2 Р(Х / еЬ) •

еь,Х Эти энтропии также трактуются как ненадежности части сообщения и

ключа. Отметим, что в поточном шифре множество ключей не зависит от длины Ь сообщения.

Теорема Шеннона.

1. Ненадежность ключа Н(К/Е|_) есть невозрастающая функция от Ь, то есть при любом 1/>Ь

Н(К/ЕО> ЩК/Еь).

2. Ненадежность первых к букв сообщения является невозрастающей функцией от Ь, то есть при

Н(Мк/ЕО> Н(Мк/Еь). 3. При любом Ь

Н(КУЕО>Н(Мь/Еь).

219

Справедливость утверждений теоремы вытекает из свойств условных энтропий.

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

На качественном уровне, под расстоянием единственности шифра по открытому тексту понимают минимальное натуральное число Ь, при котором по известному шифртексту еь длины I. однозначно восстанавливается соот­ ветствующее ему открытое сообщение Шь Аналогично, под расстоянием единственности шифра по ключу понимают минимальное Ь, при котором по известному шифртексту длины Ь однозначно восстанавливается использован­ ный ключ.

Такие качественные понятия не вполне точны. Действительно, видимо минимальное Ь, о котором идет речь (если оно существует), зависит от кон­ кретного шифртекста е, Ь=Це). Следовательно, видимо речь должна идти о среднем значении таких минимальных Це). С другой стороны, для каждого еь можно определить все множество сообщений ть, которые могут быть зашиф­ рованы шифром в криптограмму еь. Расстояние единственности шифра по открытомутексту можно определить теперь как минимальное Ь, при котором среднеезначение мощностей этих множеств равно единице.

Первое определение Шеннона расстояний единственности шифра.

Ранее было показано, что энтропия характеризует некоторый источник информации, в частности, вероятностные модели получения открытых (со­ держательных) текстов. Число открытых текстов и их вероятности оценива­ ются по фундаментальным теоремам теории информации, теоремам Шеннона, Хинчина, Макмиллана.

Аналогичную роль играет и условная энтропия ЩМь/Еь) - ненадеж­ ность части сообщения в вероятностной модели шифра. Она характеризует среднее число текстов длины Ь, которые могут соответствовать известному отрезку шифрованного текста. Именно, Шеннон полагал, что среднее число текстов пэь, которые могут быть зашифрованы в заданный шифртекст, равно

К(Ь)=2 Н<МЛ>, где 2- основание логарифма в выражении энтропии.

Аналогично 2н'к/\ )- среднее число (по всем еь) ключей, при которых

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

это значение становится равным единице, такое Ь называют расстоянием единственности шифра по ключу. Аналогично определяют расстояние един­

220

ственности шифра по открытому тексту, именно, как минимальный корень уравнения К(Ь)=2 Н(М[/Еь)=1, Таким образом, расстояния единственности шиф­ ра это минимальные корни уравнений

К(Ь)=2 Н(МЛ )=1,

2 Н(К/Е^)= 1

относительно Ь (если такие корни существуют).

Некоторые шифры устроены так, что их количество ключей растет с ростом длины Ь сообщений, например, шифр гаммирования. В этом случае возможна ситуация, когда К(Ь)—»ос с ростом Ь. Такие шифры называют асим­ птотически стойкими. Для таких шифров при достаточно большом Ь вели­ чина К(Ь) становится большой и среди К.(Ь) возможных текстов выбрать текст, который был действительно зашифрован в заданную криптограмму, становится невозможным.

Второе определение Шеннона расстояний единственности шифра (модель случайного шифра). ,

Прямой подсчет расстояний единственности шифра (по открытому, тексту и ключу), как правило, затруднителен. В связи с чем для их подсчета используют модель «случайного шифра». Пусть (Е,К,Х,Р) - шифр расшифро­ вания для шифра зашифрования, МсХ, где М - все множество содержатель­ ных открытых текстов длины N в алфавите I (|1|>2).

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

что при случайном и равновероятном выборе ключа х е К и расшифровании на нем криптограммы еь (Ь<И) вероятность получить содержательный текст рав­ на

2 НЬ

где Н - энтропия на букву содержательного текста в алфавите I, 2 - основание логарифма в выражении энтропии. Это число «почти» совпадает с вероятно­ стью выбора открытого текста длины Ь при случайном и равновероятном вы­ боре последовательности длины Ь букв алфавита (2НЬ - приближенное значе­

ние количества открытых текстов). Тогда при расшифровании шифртекста длины Ь на всех ключах из К мы получим в среднем

2НЬ

ИЧ -З -тО .)

III1-

открытых текстов. Так как Н<1о§г|1|, то отсюда следует, что г(Т)—>0 с ростом

Ь. Решая теперь уравнение л ' •