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

Пример 5.1

Рассмотрим подбрасывание монеты. Пусть и,. Энтропия задается формулой (5.4).

Очевидно, что значение подтверждается тем фактом, что для представления результата такого эксперимента с правильной (обычной) монетой необходим один бит. Например,, a.

Рассмотрим неправильную монету, у которой, а. Тогда энтропия эксперимента по подбрасыванию неправильной монеты. Можно ожидать, что в среднем для представления результата эксперимента с неправильной монетой, для которой, окажется достаточно. Это утверждение верно в том смысле, что можно сколь угодно приблизиться к числу. Трюк состоит в том, что результат большого числа бросаний представляется единственной двоичной строкой. Например, результат двух бросаний можно закодировать, используя неравномерный (чем больше вероятность, тем меньше кодовое слово) префиксный код (ни одна кодовая комбинация не является началом другой, более длинной), следующим образом:

выпало	вероятность	представление

Математическое ожидание длины такого представления равно

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

Существует, однако, проблема однозначного декодирования, состоящая в том, как получатель по длинной строке из нулей и единиц может определить, сколько экспериментов проводилось (сколько букв в символе) и какой был результат у каждого из них. Нетрудно проверить, что любая последовательность, состоящая из подпоследовательностей 111, 110, 10 и 0, однозначно разбивается на такие блоки, поскольку использовался префиксный код ‑ ни одна кодовая комбинация не является началом другой, более длинной.

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

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

С другой стороны, энтропию 1-грамм легко вычислить по вероятностям, приведенным в табл. 1.1. Получится 4,15 бита на букву.

Таблица 1.1. Распределение вероятностей 1-грамм в английском языке.

Подобные вычисления были проведены для биграмм и триграмм (см. [4] приложение F). Получены следующие величины:

По некоторым тестам асимптотическое значение величины при. меньше, чем 1.5 бита па букву!

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

Число является мерой избыточности, приходящейся на одну букву текста.

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

.

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

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

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

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

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

.

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

т.е. в ситуации, когда избыточность открытого текста из букв () удовлетворяет условию

то лишь один ключ приводит к осмысленному дешифрованию шифртекста.

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

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