Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Пусть источник S порождает сообщения в виде последовательностей, состоящих из к символов. Иначе говоря, сообщение представляет собой слово, состоящее из к символов.
OijG^ ... aik для 1 ^ гк ^ п.
Пусть Lfc обозначает минимальное ожидаемое количество бит, которое требуется для записи /с-символьного слова, порожденного источником S. Для оценки величины Lk используется следующая теорема.
Теорема 3.2 (Шеннон [262, 263]).
lim ^ = H{S).
к—'СО к
Доказательство. При всех к > 0 выполняется следующая двусторонняя оценка.
kH(S) ^Lk^ fcH(S) + 1.
Поделив эти неравенства на число к и перейдя к пределу, получаем искомую оценку. ?
Иначе говоря, минимальное среднее количество бит, необходимое для записи сообщений, порождаемых источником 5, равно H(S).
3.7.1 Свойства энтропии
Функция H(S) принимает минимальное значение, равное нулю, если источник S порождает некий символ, например а\, с вероятностью 1. Это следует из следующего выражения.
H(S) = Probla1]log2(j^l_I)=log2l = 0.
Иначе говоря, если нам известно, что источник S порождает один-единственный символ а\, зачем нам тратить бит на его запись?
Функция H[S) достигает максимума, равного log2n, если источник 5 порождает каждый из п символов с одинаковой вероятностью, равной ^, т.е. источник
Глава 3. Теория вероятностей и теория информации
113
S является случайным генератором равномерного распределения. Это следует из такого выражения.
1 п
Н (S) = ~У~] log2 п = log2 п.
i=i
Этот факт можно интерпретировать следующим образом: поскольку источник S может порождать один из п символов с одинаковой вероятностью, для записи каждого из этих п чисел следует зарезервировать log2 п бит.
Функцию H(S) можно рассматривать как объем неопределенности, или информации, содержащейся в каждом сообщении, порожденном источником S.
Пример 3.10. Рассмотрим протокол 1.1 ("Подбрасывание монеты по телефону"). Независимо от его реализации — с помощью телефона или компьютерной сети, — этот протокол сводится к жеребьевке с помощью случайного бита. Алиса извлекает большое целое число х G {/N, затем передает Бобу значение однонаправленной функции f(x) и в заключение раскрывает Бобу значение х после его попытки угадать случайное число. С точки зрения Боба, число х не должно рассматриваться как новая информация, поскольку, даже еще не получив значение /(ж), он знает, что х — натуральное число. Боб использует только интересующую его часть сообщения Алисы: критерием жеребьевки является четность числа х. Итак, мы получаем следующее выражение.
Н (Алиса) = РгоЫж — нечетное11ое9 ( ——---Л +
4 ' 1 J ЪА \Prob[х -нечетное]/
+ РгоЫж — четное] log2 (— —--Л =
i ^ Prob [х - четное] /
= ilog22 + ^log22 = l.
Иначе говоря, для записи сообщений Алисы достаточно одного бита, хотя она генерирует большое целое число. ?
Повторив протокол 1.1 п раз, Алиса и Боб получат строку, состоящую из п бит: если Боб угадал правильно, в строку записывается единица, если нет — нуль. В этой ситуации и Алиса, и Боб рассматриваются как источники случайных однобитовых протокольных сообщений. Строка битов признается обеими сторонами случайной, поскольку и Алиса, и Боб порождают случайные сообщения и знают, что противоположная сторона не может их контролировать.
3.8 Избыточность естественных языков
Пусть источник S(L) порождает слова естественного языка L. Допустим, что в среднем каждое слово в языке L состоит из к символов. По теореме Шеннона
114
Часть II. Математические основы
(теорема 3.2) величина H(S(L)) представляет собой минимальное среднее число бит в сообщении, порожденном источником S(L) (напомним, что сообщение источника S представляет собой слово, состоящее из к символов). Следовательно, величина
к
является минимальным средним количеством битов, необходимых для записи символов языка L. Величина r(L) называется энтропией языка L (rate of language L). Пусть L — английский язык. Шеннон показал, что энтропия английского языка г (English) лежит в интервале от 1,0 до 1,5 бит/буква [265].
Пусть Е = {а, 6,..., z}. Тогда r(E) = log2 26 « 4,7 бит/буква. Величина г(Е) называется абсолютной энтропией языка (absolute rate of language) с алфавитом Е. Сравнивая величины г(Е) и r(EngIish), можно убедиться, что фактическая энтропия английского языка значительно меньше абсолютной.
Избыточностью языка L (redundancy of language) с алфавитом Е называется величина
r(E) — r{L) (бит/символ).
Учитывая консервативную оценку r(English) = 1,5, получаем, что избыточность английского языка равна 4,7 — 1,5 = 3,2 бит/буква. В процентном выражении избыточность равна 3,2/4,7 и 68%. Иными словами, около 68% букв в английском слове излишни. Это означает, что статью, написанную на английском языке, можно сократить до 32% от первоначального объема без потери информации.
Избыточность естественного языка возникает вследствие наличия некоторых хорошо известных и повторяющихся форм. Например, в английском языке за буквой д практически всегда следует буква и. Кроме того, часто встречаются артикль "the" и окончания слов "ing" и "ed". Избыточность естественных языков представляет собой весьма ценное свойство для криптоанализа (cryptanalysis), позволяющее восстанавливать исходные сообщения или определять криптографический ключ по зашифрованному тексту.
