Частотные характеристики

Наиболее важная характеристика – избыточность открытого текста (подробно рассматривается в разделе надежности шифров).

Более простые:

· повторяемость букв, пар букв (биграмм), m -грамм;

· сочетаемость букв друг с другом (гласные-согласные и пр).

Такие характеристики устанавливаются на основе эмпирического анализа текстов достаточно большой длины.

Эксперимент по оценке вероятности появления в тексте фиксированных m -грамм (для небольших m).

Подсчет чисел вхождений каждой из n^m возможных биграмм в достаточно длинных открытых текстах T = t ₁ t ₂… t _l, составленных из букв алфавита { a ₁, a ₂,…, a _n}. При этом просматриваются подряд идущие m -граммы текста:

t ₁ t ₂… t_m, t ₂ t ₃… t_{m +1}, …, t _{1- m +1} t_{l - m +2}… t_l.

Если - число появлений m -граммы в тексте T, а L – общее число подсчитанных m -грамм, то при достаточно больших L:

При анализе сочетаемости букв друг с другом используют понятие условной вероятности (зависимость появления буквы в тексте от предыдущих букв).

Для условных вероятностей выполняются неравенства:

А. А. Марковым отмечена устойчивая закономерность чередования гласных и согласных. Зависимость появления букв текста вслед за несколькими предыдущими ощутима на глубину в 30 знаков, после чего практически отсутствует.

Вероятностная модель m -го приближения.

Пусть P ^{( m )}(A) – массив, состоящий из приближений для вероятностей p (b ₁ b ₂… b_m) появления m -грамм b ₁ b ₂… b _m в открытом тексте, m Î N, A = { a ₁,…, a_n }- алфавит открытого текста, b_i Î A, . Тогда источник "открытого текста" генерирует последовательность c ₁, c ₂,…, c_k, c_{k +1},… знаков алфавита A, в которой m -грамма c ₁ c ₂… c _k появляется с вероятностью

p (c ₁ c ₂… c_m)Î P ^{( m )}(A).