Взаємна інформація

Определение 5.2

Пусть в криптосистеме используются ключи из ключевого пространства , а открытые тексты порождаются источником . Рассмотрим атаку против криптосистемы на основе известного шифртекста. Расстояние единственности этой криптосистемы определяется как

где — энтропия ключа, a — избыточность открытого текста.

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

Пример 5.2 (часть 2)

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

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

Процитируем Фридмана [5]: "практически каждый пример из 25 или более букв, представляющий собой результат действия одноалфавитной подстановки на осмысленный английский текст, может быть легко расшифрован". Отметим, что числа 25 и 28 прекрасно согласуются.

Часто одна случайная величина содержит информацию о другой. В криптосистемах открытый текст и шифртекст связаны посредством ключа. Дадим формальное определение (в теоретико-информационном смысле этого слова) абсолютно безопасной криптосистемы.

Пусть и — случайные величины, определенные на множествах и соответственно. Вероятность или сокращенно

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

Выполняется соотношение

(5.5)

Неопределенность величины при условии называется условной частной энтропией иопределяется аналогично функции энтропии равенством

(5.6)

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

Условной энтропией величины по величине называется усредненное значение неопределенности по всем . Т.е.

Пусть совместная энтропия определяется аналогично функции энтропии от одной переменной.

Теорема 5.1 (цепное правило)

Доказательство. Используя соотношения (5.5) и (5.7), получим

Второе равенство следует из перестановочности аргументов в .

Иначе говоря, приведенная выше теорема утверждает, что неопределенность совместного распределения величин и равна неопределенности плюс неопределенность по .