Понятие криптологии

выражающее  этот порядок, будет равно уменьшению энтропии  системы  по

сравнению   с   максимально     возможной     величиной     энтропии,

соответствующей  отсутствию  упорядоченности  и  наиболее  хаотичному

состоянию систем.

 

Методы  исчисления  информации,  предложенные   Шенноном,   позволяют выявить  соотношение  количества  предсказуемой  (то  есть  формируемой   по определенным правилам) информации и количества той  неожиданной  информации, которую нельзя заранее предсказать. Содержащуюся в правилах информацию Шеннон определил  как  избыточную, потому что знание правил построения сообщений позволяет предсказывать появление букв (или других символов) раньше, чем они  будут  сообщены по линии связи. Таким  способом  удается  в  той  или   иной   степени   «разгрузить» предназначенный для передачи сообщений канал.  Проведенный  Шенноном  анализ английских текстов показал, что содержащаяся  в  них  избыточная  информация составляет около 80% от общего количества информации,  которое  заключает  в себе письменный текст. Остальные 20% -  это та  самая энтропия,  благодаря которой текст может служить источником непредсказуемой энергии. Если бы текстовые, устные или зрительные (в частности  телевизионные) сообщения были полностью лишены энтропии, они не  приносили  бы  получателям сообщений никаких новостей. Если  бы  письменный  текст  строился  только  на  основании  заранее сформулированных правил  ,  то,  установив  эти  правила  по  тексту  первой страницы,  можно  было  бы  заранее  предсказать,  что  будет  написано   на

страницах 50, 265, 521 и т.д.

Надежность  криптосистем

Шеннон определил точную математическую модель надежности криптосистемы. Цель криптоанализа – определить ключ K, текст P или оба. Тем не менее, интересна и некоторая вероятностная информация о P – текст ли это или аудио и т.п.

В обычном мире, криптоаналитик имеет некоторую вероятностную  информацию о P до начала (язык => избыточность). Цель криптоанализа – путем анализа изменять вероятности, связанные в каждым возможным текстом. Т.о. рано или поздно один из текстов станет заведомо верным (или достаточно вероятным).

Существует криптосистема  с совершенной секретностью (perfect secret), т.е. такая криптосистема, в которой шифртекст не дает никакой информации об исходном тексте (кроме, может быть, длины) – это одноразовый блокнот.

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

Энтропия криптосистемы  – это мера пространства ключей: H(K) = log₂ (число ключей).

Чем больше энтропия, тем надежнее криптосистема.

Информационная  энтропия

 

Энтропия (информационная) — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Так, возьмём, например последовательность символов, составляющих какое-либо предложение на русском  языке. Каждый символ появляется с разной частотой, следовательно неопределённость появления для некоторых символов больше, чем для других. Если же учесть, что некоторые сочетания символов встречаются очень редко, то неопределённость ещё более уменьшается (в этом случае говорят об энтропии n-ого порядка, см. Условная энтропия).

Условная  энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегде следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной  энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (т.е. вероятности двухбуквенных сочетаний):

где i — это  состояние, зависящее от предшествующего  символа, и pi(j) — это вероятность j, при условии, что i был предыдущим символом.

Так, для русского алфавита без буквы «ё»:

Энтропия  и неопределенность

Определение: Количество информации сообщения – это минимальное  количество битов, требуемое для  записи всех возможных значений сообщения. 

Например: поле, содержащее день недели, содержит не более чем 3 бита информации (т.к. данная информация может быть упакована в 3 бита, причем одно значение не будет использоваться). Если записывать эту информацию строкой, то потребуется больше памяти, но информации не прибавится. Точно так же поле «пол» БД содержит только 1 бит информации. 

Формально, количество информации сообщения М измеряется энтропией  сообщения, обозначаемой H(M). В целом, энтропия сообщения равна log₂ n, где n – количество возможных значений.

Энтропия сообщения  также измеряет его неопределенность, т.е. количество битов текста, необходимое для восстановления зашифрованного текста. Например, если блок шифра = «Q*56HM», а значение может быть «MALE» или «FEMALE», то неопределенность сообщения равна 1 (криптоаналитику достаточно выяснить один нужный бит для восстановления сообщения).

Если неопределенность исходного текста слишком мала, то криптосистема с открытым ключом уязвима к ciphertext-only attack. Например, если c = E(P), где P – один из n различных  возможных текстов, то криптоаналитику  требуется только зашифровать все n возможных текстов и сравнить результаты с c (т.к. ключ зашифровки - открытый). Секретный ключ так не найти, но P можно найти. Симметричные криптосистемы не подвержены такой опасности (нельзя производить пробные шифрации без ключа).

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

 

 

 

 

Заключение

Все сказанное имеет  великую теоретическую ценность, но на практике используется редко. Расстояние единственности гарантирует ненадежность, если оно слишком мало, но не гарантирует надежности, если оно велико. Очень мало криптоалгоритмов действительно не поддаются анализу.

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

К сожалению, множество работ остается засекреченным.

 

 

 

 

 

Литература

 

1. В.В. Лидовский. Теория Информации - М.: Спутник +, 2004. -111 с.
2. K.Э. Шеннон. Теория связи в секретных системах (В кн.: Шеннон К.Э. Работы по теории информации и кибернетике).- М.: ИЛ, 1963.
3. Нечаев В.И.Элементы криптографии. Основы теории защиты информации. - М: Высшая школа -1990г., 112с.