Скляр Б. Цифровая связь (2003) (1151859), страница 214
Текст из файла (страница 214)
Пример 14.3. Энтропия и неопределенность Рассмотрим выборочное множество сообщений, состоящее из восьми равновероятных сообщений (Х) =Хь Хь „Хь а) Найдите энтропию, связанную е сообщением из множества (Х). б) Дано другое множество равновероятных сообщений ( У) = У„У,. Пусть появление каждого сообщения У сужает возможный выбор Х следующим образом. При наличии У, возможны только Хь Хь Хэ или Хч При наличии У, возможны только Х,, Хм Х, илн Хз Найдите неопределенность сообщения Х, обусловленную сообщением У. Рещение а) Р(Х) = з Н(Х) = 8 ()з1ойз 8] = 3 бит/сообщение б) Р(У) =з'. Для кажлого У, Р(Х1У)=24 для четырех сообщений из множества [Х) и Р(Х(У) = 0 лля оставшихся четырех. Используя уравнение (14.6), получим следующее. Н(Х1 У) = 2((2з)4(4~- 1о8 з 4)] = 2 бит/сообщение Вилис, что знание У сводит неопределенность Х с 3 бвт/сообщение до 2 бит/сообщение.
14.2.3. Интенсивность и избыточность языка Н(Х) Г= —, Ф (14.7) Здесь Н(Х) — энтропия сообщения, или число битов в оптимальна закодированном сообщении. Для письменного английского языка при больших Н оценки г дают значения ятт Истинная интенсивность языка определяется как среднее число информационных битов, содержащихся в каждом символе, и для сообщения длиной Н выражается слелуюшим образом: между 1,0 и 1,5 бит/символ [4]. Абсолютная интенсивность или максимальная энтропия языка определяется как максимальное число информационных битов, содержащихся в каждом символе, в предпояожении, что все возможные последовательности символов одинаково вероятны. Абсолютная интенсивность задается следующим образом: «'= !обз Ь.
(14.8) Здесь 1. — число знаков в языке. Для английскою алфавита «'= !ойз 26 = 4,7 бит/символ. Истинная интенсивность английского языка, конечно, гораздо меньше его абсолютной интенсивности, поскольку, как и бояьшинство языков, английский очень избыточен и структурирован. Нзбыточнос«ль языка определяется через его истинную и абсолютную интенсивности. Р=«'-« (14.9) Для английского языка, где «'=4,7 бит/символ и «= 1,5 бит/символ, Р = 3,2, а отно- шение Р/«'= 0,68 — это мера избыточности языка. 14.2.4. Расстояние единственности и идеальная секретность число осмысленных сообщений 2™ число бессмысленных сообщений 2 — 2', (14.10) (14.11) где « — истинная интенсивность языка, а априорные вероятности классов сообщений описываются следующими выражениями.
919 Ранее утверждалось, что если допускаются сообщения неограниченной длины, то совершенная секретность требует бесконечного количества ключей. При конечном размере ключа его неопределенность Н(1(]С) обычно приближается к нулю, откуда следует, что ключ может быль определен единственным образом, а система шифрования может быть взломана Расстояние единственносяш (шис!гу дйгапсе) определяется как наименьшая длина шифрованного текста Ф, при которой неопределенность ключа Н((г]С) близка к нулю.
Следовательно, расстояние единственности — это количеспю шифрованного текста, необходимое для того, чтобы однозначно определить ключ и таким образом взломать систему шифрования. Шеннон (Язеппоп) [5] описал систему с идеальной секретностью как систему, в которой Н0(]С) не стремится к нулю, если количеспю шифрованного текста стремится к бесконечности. Иными словами, ключ не может быть определен, независимо от того, сколько шифрованного текста перехвачено. Термин "идеальная секретность" описывает систему, которая не достигает совершенной секретности, но, тем не менее, не поддается взлому (безусловно защищенная система), поскольку она не дает достаточно информации для опредеяения ключа.
Большинство систем шифрования слишком сложны для определения вероятностей, необходимых для вычисления расстояния единственности. В то же время расстояние единственности иногда можно аппроксимировать, что было показано Шенноном [5] и Хэллманом (Не))гпап) [6]. Следуя Хэллману, предположим, что каждый открытый текст и шифрованное сообщение получены с помощью конечного алфавита из б символов.
Таким образом, всего существует 2" возможных сообщений длиной Н, где «' — абсолютная интенсивность языка. Всю обяасть сообщений можно разделить на два класса — осмысленные сообщения М, и бессмысленные сообщения Мь Тогда имеем Р(М ) = —, = 2 М~ — осмысленное 1 2'" (14.12) Р(Мг) = 0 Мг — бессмысленное Предположим, что существует 2мо возможных ключа (размер алфавита ключей), где О(К) — энтропия ключа (количеспю бит в ключе). Предположим, что все ключи равновероятны. (14.13) Р(К) = — =2 2 (14.14) возникает всегда, когда шифрование с помощью другого ключа К может давать С, из того же сообщения М, или из некоторого другого сообщения М,.
С, =Ек(М,)=Ек,(М|)=ЕК (Мз) (14.15) Криптоанапнтик, перехвативший С, не сможет выбрать верный ключ и, следовательно, не сможет взломать систему шифрования. Мы не рассматриваем операции дешифрования, которые дают бессмысленные сообщения, так как они могут легко отбрасываться.
Для каждого верного решения конкретного шифрованного текста существует 2гхо ' неверных ключа, каждый из которых имеет ту же вероятность Р(Г) получения неверного решения. Так как все осмысленные открытые сообщения предполагаются равновероятными, вероятность неверного решения равна вероятности получения осмысленного сообщения. 2" Р(Р) = — =2 =2 2" (14.16) Здесь О= К вЂ” г — избыточность языка. Тогда ожидаемое число неверных решений Р' равно следующему: ~~ и<к1 ф,(Р) [2н(к) 1~2-он 2н1к> — он (14.17) Поскольку Р быстро убывает с увеличением Ф, то )о8 Р = н(К) — 11)у = о (14.18) является точкой, где число неверных решений достаточно мало; так по шифр может быть взломан. Следовательно, получаемое расстояние единственности описывается следующим выражением: Н(К) 0 (14.19) 919 1ао гъ а Ф Определение расстояния единственности основано на модели случайного кгифра, которая утверждает, что лля каждого ключа К и шифрованного текста С операция дешифрования Вк(С) дает независимую случайную переменную, распределенную по всем возможным 2'" сообщениям (как осмысленным, так и бессмысленным).
Следовательно, для данных К и С операция Рк(С) может с равной вероятностью давать любое из открытых сообщений. При данном шифровании, описываемом как С, =Ек (М,), неверное решение Р Из уравнения (14.17) следует, что если Н(К) значительно больше РН, то будет множество осмысленных расшифровок, и, следовательно, существует малая вероятность выделения криптоаналитиком верного сообщения из возможных осмысленных. Приблизительно, РН вЂ” это число уравнений для ключа, а Н(К) — число неизвестных. Если число уравнений меньше числа неизвестных битов ключа, единственное решение невозможно; говорят, что система на поддается взлому. Если число уравнений больше числа неизвестных, возможно единственное решение, н система не может больше считаться не поддающейся взлому (хотя она все еще может относиться к защищенным по вычислениям).
Стоит отметить, что доминирование бессмысленных дешифровок позволяет взламывать криптограммы. Уравнение (14.19) показывает значение использования методов сэгатия данных до шифрования. Сжатие данных устраняет избыточность языка, таким образом увеличивая расстояние единственности. Совершенное сжатие данных даст Р = 0 и Ф = для любого размера ключа.
Пример 14.4. Расстояние единственности Вычислите расстояние единственности лля системы шифрования, испальзуюшей письменный английский язык, ключ которой задается последовательностью Ь, йь ..., Й~ь где кюедое Й,— случайное целее из интервала (1, 25), которое определяет номер сдвига (рис. 14.3) для (-го символа. Предположим, по все возможные ключевые последовательности равновероятны. Решение Существует (25)" возможных равновероятных ключевых последовательностей. Следовательно, используя равенства (14.5),(!4.8) и (!4.!9), получаем следующее: энтропия ключю Н(К) = 1ойз (25)зе = 135 бит, абсолютная интенсивность английского языка: К = !оде 26 = 4,7 бит/символ, предполагаемая истинная интенсивность английского языка: г = 1,5 бит)символ, избыточность: Р = г' — г = 3,2 битгсимвол, Н(К) 135 Ф = — = — 43 символа.
Р 3,2 В примере 14.2 совершенная секретность сообщения из 29 символов иллюстрировалась с использованием того же типа ключевой последовательности, что и в данном примере, где показано, что если имеюшийся шифрованный текст состоит из 43 символов (откуда следует, что некоторая часть ключевой последовательности должна использоваться дважды), то возможно единственное решение. В то же время не определена вычислительная сложность отыскания решения. Даже если оценить теоретическое количество шифрованного текста, необходимое для взлома шифра, практически это может оказаться невозможным. 14.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
