О числе осмысленных текстов получаемых в стационарном источнике независимых символов алфавита

Ранее отмечалось, что, любой что язык из которого составлены сообщения, обладает избыточностью. Язык избыточен, если для любого n возможные последовательности из n букв не равновероятны. Все естественные языки обладают избыточностью. Ниже приводится частоты появления букв в английских текстах. Они получены на 4 миллионах знаках из писем английского текста. (C.M. MEYER, S.M. MATYAS. Cryptography: A New Dimension in Computer Data Security).

a	Кол. а	Р(а)	а	Кол.а	р(а)
A		.0804	N		.0709
B		.0154	O		.0760
C		.0306	P		.0200
D		.0399	Q		.0011
E		.1251	R		.0612
F		.0230	S		.0654
G		.0196	T		.0925
H		.0549	U		.0271
I		.0726	V		.0099
J		.0016	W		.0192
K		.0067	X		.0019
L		.0414	Y		.0173
M		.0253	Z		.0009

Индивидуальные частоты букв в 4 миллионах знаков английского текста, P (a) = Кол.(a)/4,000,000.

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

Приближенное значение числа s осмысленных сообщений в заданном алфавите может быть оценено следующим образом. При достаточно большом n имеем

Р(i(1),i(2),…, i(n))= = =p,

где p(i) – вероятность возникновения i-й буквы, n(i) – частота i-той буквы в тексте i(1),i(2),…, i(n), , np(i) – среднее значение n(i) в текстах длины n. Когда длина сообщения n очень большая, в каждом сообщении буква i из I встречается приблизительно np(i) раз. Следовательно, для очень большого n, большинство сообщений для нашего источника имеют вероятность приблизительно равную =p. Просуммировав эти одинаковые вероятности мы должны получить величину приблизительно равную единице. Откуда получаем sp≈1 или . Следовательно,

Log₂s»-Log₂p» .

Если H= – определена как энтропия на знак для нашего источника сообщений, то s=2^nH. Используя значения p(a) из приведенной таблицы для английского языка, получаем энтропию H=4,17 на знак открытого текста. Таким образом, число содержательных сообщений на английском языке (подсчитанное с помощью простейшей модели стационарного источника независимых символов алфавита) может быть выражено как s»2^n4,17. Принимая во внимание вероятности пар букв (биграмм), троек (триграмм), и так далее, можно получить соответственно более точное значение s. Принято считать, что реальное значение энтропии на букву сообщения для английского языка (|I|=26) равно H=1,2.

Стационарный источник независимых биграмм. Открытый текст такого источника является реализацией последовательности независимых испытаний в полиномиальной вероятностной схеме с числом исходов равным m², где m – мощность алфавита I. Для простоты мы отождествим алфавит с множеством чисел {0,1,…,m-1} (обычно буква отождествляется с ее номером в естественно упорядоченном алфавите). Множество исходов взаимнооднозначно соответствует множеству всех биграмм алфавита. Эта модель характеризуется следующим равенством:

P(i(1),i(2),…, i(2n))= ,

где Р(х_2j-1=i,х_2j=i`)³0, для всех i,i`Î{0,1,…,m-1}, а

.

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

р11	р12	…	р1m
р21	р22	…	р2m
…	…	…	…
рm1	pm2	…	pmm

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

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

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

Р((i(1),i(2),…, i(n))=р(i(1))× .

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

р(s/t)³0, p(t) ³0, t,sÎ{0,1,…,m-1};

, tÎ{0,1,…,m-1};

p(s)= , sÎ{0,1,…,m-1}.

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

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

Стационарный источник зависимых k-грамм k³2. Эти модели характеризуются не только размером k рассматриваемых мультиграмм (символов, генерируемого сообщения), но и глубиной межсимвольной зависимости. Глубина зависимости определяется как размер h мультиграммы (составленной из k-грамм), от значения которой зависит вероятность появления в сообщении следующей за мультиграммой k-граммы. Во всех языках зависимость вероятности k-граммы от последнего символа h-гаммы с ростом h заметно убывает, поэтому подобные модели используются на практике при небольших значениях h, тем более что с ростом h эти модели становятся весьма громоздкими.

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

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

В данной модели предполагается, что открытые сообщения реализуются некоторым стационарным эргодическим источником сообщений. Для такого источника определена предельная энтропия Н: Н_L®Н, при L® µ, где Н_L – энтропия на один знак сообщения длины L. Таким образом, Н – энтропия открытого текста на один знак.

Пусть Р(С_L) – вероятность реализации источником сообщения С_L длины L, I(C_L)=log_a – собственная информация сообщения С_L. Тогда по теореме Макмиллана при L®µ справедливо асимптотическое равенство

I(C_L)»LH,

откуда получаем, что для всех вероятностей Р(C_L):

Р(C_L)»a^-LH,

где а – основание логарифма, по которому вычисляется Н. В частности, число открытых текстов длины L (при большом L) приблизительно равно а^LH. Для литературных текстов на русском, английском языках Н=1 бит. Если N – число букв алфавита, то D=1–H/log_aN называют избыточностью языка, она показывает часть букв открытого текста, которую можно пропустить без потери содержания текста. Для русского и английского языков D=0,5–0,8.