Марковская модель. 
Криптографические методы защиты информации

В данной модели открытый текст <�ц, аг,…, a_s, а, е Л, является реализацией простой однородной цепи Маркова с п состояниями.

Тогда вероятность появления текста а, 02,…, а., вычисляется по формуле

где р (а) — вероятность первого знака текста, 7r (a/,|a/₍_i) вероятность того, что на месте с номером h будет знак а/, при условии, что на предыдущем месте находится знак a/,_i.

Таким образом, данная модель задается начальным вектором вероятностей р (а) = (р (а), а? Л) и матрицей переходных вероятностей.

Как и ранее, оценки для элементов матрицы переходных вероятностей, а также для начального вектора, получаются экспериментально.

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

Критерии на открытый текст

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

Необходимо различить две простые гипотезы:

• • Щ — вектор а является открытым текстом (в заданной модели),
• • Н — вектор а является случайной равновероятной последовательностью знаков алфавита Л.

Важнейшими параметрами любого статистического критерия являются вероятности ошибок первого и второго рода:

• • а = P (#i|#o) — открытый текст принят за случайный набор знаков;
• • 0 = P (HoHi) — случайный набор знаков принят за открытый текст.

Важными параметрами также являются:

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

Рассмотрим критерий на основе запретных биграмм. Пусть среди п² всевозможных биграмм имеется т запретных. При этом открытым текстом считается последовательность четной длины s — 21, состоящая из t биграмм, среди которых нет запретных. В таком случае ошибка первого рода будет равна нулю (а = 0), a ошибка второго рода

Для приближенной оценки ошибки второго рода можно воспользоваться формулой.

и, А существенно меньше единицы.

Средняя длина случайного текста, на которой срабатывает критерий, вычисляется по формуле.

Если критерий применять независимо (т.е. к различным участкам текста) г раз, то ошибка второго рода будет равна.

Отсюда, для приближенной оценки длины материала N = tr (биграмм), при котором происходит отсев всех ложных ключей, можно использовать равенство.

следовательно,.

где К — мощность ключевого множества.

Пример 2.5. Как следует из экспериментальных таблиц частот встречаемости биграмм, в русском языке имеется т = 382 запретные биграммы применительно к алфавиту из 31 знака (при «Е».

= «Ё» и «Ъ» = «Ь»). Тогда справедливо выполнение следующих равенств.

В английском языке имеется тп = 250 запретных биграмм применительно к алфавит}' из 26 знаков (в частности, запретны все биграммы, начинающиеся с буквы «q», за исключением биграммы «qu», встречающейся с вероятностью 10^_3). Тогда.