Математические модели открытого текста

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

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

Учет частот k-грамм приводит к следующей модели от­крытого текста. Пусть Р^(k)(А) представляет собой массив, состоящий из приближений для вероятностей p(b₁b₂...b_k) появления k-грамм b₁b₂...b_k в открытом тексте, kÎN, А= {a₁,..., a_n} – алфавит открытого текста, b_i Î A, i =1,…,k.

Тогда источник "открытого текста" генерирует последова­тельность c₁,c₂,...,c_k,c_k+1,... знаков алфавита А, в которой k -грамма c₁c₂...,c_k появляется с вероятностью р(c₁c₂...c_k) Î Р^(k)(А), следующая k -грамма c₂c₃...c_k+1 по­является с вероятностью р(c₂c₃...c_k+1) Î Р^(k)(А) и т. д. Назовем построенную модель открытого текста вероятностной моделью k -го приближения.

Таким образом, простейшая модель открытого текста – вероятностная модель первого приближения – представляет собой последовательность знаков c₁,c₂,... , в которой каждый знак c_i, i = 1,2,..., появляется с вероятностью р(c_i) Î Р⁽¹⁾(А), независимо от других знаков. Будем называть также эту модель позначной моделью открытого тек­ста. В такой модели открытый текст c₁c₂...c_kимеет вероят­ность

В вероятностной модели второго приближения первый знак с₁ имеет вероятность р(с₁) Î P⁽¹⁾(А), а каждый сле­дующий знак с_i зависит от предыдущего и появляется с ве­роятностью

где р(c_i-1c_i) Î Р⁽²⁾(А), р(c_i-1) Î Р⁽¹⁾(А), i=2,3,.... Други­ми словами, модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст c₁c₂...c_kимеет вероятность

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

Приведем примеры "открытых текстов", выработанных компьютером на основе частотных характеристик (алфавита со знаком пробела) собрания сочинений Р. Желязны объемом 10652970 байтов:

1. (Позначная модель) олисъ проситете пригнуть стречи разве возникл;

2. (Второе приближение) н умере данного отствии офици­ант простояло его то;

3. (Третье приближение) уэт быть как ты хоть а что я спящихся фигурой куда п;

4. (Четвертое приближение) ество что ты и мы сдохнуть пересовались ярким сторож;

5. (Пятое приближение) луну него словно него словно из ты в его не полагаете помощи я д;

6. (Шестое приближение) о разведения которые звенел в тонкостью огнем только.

Как видим, тексты вполне "читаемы".

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