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

191

Под открытым текстом понимается реализация последовательно­ сти независимых испытаний в полиномиальной вероятностной схеме с числом исходов |1|=т. Исходу взаимно однозначно соответствует символ ал­

фавита I. Эта модель позволяет разделить буквы алфавита на классы высокой, средней и низкой частот использования. Ниже приводятся буквы высокой частоты использования для некоторых европейских языков (частота указана в процентах).

[язык			Буквы алфавитов и частоты их
				использованйя в текстах
1Английский	Е	12,86	Т	9,72	А	7,96	I	7,77	N	7,51	К.	7,03
[Испанский	Е	14,15	А	12,9	О	8,84	8	7,64	I	7,01	Я	6,95
1Итальянский	I	12,04	Е	11,6	А	11,1	О	8,92	N	7,68	т	7,07
|Немецкий	Е	19,18	• N	10,2	I	8,21	8	7,07	К	7,01	т	5,86
[Французский	Е	17,76	8	8,23	А	7,68	N	7,61	т	7,30	I	7,23
1Русский	О	11,0	И	8,9 ,	Е	8,3	А	7,9	н	6,9	Т	6,0

Для сравнения частот редких букв и букв, приведенных в таблице, укажем, что, например, в английском языке редкими буквами являются буквы Щ2, а их частоты в процентах оцениваются величинами 0,13, 0,12, 0,08, соответственно. Из этой таблицы видно, что не случайно итальянский и ис­ панский языки считаются певучими: на долю гласных приходится около по­ ловины всех букв.

Самыми частыми биграммами в русском языке являются (в процен­ тах)СТ (1,74), НО (1,29), ЕН (1,23), ТО (1,21), НА (1,20), ОВ (1,16), НИ (1,15), РА (1,14), ВО (1,08), КО (1,07).

Наиболее частые триграммы: СТО, ЕНО, НОВ, ТОВ, ОВО, НАЛ, РАЛ,

НИС.

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

ятность появления в сообщении.

Стационарный источник независимых биграмм.

Открытый текст такого источника является реализацией последовательности независимых испытаний в полиномиальной вероятностной схеме с числом исходов равным т 2, где ш - мощность алфавита I. Для простоты мы отожде­ ствим алфавит с множеством чисел {0,1 ,...,ш -1 } (обычно буква отождествля­

ется с ее номером в естественно упорядоченном алфавите). Множество исхо-

I

192

дов взаимнооднозначно соответствует множеству всех биграмм алфавита. Эта модель характеризуется следующим равенством:

Р 0(1),1(2),...,1(2п ))= П Р (х2 н = 1 2 Н х 2з = 1 2>),

1=1

г д е Р (х2].1=1,х 2]= 1 ')> 0 , д л я в с е х 1,Ге {0,1,...,т-1}, а

Х р(х 2И = Бр(х 2) = 0 = 1 -

1,1'

В качестве оценок вероятностей биграмм используются относительные частоты их появления в открытом тексте, которые вычисляются эксперимен­ тально на большом текстовом материале. Вероятности биграмм в алфавите {0,1,...,т -1 } могут быть сведены в матрицу размера тхш:

Р п	Р 12	Р1т
Р21	Р22	Р2т
. . .	. . .	• • .
Рш1	Рш2	Ртш

где р)к - вероятность биграммы ()к). Из матрицы вероятностей биграмм де­ шифровальщик может извлечь ряд полезных особенностей, свойственных ис­ точнику сообщений и языку в целом. Например, в английском языке все би­ граммы вида (я,...) имеют нулевую вероятность за исключением биграммы (Я,и), вероятность которой равна приблизительно 0,0011. Биграммы вида (а,...) имеют ненулевую вероятность за исключением биграммы (а,я).

Данная модель точнее по сравнению с предыдущей отражает особен­ ности языков и источников сообщений. В частности, согласно этой модели всякое сообщение, у которого на нечетном месте х^.ьх^ располагается за­ претная биграмма (У'), имеет нулевую вероятность. В то же время, моделью игнорируется свойственные языкам зависимости между соседними биграм­ мами. Например, вероятность слова «яияи» в данной модели английского языка оценивается величиной 1,21-10'6, хотя в языке оно не встречается. В меньшей степени указанные недостатки присущи следующей модели.

Стационарный источник марковски зависимых букв.

Открытый текст такого источника является реализацией последова­ тельности испытаний, связанных простой однородной цепью Маркова с т состояниями. Данная модель (как и соответствующая цепь Маркова) характе­ ризуется матрицей П переходных вероятностей: П=||р(8/1)||, 8,1 из алфавита {0,1 ,... ,т - 1 } и стационарным распределением вероятностей Р=(р( 1),..., р(ш))

193

наалфавите (на состояниях цепи Маркова). Вероятность случайного сообще­ ниявыражается формулой

п-1

Р(С(1 ),1(2),..„ 1(п»=р(1( 1»- П р О О + /1 0 ).

)=1

Переходные вероятности и стационарное распределение удовлетворяют усло­ виям:

р(з/1)>0, р(1) >0,1,8€ {0,1,... ,ш-1};

т -1 2 ]р (8/ 1) = М е { 0,1 ,..;,т - 1 };

8=0

т - 1

р(8)= 2 р(1)р(з/1), 8€ {0,1,... ,т - 1}.

1=0

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

Стационарный источник независимых к-гамм, к>2.

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

Стационарный источник зависимых к-грамм к>2.

Эти модели характеризуются не только размером к рассматриваемых мультиграмм (символов, генерируемого сообщения), но и глубиной межсимвольной зависимости. Глубина зависимости определяется как размер Ь мультиграммы (составленной из к-грамм), от значения которой зависит вероят­ ность появления в сообщении следующей за мультиграммой к-граммы. Во

всех языках зависимость вероятности к-граммы от последнего символа Ь-

7З а к .5

194

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

Нестационарные источники сообщений.

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

Теоретико-информационная модель источников сообщений.

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

Вданной модели предполагается, что открытые сообщения реализу­ ются некоторым стационарным эргодическим источником сообщений. Для

такого источника определена предельная энтропия Н: Нь—»Н, при ос, где Нь - энтропия на один знак сообщения длины Ь. Таким образом, Н - энтропия открытого текста на один знак.

Пусть Р(СО - вероятность реализации источником сообщения Сь дли­

ны Ь, 1(Сь)=1о§а— -------собственная информация сообщения О,. Тогда по

Р(СЬ)

теореме Макмиллана при Ь—»ос справедливо асимптотическое равенство 1(0>Ь Н ,.

откуда получаем, что для всех вероятностей Р(С[.): Р(СО*аш,

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

зывает часть букв открытого текста, которую можно пропустить без потери содержания текста. Для русского и английского языков 0=0,5-0,8.

\

195

Параграф 3.3 Критерии на осмысленные сообщения

Важнейшей задачей криптографии является задача распознавания-от­ крытых текстов. .Имеется некоторая последовательность знаков, записанная в алфавите I: .

3 =11,12,-.П., ^ е У е {1 ,2 ,...,Ь } .

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

Формальное правило, которое позволяет ответить на данный вопрос, называется критерием на открытый текст. При построении таких критериев обычно ограничиваются использованием моделей открытых текстов (см. па­ раграф 2.3.) При этом множество X открытых текстов заменяется на некото­ роедругое множество, тексты которого формально считаются открытыми текстами в этой модели.

В терминах математической статистики можно сказать, что ряд таких критериев позволяет различать две гипотезы: НО - последовательность 3 - открытыйтекст (в принятой модели); Н1 - последовательность 3 - случайная равновероятная последовательность знаков. Любой статистический критерий различения двух простых гипотез, в частности, ряд критериев на открытый текст может допускать ошибки двоякого рода:

ошибка первого рода - имеет место гипотеза НО, а критерий принима­ ет гипотезу Н1, то есть отбраковывается открытый текст;

ошибка второго рода - имеет место гипотеза Н1 , а критерий принима­

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

Вероятности этих ошибок

а=Р(Н1/Н0), Р=Р(Н0/Н1)

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

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

7*

196

рением возможностей применения критериев запретных знаков и запретных биграмм.

Критерии запретных знаков и запретных биграмм.

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

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

«Открытый текст» (далее ОТ) 3 получается в результате выборки ш- грамм алфавита I из заданного вероятностного распределения на них: . {Р(а|,а2,.,ат), (аьа2,.,ат)€1т } - гипотеза НО. Причем данные значения вероят­

ностей соответствуют вероятностям их появления в открытом тексте (они по­ лучены путем маркировки достаточно длинного открытого текста).

Гипотеза Н1 - текст 3 получен выборкой его т-грамм из вероятност­ ного равномерного распределения на 1ш, вероятность появления любой т - граммы есть 1/|1|т.

Отберем Ь самых редких т-грамм и назовем их запретными. Поло­ жим, р=р(з) - суммарная вероятность их появления в ОТ. Остальные т - граммы назовем незапретными. Положим, р(н)=1-р(з) —суммарная вероят­ ность незапретных т-грамм. Суммарная вероятность появления в случайном тексте запретной т-граммы равна 0=Ь/|1|т.

Критерий запретных т-грамм с о с т о и т в поиске в последовательности 3 =11,12,'..Ль запретной т-граммы. Для этого просматривается первая т-грамма

•1,12,-• лт, вторая - 12,.. Лш+1 и т.д. Если запретная т-грамма отсутствует в 3, то

принимается гипотеза НО - считается, что текст открытый. Если нашли за­ претную т-грамму, то принимается гипотеза Н1 - текст считается случайным.

Всех т-грамм в тексте 3 есть Ь -(т-1). В случае т>1 т-граммы оче­ видно зависимы. Но далее, как мы увидим, расчеты ошибок критерия провЪдятся в предположении их независимости.

Рассчитаем ошибку а критерия а=Р(Н 1/Н0)=Р(н,н,... ,з,.. .н),

где Р(н,н,...,з,...н) - вероятность появления запретной т-граммы (хотя бы один раз) в выборке длины Ь -(т-1) из распределения {Р(а,,а2,.,ат),(а,,а2,.,ат)е Г }. Имеем

а=Р(Н1/Н0)=Р(н,н,. ..,3,.. .н)=1-(1-р)ь'т+|.

Случай запретных знаков, т=1.

В этом случае а=1-(1-р)ь, а р=Р(Н0/Н1)=(Ьд)ь=(1-Ь/|1|)ь.

197
Случай запретных биграмм, ш=2. Пустыи=2. Тогда	а= 1-(1-р)ы .

Проведем расчет Р=Р(Н0/Н1). Обозначим через У|/(Ь) ч и с л о всех п о ­

следовательностей в алфавите I длины Ь, не содержащих запретных биграмм. Тогда

Р=Р(Н0/Н1)=У|/(Ь)/|1|1'.

Положим, 1={ 1,2,...,п}. Для подсчета \|/(Ь) обозначим через \(^(Ь) - число последовательностей в алфавите I длины Ь, не содержащих запретных биграмм и оканчивающихся буквой . Тогда для ] е { 1,2,...,п} имеют место

рекуррентные соотношения ^(Ь+1)=у ,(Ь)Ьи+\р2(Ь)Ь2]+. • -М/„(Ь)Ь^ ,

где Ц =0, если биграмма д - запретная и Ьд =1 в противном случае. Рассмот­ римматрицу В=( Ъц) размера пхп и вектор

УЧЬИЧ' 1(Ь)> Уг(Ь),• • •, Уп(Ь)).

Предыдущие рекуррентные соотношения можно записать в виде ' ‘ \^ (Ь + 1)= чГ(Ь)В.

Элементы Ь-ой степени Вь матрицы В запишем в виде Ь^(Ь), Вь=(Ьц(Е)). Пре­ дыдущее равенство может быть продолжено так

у^(Ь+1)= У|/^(Ь)В=\|/^(Ь+1)= \р^(2)Вь|

или

Х|/](Ь+1)=х|/,(2)Ьц(Ь-1)+1|/2(2)Ь2](Ь-1)+. ..1)/п(2)ЬпХЬ-1), где]е{1,...,п}, ц/г(2) - число незапретных биграмм оканчивающихся на г, Ь^Ь-1) - число текстов длины Ь- 1 в алфавите I, начинающихся с г , оканчи­

вающиеся на^ и не содержащих запретных биграмм. Расчет величин \|/г(2) проводится непосредственно. Таким образом, расчет ошибки р сводится к расчету значений элементов матрицы Вь'2. Для подсчета этих значений ис­ пользуют асимптотические результаты. Один из подходов к их вычислению состоит в использовании теоремы Фробениуса и формулы Перрона.

Часть теоремы Фробениуса (см. /41, стр. 323Г).

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

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

рестановки строк и столбцов с одинаковыми номерами нельзя привести к виДУ

Гр сЛ

198

где Р и К. - квадратные ненулевые матрицы, а элементы подматрицы Т могут быть произвольными. НеразложимЪсть матрицы В следует из ее связи с от­ крытым текстом. Степень разложимой матрицы имеет аналогичный вид. Если бы матрица В была разложима то нашлись бы Ц(Ь), которые равнялись бы нулю при любом Ь, то есть переход от знака г к знаку} невозможен ни за ка­ кое число шагов Ь. Это обстоятельство, очевидно, не соответствует природе открытого текста, и поэтому матрицу В можно считать неразложимой.

Таким образом, матрица В удовлетворяет всем условиям теоремы Фробениуса и, следовательно, имеет простое максимальное по модулю харак­ теристическое число X.

Матрица называется ациклической, если ее путем перестановки строк и столбцов с одинаковыми номерами нельзя привести к виду

' О Т1,2	0 "
О .	О

О. . Т г-1,г ’

ДГгД 0 . О )

где все диагональные элементы - нулевые квадратные подматрицы, а все мат­ рицы Т1,2; Т2,3;..., Тг-1,г; Тг,1, стоящие надТлавной диагональю, - ненуле­ вые. В противном случае, матрица называется циклической. Цикличность матрицы В влечет наличие таких знаков г и], что переход из г в\ в открытом тексте возможен лишь за число шагов, кратное г. Последнее не характерно для открытого текста, в связи с чем матрицу В считают ациклической.

Из формулы Перрона (см., например, Романовский В.И., «Дискретные цепи Маркова») следует, что асимптотически при Ь—»ос имеет место соотно­ шение

Ьг((Ь)= с ^ , гД е {1 ,2,... ,п},

где Сц от Ь не зависят. Воспользуемся этим соотношением для получения при­ ближенного значения \|/(Ь). Так как

\|/(Ь)= \|/,(Ь)+\|/2(Ь)+...у„(Ь),

то при Ь—>ос
У (Ь )* Е Е ^ г ( 2)с д^Ь" 2 = ^ Ь" 2	]С 2 Ж ( 2)Сд .
)=1 г=1	;=1 г=1

Двойная сумма не зависит от Ь, поэтому, обозначив ее через С, получим

у(Ь)*СХь'2,

откуда следует, что

199

Ь —>00

у ( Ь )

Таким образом, вычисляя непосредственно числа \|/(2), \|/(3),... и рас­ сматривая их последовательные отношения, можно вычислить X с любой сте­ пенью точности. Пусть для достижения нужной степени точности пришлось подсчитать \|/(2), у(3),..., у(к). Тогда для Ь>к имеем приближенную формулу

\|/( Ь ) »М /(к )А 1" к.

Разделив полученное число на пь, получим приближенное значение вероятно­ сти Рюшибки 2-го рода.

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

ПРИМЕР. Пусть для русского языка запретными буквами выбраны: Ф,Ц,Щ, Э. Тогда р*0,01. Р=Ь/К=4/30«0,133. При Ь=100 получим а«0,64, Р»0,63-10‘б. При Ь=50 получаем а«0,40, р«0,79-10'3. Заметим, что в итальян­ ском языке очень редко используются 5 знаков латинского алфавита: 1,К,\^,Х,У, суммарная вероятность которых р«0,003, в то время как Р=5/26«0,192. Для этого случая критерий работает намного лучше. Если для русского языка выбрать 376 самых редких биграмм то их суммарная вероят­ ностьсоставит р*0,0093, при этом 0=376/900*0,416. Непосредственный под­ счетдает у(2)=524, ц/(3)=10416, \|/(4)=203587 и т.д. Последовательные при­ ближения,значения X имеют вид

19,8778, 19,5456, 19,6030. Положив Х=19,60 получаем при Ь=100

а«0,61, р*4,45-1017.

Среднее число знаков, на котором срабатывает критерий.

Рассмотрим критерий запретных знаков, т=1. Пусть %- случайная ве­ личина, принимающая значения номера знака, на котором сработал критерий при проверке случайного текста, ^е {1,2,... ,Ь}. Событие ^=к означает, что на первыхк- 1 местах в случайном тексте имеются незапретные знаки, а на к-ом

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

Р С ^ к М ^ г ' д ,

К < ь .

200

Согласно правилу, определяющему действие критерия, его работа заканчива­ ется на Ь-ом шаге принятием гипотезы НО или Н1, если на первых Ь-1 местах стояли незапретные знаки. Следовательно,

Р($=ЬМ 1-С »Ы.

Математическое ожидание Е2, случайной величины 4 подсчитывается

непосредственно

Е^=2 к(1 - д ) к_1д

к=1

Используя обозначение (1-<3)=х и формулы

1 - х	= 1+х+...+хЬ-1	и	( 1 - х	Ьхы (1 - х ) + (1 - х ь )
1 - х			8х 1 - х	(1 - х ) 2
получаем		<3	<3
	<3

ГЛАВА 4. ТЕОРЕТИЧЕСКАЯ СТОЙКОСТЬ ШИФРОВ. ТЕОРЕТИКО-ИНФОРМАЦИОННЫЕ МО­ ДЕЛИ ШИФРОВ

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