Характеристики сообщений

Сообщения, как бы сложны они не были, можно представить себе в виде последовательности знаков. Эти знаки берутся из заранее фиксированного набора, например, русского алфавита. Разные знаки могут встречаются в сообщениях с разной частотой. Поэтому количество информации, передаваемой разными знаками может быть разным. В том смысле, который предложил Шеннон, количество информации определяется средним числом возможных вопросов с ответами ДА и НЕТ для того, чтобы угадать следующий символ сообщения. Если буквы в тексте следуют независимо друг от друга, то среднее количество информации в сообщении приходящееся на один знак (энтропия или ненадёжность), равно:

где p_i - частота появления символа i, а n – количество символов в алфавите сообщения.

Отметим три особенности такого определения информации:

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

2. В нем предполагается независимость вероятности появления знаков от их предыстории.

3. Заранее известна знаковая система, в которой передается сообщение, то есть язык, способ кодирования.

В каких единицах выражается значение количества информации по Шеннону? Точнее всего ответ на этот вопрос дает теорема кодирования, утверждающая, что любое сообщение можно закодировать символами 0 и 1 так, что полученная длина сообщения будет сколь угодно близка сверху к Н. Эта теорема позволяет назвать и единицу информации - бит. Так как для русского текста, переданного лишь прописными буквами, Н=4.43 бит на букву, то это означает, что в принципе в русском алфавите можно было бы обойтись лишь 22 буквами или на 45% сократить длину файлов в формате ASCII. Таким образом, сообщения языка занимают места больше, чем это необходимо. Это явление называют избыточностью языка. Поэтому искажения отдельных символов сообщения зачастую не разрушают содержания, что случилось бы при отсутствии избыточности.

Избыточность можно вычислить следующим образом:

где H_max – максимальная энтропия текста сообщения, то есть текста, в котором все n символов алфавита случайны и равновероятны.

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

или

где n_k – количество символов ключа

Однако утверждение, что вероятность появления символа в связном тексте не зависит от предидущих символов, неверно и статистически, и лингвистически. Уже давно замечено, что обычно за согласной буквой следует гласная, а за гласной согласная. Поэтому, в конце XIX века, петербургский математик Марков предложил текст рассматривать как цепочку символов, где вероятность появления буквы зависит от предыдущей и только от нее. Таким образом, он стал рассматривать не вероятности p_j появления в сообщении знака i, а вероятности p(j|i) появления знака j при условии, что перед ним стоит знак i. Теория Марковских цепей оказалась чрезвычайно продуктивной для криптографии. Пока же достаточно отметить, что первое свое опробование она имела при анализе текстов "Евгения Онегина" самим Андреем Андреевичем Марковым. Объем информации в одном символе марковской цепи определяется следующей формулой:

В этом случае нет противоречия с требованием независимости знаков, так как знаком здесь считается не отдельный символ, а биграмма. Если вероятности биграмм представлены десятью классами от 0 до 9 в порядке возрастания и образуют по средним значениям геометрическую прогрессию. Справа в этой таблице даны вероятности встречи отдельных символов. Так, из нее следует, что биграмма АЙ встречается довольно часто (класс 7), а биграмма ЙА почти совсем не попадается (класс 0). Среднее количество информации, приходящееся на один символ, определяемое по этой таблице равно 3.5 бит, что эквивалентно примерно II буквам в русском алфавите или возможности сжатия текстов примерно на 57% при их оптимальном кодировании.

АБВГД ЕЖЗИЙ КЛМНО ПРСТУ ФХЦЧШ ПТЪЫЬ ЭЮЯ Промилле

А 27867 77747 77883 76782 66775 50000 679 79

Б 71101 62260 56357 27507 05410 55722 035 16

В 80504 80371 67568 46666 03013 00820 048 45

Г 60116 50060 45448 07006 00120 00000 004 18

Д 81634 81070 47178 46527 13334 00640 457 30

Е 55678 66647 78896 58893 36565 60011 559 83

Ж 60006 72170 50271 01213 00000 00020 002 9

3 84626 41161 55667 15006 00210 02620 046 17

И 66766 85777 76885 57881 57776 30100 679 69

й 00303 00000 36540 00660 00123 00000 008 11

к 81511 65271 27058 07667 00601 00000 007 34

л 84121 86180 44167 00336 30031 10680 786 50

м 75722 80170 44768 51316 10000 00730 068 31

н 90336 81190 60178 00576 52530 00850 467 67

о 28888 67768 78876 78883 25676 50015 259 108

п 70000 80470 36148 49456 20100 00453 044 28

р 91644 86080 52668 42667 35424 20740 167 48

с 64625 72070 78668 75696 35155 00561 387 56

т 82714 80080 64569 38846 00040 21780 158 55

у 34466 76533 65560 67771 55063 60000 748 29

ф 60000 50060 02206 04035 40000 00100 002 1

х 43300 40030 11056 05313 00200 01000 008 10

ц 50600 60070 00003 00004 00000 00500 005 3

ч 70100 80070 61062 01073 00013 00130 004 14

ш 50000 60070 33034 03034 00000 00040 005 10

щ 60000 70060 00020 02004 00000 00040 101 4

ъ 00000 40000 00000 00000 00000 00000 032 1

ы 14735 71517 55621 55560 07054 10100 018 18

ь 01000 30710 60471 00640 00016 10000 628 13

э 00400 10002 65210 20170 43000 00000 001 2

ю 05002 01204 10000 00370 00061 70010 307 5

я 01525 62502 23650 14470 04430 40000 649 20

78978 75883 86899 98987 76785 11218 260 138

Описанное свойство зависимости буквы в тексте от предыдущей, называется марковостью первого порядка, а независимость букв друг от друга марковостью нулевого порядка. Естественно, что можно рассматривать также и марковости высших порядков, например второго, когда буква зависит от двух предыдущих. Для того, чтобы оценить порядок марковости в связном тексте, проведено случайное моделирование, используя сначала вероятности отдельных букв, потом биграмм, триграмм и так далее. Примеры марковского синтеза текстов разных порядков марковости от 0 до 4 приведены в следующей таблице:

0 ПАВЛНТ И ОАБУТ ЕИИЕТК ЖМЕ КСВИДАИВ

1 МОЙ ОГЛЬ ТАМАНУ ЧТЕТОГАНЕ СТА СЛИНА

2 КРУЖБЫ И ОТЧАЕТОНЕИСТАК ПЕХ ЭТОГО 3

3 В ДЕПАРЫ ЧТО НАСТЯМИ РАСПРОИСХОДИН

4 ПОНЯЛ О ГЛУБОКОЙ СИСТЕМ И ДЕЛЕ ВОДЫ

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

символы в слога, слога в слова, слова в предложения, а предложения в сообщение.

Теперь рассмотрим одно приложение знаний свойств естественного текста сообщения для нужд криптографии. Требуется по отрезку текста решить, что он собой представляет, осмысленное сообщение или последовательность случайных символов. Ряд шифров приходится на ЭВМ вскрывать перебором ключей, а вручную просмотреть свыше тысячи фрагментов вдень просто не под силу, да и скорость мала. Поэтому нужно эту задачу реализовать на ЭВМ. Пусть предстоит перебрать примерно миллиард ключей на машине со скоростью тысяча ключей в секунду, на что уйдет около 10 дней. В этом случае мы рискуем впасть в две крайности. Если будем чрезмерно осторожны в оценках, то часть несмысловых текстов будет воспринята как сообщения и передана человеку. Эта ошибка обычно называется "ложная тревога" или ошибка первого рода. При количестве таких ошибок свыше 1000 в день человек устанет и может начать проверять тексты невнимательно. Значит, допускается не более одной ошибки такого рода на сто тысяч проверок. Далее, если подойти к проверке поверхностно, то можно пропустить смысловой текст и по окончании полного перебора его опять придется повторить. Чтобы не рисковать необходимостью повторения всей работы, ошибки второго рода или "пропуски сообщения" допустимы лишь одном случае из ста или тысячи.

Самый простой критерий, который приходит в голову, связан с использованием алфавита сообщения. Если учитывать, что в нем могут встретиться лишь знаки препинания, цифры, заглавные и малые русские буквы, то в тексте сообщения встретится не больше половины набора кодовой таблицы ASCII. Следовательно, встретив в тексте недопустимый символ можно уверенно говорить о том, что он несмысловой - ошибки второго рода почти исключены при нормально работающем канале связи. Для того, чтобы снизить вероятность "ложных тревог" до принятой выше величины, требуется, чтобы текст состоял не менее чем из двадцати трех символов. Дело усложняется, если используемый код букв не избыточен, как представление в ASCII русского текста, а содержит ровно столько символов, сколько их в алфавите. Тогда приходится вести оценку по вероятностям встречи символов. Чтобы обеспечить приемлемые вероятности ошибок первого и второго рода при оценке максимального правдоподобия, необходимо анализировать уже около сотни символов, а анализ вероятностей биграмм лишь несколько снижает эту величину. Таким образом, короткие сообщения при большой длине ключа вообще невозможно расшифровать однозначно, так как появляющиеся случайные тексты могут совпадать с осмысленными фразами. Аналогичную задачу приходится решать и при контроле качества шифрования. В этом случае, правда, вероятность ложной тревоги можно повысить, приняв ее не свыше одной тысячной, при той же самой вероятности пропуска сообщения. А это позволит ограничиться для проверки лишь 20-30 символами.