Вероятностно-статистические модели сообщений и их энтропийные свойства

     Содержание 

Введение . ....................................................5

1 Вероятностно-статистические характеристики сообщений .............6

2 Совершенная  секретность. .....................................16

3 Выводы   ...................................................22

Зкалючение  ..................................................23

Список  использованных источников ...............................24 
Реферат

     Курсовая  работа содержит 24 страницы формата  А4, 1 рисунок. 

     ВЕРОЯТНОСТЬ, ЧАСТОТА ВСТРЕЧАЕМОСТИ, ЭНТРОПИЯ, АБСОЛЮТНАЯ НОРМА ЯЗЫКА, ЭНТРОПИЯ ЯЗЫКА, БИТ, ИЗБЫТОЧНОСТЬ, ИЗБЫТОЧНОСТЬ ЯЗЫКА, СООБЩЕНИЕ, ОТКРЫТЫЙ ТЕКСТ, КРИПТОАНАЛИЗ, КРИПТОСТОЙКОСТЬ, КРИПТОСИСТЕМА, КРИПТОГРАММА, СИМВОЛ, СЛОВО, ИНФОРМАЦИЯ, СОВЕРШЕННАЯ СЕКРЕТНОСТЬ, РАССТОЯНИЕ УНИКАЛЬНОСТИ.

     В данной работе произведено исследование вопросов оценки эффективности криптосистем на основе вероятностно-статистических характеристик зашифрованных сообщений.

Результатом исследования являются выводы относительно требований к характеристикам сообщений.  
Введение 

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

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

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

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

     В естественных языках частоты встречаемости  различных букв сильно отличаются. Например, наиболее часто в текстах на русском языке встречаются три гласные буквы: О, И, Е. Следом идут буквы Т, Н, А, С. Отличаются по частотам и биграммы: среди которых чаще всего в русском языке встречаются ТС, ОН, ИН, НЕ, ВО, ОТ, СО. Эти характеристики могут быть разными для различных предметных областей. 

     Энтропия. Рассмотренные выше характеристики отражают лишь поверхностные свойства сообщений. Более глубокие свойства текстов изучаемые методами теории информации, разработанной K. Шенноном, это "количество информации", содержащейся в сообщении. Для понимания этого свойства необходимо ввести  меру количества информации. Оно связано c понятием энтропии, определяемой функцией от вероятностного распределения и характеризующей количество неопределенности или информации в случайном эксперименте. К. Шеннон предложил признать формулу:

     прирост информации = устраненной неопределенности,

выражающей  закон сохранения энтропии. На основании этой формулы неопределенность и информация должны измеряться одной и той же мерой.

      Энтропия  Н(ξ) определяется формулой:

                                           ,

где p_i – вероятность i-го символа, n – количество различных символов алфавита, присутствующих в сообщении. Единицу измерения энтропии вероятностной схемы предлагает так называемая теорема кодирования, утверждающая, что любой исход можно закодировать символами 0 и 1 так, что полученная длина кодового слова будет сколь угодно близка сверку к Н(ξ).

      На  основании этого единицей количества информации естественно считать  1 бит. Легко видеть, что если р₁ =1/п при всек i=1, п, то Н =1og₂ п. Кроме того, в общем случае имеет место неравенство Н(ξ) >= 0, причем Н(ξ)= = 0 в том и только в том случае, когда р_i =1 для некоторого i и р_j = 0 для всех j≠i.

      Мерой среднего количества информации, приходящейся на одну букву открытого текста языка L (рассматриваемого как источник случайнык текстов), служит величина Н_L , называемая энтроnией языка L. В общем случае следует взять энтропию вероятностной скемы на r-граммах, деленную на r. Соответствующие вычисления для английского языка дают: Н₂/2 ≈ 3,56, Н₃/3 ≈ 3,3. Исследования показывают, что с ростом r отношение Н_r/r стремится к некоторому пределу. Этот предел определяется как энтропия языка Н_L.

 
 

При этом формула

 

определяет  избыточность языка R_L .

     Термин "избыточность языка" возник в  связи с тем, что максимальная информация, которую в принципе могла  бы нести каждая буква сообщения, равна Н₀ =1og_a n , где п - число букв в алфавите. Так было бы в случае, если бы буквы сообщения появлялись случайно и равновероятно. В то же время средняя энтропия буквы в открытом тексте значительно меньше n, следовательно, буква несет меньше информации, чем log_a n. Величина log_a n - - Н_L характеризует, таким образом, неиспользованные возможности в передаче информации с помощью текста, а отношение

       

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

     Клод  Шеннон предложил оригинальный метод  оценивания отношения Н_r /r для осмысленных текстов с позиции меры неопределенности опыта, состоящего в угадывании r-й буквы текста, при условии, что предшествующие его буквы известны. Эксперимент по угадыванию r-й буквы текста легко может быть поставлен. Для этого достаточно выбрать осмысленный отрезок открытого текста длины r-1 и предложить кому-либо угадать следующую букву. Подобный опыт может быть повторен многократно, при этом сложность угадывания r-й буквы может быть оценена с помощью среднего значения числа попыток F_r , требующихся для нахождения правильного ответа. Ясно, что величины F_r для разных значений r являются определенными характеристиками статистической структуры языка. Очевидно, что среднее число попыток F_r с ростом r может лишь уменьшаться. Прекращение этого уменьшения будет свидетельствовать о том, что соответствующие опыты имеют одинаковую неопределенность, то есть что отвечающая им величина H_r /r практически уже достигла своего предельного значения Н_L .

     Исходя  из зтих рассуждений, К. Шеннон произвел ряд подобны[ экспериментов, в которых  r принимало значения 1,15 и 100. При этом он обнаружил, что отгадывание сотой буквы по 99 предшествующим заметно более просто, чем угадывание 15-й буквы по 14 предыдущим. Опыты показали, что с ростом r величина H_r /r убывает вплоть до r ≈ 30, а при дальнеишем росте r она уже практически не меняется. Согласно исследованиям Б. Б. Пиотровского, имеют место следующие приближения величины Н_L , которые приведены в таблице 1:

     Таблица 1 – Энтропия и избыточность языков

     

     Из  приведенной таблицы видно, что  языки имеют весьма большую избыточность, Что означает, например, избыточность, составляющая 75%? Это не означает буквально то, что любые 3 из 4 букв текста можно вычеркнуть без потери информации. Более точно это означает, что при оптимальном кодировании текста (при использовании, например, кода Хаффмена, кода Фано или другого оптимального кода его можно сжать до четверти длины без потери информации.

      Сделаем замечание  о другом возможном подходе к  определению величины Н_L для литературных текстов. А. Н. Колмогоров, не согласившись с тем, что теоретико-информационные рассмотрения игнорируют вопрос о смысловом содержании литературных текстов, предложил так называемый комбинаторный подход. Суть такого подхода к определению энтропии текста состоит в следующем. Шенноновскую энтропию Н_L , приходящуюся на букву текста, можно определить тем условием, что для n-буквенного алфавита число текстов длины L, удовлетворяющих заданным статистическим ограничениям, равно (при достаточно больших L) не 
 

как это  было бы, если мы имели бы право брать  любые наборы из L букв, а всего лишь

 

     По  сути, это и есть асимптотика числа осмысленных открытьтх текстов длины L для данного языка. Исходя из этого, можно определить энтропию Н_L языка формулой:

       
 

не зависящей  ни от каких теоретико-вероятностных  представлений. Величину М(L) можно оценивать  с помощью подсчета числа возможных продолжений литературного текста.

     Абсолютная  норма языка равна максимальному  количеству битов, которое может  быть передано каждым символом при  условии, что все последовательности символов равновероятны. Если в языке L символов, то абсолютная норма равна:

     R_L = log₂ L

     Это максимум энтропии отдельных символов. Для английского языка с 26 буквами  абсолютная норма равна log₂ 26, или около 4.7 бит/буква.

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

     В реальном криптоанализе у криптоаналитика  есть некоторая вероятностная информация о P еще до начала работы. Он, скорее всего, знает язык открытого текста. Этот язык обладает определенной, связанной  с ним избыточностью. Если это сообщения для Боба, оно, возможно, начинается словами "Дорогой Боб". Определенно, "Дорогой Боб" намного вероятнее, чем "e8T&.g [,m". Целью криптоаналитика является изменение вероятностей, связанных с каждым возможным открытым текстом. В конце концов, из груды возможных открытых текстов будет выбран один конкретный (или, по крайней мере, весьма вероятный).

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

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

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

     Энтропия  криптосистемы является мерой размера  пространства ключей, K. Она приблизительно равна логарифму числа ключей по основанию 2:

     H(К) = log₂ K

     Энтропия  криптосистемы с 64-битовым ключом равна 64 битам, энтропия криптосистемы с 56-битовым ключом равна 56 битам. В общем случае чем больше энтропия, тем тяжелее взломать криптосистему. 

     Расстояние  единственности. Попытки определения  истинного ключа шифра по данной криптограмме путем ее расшифрования на всех возможных ключах могут привести к тому, что критерий на открытый текст примет несколько претендентов за открытый текст. Это объясняется не только недостатками критерия. При небольших длинах криптограмм результат ее расшифрования может дать несколько осмысленных текстов. Например, криптограмму WNAJW, полученную при использовании сдвигового шифра для английского языка, порождают два открытых текста RIVER и ARENA, отвечающик ключам F(=5) и W(=22). При этом один из ключей является истинным, а другой -ложным. Аналогичная ситуация может иметь место для любого другого шифра.