Критерии на осмысленные сообщения

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

Á=i₁,i₂,…i_L, i_jÎI, jÎ{1,2,…,L}.

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

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

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

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

ошибка второго рода – имеет место гипотеза Н1, а критерий принимает гипотезу Н0, то есть за открытый текст принимается случайный набор знаков.

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

a=Р(Н1/Н0), b=Р(Н0/Н1)

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

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

Критерии запретных знаков и запретных биграмм. Один из простых в реализации критериев использует ту особенность открытого текста, что некоторые m-граммы алфавита появляются в нем очень редко. Итак, предполагают, что заданная последовательность знаков есть реализация некоторого случайного процесса. Примем следующую вероятностную модель. «Открытый текст» (далее ОТ) Á получается в результате выборки m-грамм алфавита I из заданного вероятностного распределения на них: {Р(a₁,a₂,.,a_m), (a₁,a₂,.,a_m)ÎI^m } – гипотеза Н0. Причем данные значения вероятностей соответствуют вероятностям их появления в открытом тексте (они получены путем маркировки достаточно длинного открытого текста). Гипотеза Н1 – текст Á получен выборкой его m-грамм из вероятностного равномерного распределения на I^m, вероятность появления любой m-граммы есть 1/|I|^m. Отберем h самых редких m-грамм и назовем их запретными. Положим, р=р(з) – суммарная вероятность их появления в ОТ. Остальные m-граммы назовем незапретными. Положим, р(н)=1-р(з) – суммарная вероятность незапретных m-грамм. Суммарная вероятность появления в случайном тексте запретной m-граммы равна Q=h/|I|^m. Критерий запретных m-грамм состоит в поиске в последовательности Á=i₁,i₂,…i_L запретной m-граммы. Для этого просматривается первая m-грамма i₁,i₂,…i_m, вторая – i₂,…i_m+1 и т.д. Если запретная m-грамма отсутствует в Á, то принимается гипотеза Н0 – считается, что текст открытый. Если нашли запретную m-грамму, то принимается гипотеза Н1 – текст считается случайным.Всех m-грамм в тексте Á есть L–(m–1). В случае m>1 m-граммы очевидно зависимы. Но далее, как мы увидим, расчеты ошибок критерия проводятся в предположении их независимости. Рассчитаем ошибку a критерия

a=Р(Н1/Н0)=Р(н,н,…,з,…н),

где Р(н,н,…,з,…н) – вероятность появления запретной m-граммы (хотя бы один раз) в выборке длины L–(m–1) из распределения {Р(a₁,a₂,.,a_m),(a₁,a₂,.,a_m)ÎI^m }. Имеем

a=Р(Н1/Н0)=Р(н,н,…,з,…н)=1-(1-р)^L-m+1.

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

В этом случае a=1-(1-р)^L, а b=Р(Н0/Н1)=(1-Q)^L=(1-h/|I|)^L.

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

Проведем расчет b=Р(Н0/Н1). Обозначим через y(L) число всех последовательностей в алфавите I длины L, не содержащих запретных биграмм. Тогда

b=Р(Н0/Н1)=y(L)/|I|^L.

Положим, I={1,2,…,n}. Для подсчета y(L) обозначим через y_j(L) – число последовательностей в алфавите I длины L, не содержащих запретных биграмм и оканчивающихся буквой j. Тогда для jÎ{1,2,…,n} имеют место рекуррентные соотношения

y_j(L+1)=y₁(L)b_1j+y₂(L)b_2j+…y_n(L)b_nj,

где b_rj =0, если биграмма rj – запретная и brj =1 в противном случае. Рассмотрим матрицу В=(b_rj) размера n´n и вектор

y^®(L)=(y₁(L), y₂(L),…, y_n(L)).

Предыдущие рекуррентные соотношения можно записать в виде

y^®(L+1)= y^®(L)В.

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

y^®(L+1)= y^®(L)В=y^®(L+1)= y^®(2)В^L-1

или

y_j(L+1)=y₁(2)b_1j(L-1)+y₂(2)b_2j(L-1)+…y_n(2)b_nj(L-1),

где jÎ{1,…,n}, y_r(2) – число незапретных биграмм оканчивающихся на r, b_rj(L-1) – число текстов длины L–1 в алфавите I, начинающихся с r, оканчивающихся на j и не содержащих запретных биграмм. Расчет величин y_r(2) проводится непосредственно. Таким образом, расчет ошибки b сводится к расчету значений элементов матрицы B^L-2. Для подсчета этих значений используют асимптотические результаты. Один из подходов к их вычислению состоит в использовании теоремы Фробениуса и формулы Перрона.

Часть теоремы Фробениуса см. [Гантмахер Ф.Р.Теория матриц.М.,1954, стр. 323].

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

где Р и R – квадратные ненулевые матрицы, а элементы подматрицы Т могут быть произвольными. Неразложимость матрицы B следует из ее связи с открытым текстом. Степень разложимой матрицы имеет аналогичный вид. Если бы матрица B была разложима то нашлись бы b_rj(L), которые равнялись бы нулю при любом L, то есть переход от знака r к знаку j невозможен ни за какое число шагов L. Это обстоятельство, очевидно, не соответствует природе открытого текста, и поэтому матрицу B можно считать неразложимой. Таким образом, матрица B удовлетворяет всем условиям теоремы Фробениуса и, следовательно, имеет простое максимальное по модулю характеристическое число l. Матрица называется ациклической, если ее путем перестановки строк и столбцов с одинаковыми номерами нельзя привести к виду

,

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

Из формулы Перрона см., например, [Романовский В.И., «Дискретные цепи Маркова»] следует, что асимптотически при L®µ имеет место соотношение

b_rj(L)= c_rjl^L, r,jÎ{1,2,…,n},

где c_rj от L не зависят. Воспользуемся этим соотношением для получения приближенного значения y(L). Так как

y(L)= y₁(L)+y₂(L)+…y_n(L),

то при L®µ

y(L)» .

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

y(L)»Сl^L-2,

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

=l.

Таким образом, вычисляя непосредственно числа y(2), y(3),… и рассматривая их последовательные отношения, можно вычислить l с любой степенью точности. Пусть для достижения нужной степени точности пришлось подсчитать y(2), y(3),…, y(к). Тогда для L>к имеем приближенную формулу

y(L)»y(к)l^L-к.

Разделив полученное число на n^L, получим приближенное значение вероятности b-ошибки 2-го рода.

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

Пример. Пусть для русского языка запретными буквами выбраны: Ф,Ц,Щ, Э. Тогда р»0,01. Q=h/N=4/30»0,133. При L=100 получим a»0,64, b»0,63×10^-6. При L=50 получаем a»0,40, b»0,79×10^-3. Заметим, что в итальянском языке очень редко используются 5 знаков латинского алфавита: J,K,W,X,Y, суммарная вероятность которых р»0,003, в то время как Q=5/26»0,192. Для этого случая критерий работает намного лучше. Если для русского языка выбрать 376 самых редких биграмм то их суммарная вероятность составит р»0,0093, при этом Q=376/900»0,416. Непосредственный подсчет дает y(2)=524, y(3)=10416, y(4)=203587 и т.д. Последовательные приближения значения l имеют вид

19,8778, 19,5456, 19,6030.

Положив l=19,60, получаем при L=100

a»0,61, b»4,45×10^-17.

Среднее число знаков, на котором срабатывает критерий. Рассмотрим критерий запретных знаков, m=1. Пусть x – случайная величина, принимающая значения номера знака, на котором сработал критерий при проверке случайного текста, xÎ{1,2,…,L}. Событие x=к означает, что на первых к–1 местах в случайном тексте имеются незапретные знаки, а на к-ом месте впервые появился один из запретных знаков. Учитывая независимость знаков случайного текста, получим

Р(x=к)=(1– Q)^к-1Q, к<L.

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

Р(x=L)=(1– Q)^L-1.

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

Еx= + L(1– Q)^L-1.

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

1+х+…+х^L-1 и = ,

получаем Еx= » .