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

Рассмотрим шифр, заданный вероятностной моделью.

в которой X - множество текстовых сообщений длины L естественного языка, характеризующегося энтропией Я, с алфавитом из п букв, который является также алфавитом и шифртекста:

Полагаем также, что при шифровании сохраняется длина сообщения. Таким образом, X, Y С A^L. Для у е A^L через К (у) обозначим множество пар (х, к), для каждой из которых шифртекст у является результатом зашифрования осмысленного текста х € X на ключе к, т. е.

Отметим, что в множестве К (у) одна пара (х, к) соответствует истинному ключу к (а значит, и истинному открытому тексту х), у каждой из оставшихся К (у) — 1 пар по крайней мере одна из частей — ложная.

Обозначим через Ml среднее значение мощности множества К (у) по всем возможным шифртекстам:

Определение 4.4. Расстоянием единственности для шифра SB называется натуральное число L, при котором среднее значение Mi мощности множества К (у) равно единице.

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

Утверждение 4.5. Величина Mi равна единице для шифра SB в том и только том случае, если

Доказательство. Достаточность условий вытекает из (4.11) с учетом того, что при | У |=| X 11 К| мощность множества К (у) равна единице.

Пусть теперь | Y |<| X || К |. Тогда

Отсюда.

Оценивая число смысловых открытых текстов длины L величиной 2^НЬ, получим оценку для расстояния единственности.

Минимальное значение L, удовлетворяющее данному неравенству.

и принимается за расстояние единственности (здесь В — есть избыточность языка).

Сделаем следующие замечания.

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

даже в рамках одного языка. Как известно, энтропия на знак есть предел отношения.

где #_г — энтропия для r-граммной модели открытого текста. Поэтому в наших расчетах по формуле (4.12) при использовании r-граммной модели полагаем II = В частности, для английского языка.

2. При использовании формулы (4.12) для оценки расстояния единственности блочных шифров следует использовать смысловые открытые тексты, длина которых, измеряемая числом бит в их двоичном представлении, кратна длине двоичных блоков, обрабатываемых блочным шифром. При этом полученное расстояние единственности измеряется числом алфавитных знаков в сообщении.

Пример 4.1. Рассмотрим шифр простой замены с параметрами французского разговорного языка п = 26, | К — 26!, Н = 1.50. Тогда

то есть расстояние единственности для данного шифра составляет 28 символов.