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

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

На практике наиболее часто используются следующие алфавиты:

· бинарный ‑ Z₂ = {0,1};

· шестнадцатеричный ‑ Z₁₆={0,1,…,A,B,C,D,E,F};

· 26 букв латинского алфавита ‑ Z₂₆={A,B,C,…,X,Y,Z};

· усеченное множество букв кириллицы ‑ Z₃₂={A,Б,B,Г,…};

· множество символов, входящих в стандартные коды ASCII ‑ Z₂₅₆.

В общем случае, если не оговорено иное, будем полагать, что алфавитом сообщений, подлежащих зашифрованию, является кольцо вычетов Z_m={0,1,…,m-1}, а величину m будем называть мощностью или модулем алфавита исходных текстов.

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

В частности, для достаточно большого объема литературного текста на русском языке наиболее часто встречающимися буквами оказываются {о,и}, среди наиболее часто встречающихся букв английского языка символы {e,t} (таблица 1).

Таблица 1

Относительные частоты встречаемости букв английского языка

(выборка 300 000 букв газетно-журнального текста)

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

С указанной целью используется ряд математических моделей открытых текстов, приведем примеры наиболее распространенных моделей, характеризующих их важные вероятностно-статистические свойства:

1. Открытый текст T={t₁,t₂,…} является последовательностью полиномиальных испытаний на множестве исходов Z_m={0,1,…,m-1} с вектором вероятностей встречаемости отдельных знаков , где:

Это одна из наиболее распространенных моделей открытого текста, которая позволяет решать задачи, связанные с классом поточных шифров (см. раздел «Классификация шифрсистем»).

Отметим, что применительно к схеме независимых испытаний используется характеристика неопределенности или мера информации, извлекаемой из эксперимента. Энтропией вероятностной схемы

называется величина H(ξ):

Согласно теореме кодирования любой исход вероятностной схемы может быть закодирован символами 0 и 1 так, что полученная длина кодового слова будет сколь угодно близка сверху к H(ξ). Итак, единицей количества информации логично считать один бит.

Нетрудно показать, что функция энтропии выпукла вверх и достигает своего максимума log₂m для равновероятного распределения (1/m,…,1/m).

С энтропией связана еще одна характеристика – избыточность языка R, которая вычисляется по формуле:

Понятие избыточности языка возникло в связи с тем, что максимальная информация, которую мог бы нести каждый символ сообщения, в равновероятной схеме равен H=log₂m. Для реальных текстов буква несет меньше информации, поэтому величина log₂m-H характеризует неиспользованные возможности в передаче текста, а отношение

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

В частности, очевидно, что вычеркивание из текста на русском языке всех гласных букв практически не снижает его информативности. Более того, в некоторых языках до 70-80 % знаков текста можно удалить без существенной потери смысла. Как следствие, для m-буквенного алфавита количество смысловых текстов (с заданными ограничениями на встречаемость букв) значительно меньше числа всевозможных наборов из N букв: m^N. Согласно теореме Мак-Миллана число открытых текстов для реального языка с величиной энтропии на один знак текста H для достаточно больших N оценивается величиной #N:

2. Другая модель ‑ открытый текст T={t₁,t₂,…,t_v,t_v+1,t_v+2,…,t_2v,…} является последовательностью независимых испытаний на декартовом произведении множеств:

которое называется множеством v-грамм. При этом, по крайней мере, для некоторых v-грамм (t_i1,t_i2,…,t_iv) имеет место:

Модель обычно используется при анализе шифров блочного типа.

3. Еще одна модель ‑ открытый текст T={t₁,t₂,…} является последовательностью испытаний, связанных в простую однородную цепь Маркова с начальным вектором распределения вероятностей и матрицей переходных вероятностей . Данная модель позволяет учитывать наличие зависимостей между знаками открытого текста, а потому используется для построения критериев, с помощью которых отбраковуются ложные варианты ключей.

Статистические свойства реальных открытых текстов являются исходными данными для проведения криптоаналитических атак и оценки практической стойкости шифросистем.