1.5. Модели открытых текстов

Введенная нами математическая модель шифра _В содержит вероятностные распределения Р(Х) и Р(К) на множествах открытых текстов и ключей соответственно. Если Р(К) определяется свойствами устройств, служащих для генерации ключей (которые могут быть случайными или псевдослучайными), то Р(Х) определяется частотными ха­рактеристиками самих текстов, подлежащих шифрованию. Характер таких текстов может быть различный: это могут быть обычные литературные тексты, формализованные дан­ные межмашинного обмена и т. д. Так или иначе, открытые тексты обладают многими закономерностями, некоторые из которых наследуются шифрованными текстами. Именно это является определяющим фактором, влияющим на надежность шифрования.

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

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

Один из естественных подходов к моделированию от­крытых текстов связан с учетом их частотных характеристик, приближения для которых можно вычислить с нужной точно­стью, исследуя тексты достаточной длины. Основанием для такого подхода является устойчивость частот 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. (Шестое приближение) о разведения которые звенел в тонкостью огнем только.

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

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

Критерии распознавания открытого текста

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

Итак, согласно нашей договоренности, открытый текст представляет собой реализацию независимых испытаний слу­чайной величины, значениями которой являются буквы алфавита А={а₁,...,а_n}, появляющиеся в соответствии с распре­делением вероятностей Р(А) = (р(а₁),...,р(а_n)). Требу­ется определить, является ли случайная последовательность c₁,c₂,...,c_k букв алфавита А открытым текстом или нет.

Пусть Н₀ – гипотеза, состоящая в том, что данная по­следовательность – открытый текст, Н₁ – альтернативная гипотеза. В простейшем случае последовательность c₁,c₂,...,c_k можно рассматривать при гипотезе Н₁ как случайную и рав­новероятную. Эта альтернатива отвечает субъективному представлению о том, что при расшифровании криптограммы с помощью ложного ключа получается "бессмысленная" последовательность знаков. В более общем случае можно считать, что при гипотезе Н₁ последовательность c₁,c₂,...,c_k представляет собой реализацию независимых испытаний некото­рой случайной величины, значениями которой являются буквы алфавита А={а₁,...,а_n}, появляющиеся в соответствии с распределением вероятностей Q(A)=(q(а₁),...,q(а_n)). При таких договоренностях можно применить, например, наиболее мощный критерий различения двух простых гипотез, ко­торый дает лемма Неймана-Пирсона.

В силу своего вероятностного характера такой критерий может совершать ошибки двух родов. Критерий может при­нять открытый текст за случайный набор знаков. Такая ошиб­ка обычно называется ошибкой первого рода, ее вероятность равна = р{Н₁ /Н₀}. Аналогично вводится ошибка второго рода и ее вероятность =р{h₀/h₁}. Эти ошибки определяют качество работы критерия. В криптографических иссле­дованиях естественно минимизировать вероятность ошибки первого рода, чтобы не "пропустить" открытый текст. Лемма Неймана-Пирсона при заданной вероятности первого рода минимизирует также вероятность ошибки второго рода.

Критерии на открытый текст, использующие запретные сочетания знаков, например, k-граммы подряд идущих букв, будем называть критериями запретных k-грамм. Они уст­роены чрезвычайно просто. Отбирается некоторое число s редких k-грамм, которые объявляются запретными. Теперь, просматривая последовательно k-грамму за k-граммой ана­лизируемой последовательности c₁,c₂,...,c_k, мы объявляем ее случайной, как только в ней встретится одна из запретных k-грамм, и открытым текстом в противном случае. Такие кри­терии также могут совершать ошибки в принятии решения. В простейших случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных k-грамм являются весьма эф­фективными.

Контрольные вопросы

–Чем отличаются подходы к обеспечению безопасности информации в криптографии и в методах сокрытия информации?

–Какими методами обеспечивается конфиденциальность информации?

–Что такое целостность информации?

–Для каких аспектов информационного взаимодействия необходима аутентификация?

–Какие средства используются для обеспечения невоз­можности отказа от авторства?

–В чем суть предварительного распределения ключей?

–В чем разница между обычным и открытым распределе­ниями ключей?

–Для чего нужны схемы разделения секрета?

–Что такое сертификат открытого ключа?

–Каковы функции центра сертификации ключей?

–Чем отличаются алгебраическая и вероятностная модели шифра?

–С какими целями в криптографии вводят модели откры­тых текстов?

–Как подсчитать вероятность данного открытого текста в модели первого приближения?

–Какие подходы используются для распознавания откры­тых текстов?

–Какая идея воплощена в расположении клавиш на клавиатуре пишущей машинке, компьютера, логотипа?