Теорема 5.4. Безумовно безпечні системи

Безумовно безпечні системи

Пример 5.3

Двоичный симметричный канал передачи информации может быть описан следующим образом. Источник посылает значение величины с вероятностью или тоже с вероятностью. Приемник получает значение величины с вероятностью или же с вероятностью (интерпретируется как вероятность ошибки, которую вносит источник шума). Это означает, что, и что вероятность того, что источник посылал при получении равно

Аналогично,. Кроме того, и Таким образом, для двоичного симметричного канала по формуле
𝐼(𝑋;𝑌)=−(5.8) получаем,

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

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

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

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

а шифртекст — последовательность случайных величин

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

(5.9)

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

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

Доказательство теоремы 5.4. Из равенства (5.9) и цепного правила (теорему 5.1
можно применять и к условной энтропии) следует, что

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

Из этого следует, что

и по теореме 5.3 получаем

Дата добавления: 2013-12-12