Кpиптогpафия от папиpуса до компьютеpа


Характеристики сообщений - часть 3


H= См. Pi(См. Pij*Ld(Pij))

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

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

0     ПАВЛНТ И ОАБУТ ЕИИЕТК ЖМЕ КСВИДАИВ
     1     МОЙ ОГЛЬ ТАМАНУ ЧТЕТОГАНЕ СТА СЛИНА
     2     КРУЖБЫ И ОТЧАЕТОНЕИСТАК ПЕХ ЭТОГО 3
     3     В ДЕПАРЫ ЧТО НАСТЯМИ РАСПРОИСХОДИН
     4     ПОНЯЛ О ГЛУБОКОЙ СИСТЕМ И ДЕЛЕ ВОДЫ

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




- Начало -  - Назад -  - Вперед -



Книжный магазин