Клод Шеннон. Теория связи в секретных системах. Свойства ненадежности.

12. Свойства ненадежности.

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

Теорема 7.  Ненадежность ключа Н_Е(K,N) — невозрастающая функция N. Ненадежность первых А букв сообщения является невозрастающей функцией N. Если перехвачено N букв, то ненадежность первых N букв сообщения меньше или равна ненадежности ключа. Это можно записать следующим образом:

H_E(K,S) H_E(K,N),  SN,
H_E(M,S)H_E(M,N),
H_E(M,N)H_E(K,N).

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

Справедливость утверждений этой теоремы вытекает из некоторых свойств условной энтропии, доказанных в работе "Математическая теория связи". Так, для доказательства первого или второго утверждения теоремы воспользуемся тем, что для любых случайных событий A и B

H(B)H_A(B).

Если отождествить B с ключом (при условии, что известны первые S букв криптограммы), а А с остающимися N – S буквами, то мы получим первое утверждение. Аналогично, если отождествить B с сообщением, то получится второе утверждение. Последнее утверждение следует из неравенства

H_E(M)H_E(K,M) = H_E(K) + H_E,K(M)

и из того, что H_E,K(M) = 0, так как K и E полностью определяют M.

Так как сообщение и ключ выбираются независимо, то

H(M,K) = H(M) + H(K).

Кроме того,

H(M,K) = H(E,K) = H(E) + H_E(K),

что вытекает из того факта, что знание M и K или E и K эквивалентно знанию всех трех величин M, K и E. Преобразуя эти две формулы, мы получаем формулу для ненадежности ключа:

H_E(K) = H(M) + H(K) – H(E),

В частности, если H(M) = H(E), то ненадежность ключа H_E(K) равна априорной неопределенности ключа H(K). Это имеет место в совершенно секретных системах, описанных выше.

Формула для ненадежности сообщения может быть получена аналогичным способом. Мы имеем:

H(M,E) = H(E) + H_E(M) = H(M) + H_M(E),
H_E(M) = H(M) + H_M(E) – H(E).

Если имеется произведение секретных систем S = TR, то следует ожидать, что повторный процесс шифрования не уменьшит ненадежности сообщения. То, что это действительно так, можно показать следующим образом. Пусть M, E₁, E₂ – сообщение и первая и вторая криптограммы соответственно. Тогда

Следовательно,

так как для любых случайных величин х, у, z справедливо H_xy(z)H_y(z) то получаем желаемый результат: .

Теорема 8.  Ненадежность сообщения для произведения секретных систем S = TR не меньше ненадежности для одной системы R.

Предположим, что имеется система T, которая может быть записана как взвешенная сумма нескольких систем R,S,...,U

T = p₁R + p₂S + ... + p_mU,   ,

и системы R, S, ..., U имеют ненадежности H₁, H₁, ..., H_m.

Теорема 9.  Ненадежность для взвешенной суммы систем ограничена неравенствами

.

Эти границы нельзя улучшить. Здесь H_i могут означать ненадежность ключа или сообщения.

Верхняя граница достигается, например, в строго идеальных системах (которые будут описаны ниже), где разложение производится на простые преобразования системы. Нижняя граница достигается, если все системы R, S, ..., U приводят к полностью различным пространствам криптограмм. Эта теорема также доказывается с помощью общих неравенств, которым подчиняется ненадежность:

H_A(B)H(B)H(A) + H_A(B),

где A может обозначать данную используемую систему, а B – ключ или сообщение.

Имеется аналогичная теорема для взвешенных сумм языков. Для ее доказательства обозначим данный язык буквой A.

Теорема 10.  Предположим, что система может быть применена к языкам L₁, L₁, ..., L_m и при этом получаются ненадежности H₁, H₁, ..., H_m. Если система применяется к взвешенной сумме , то ненадежность H ограничена неравенствами

.

Эти границы нельзя улучшить. Рассматриваемая ненадежность может относиться как к ключу, так и к сообщению.

Полная избыточность D_N для N букв сообщения определяется с помощью соотношения

D_N = log G – H(M),

где G – полное число сообщений длины N, а H(M) – неопределенность выбора одного из них. В секретной системе, где полное число возможных криптограмм равно числу возможных сообщений длины N, имеет место неравенство H(E)log G. Следовательно,

H_E(K) = H(K) + H(M) – H(E)H(K) – [log G – H(M)].

Поэтому

H(K) – H_E(K)D_N.

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

Предположим теперь, что имеется чистая секретная система. Обозначим различные остаточные классы сообщений через C₁, C₂, ..., C_r и соответствующие остаточные классы криптограмм через C'₁, C'₂, ..., C'_r. Вероятности всех E из C_i одинаковы:

,   E – элемент C_i,

где _i – число различных сообщений в C_i. Таким образом, имеем

.

Подставив это значение H(E) в выражение, полученное выше для H_E(K), получим следующую теорему.

Теорема 11.  Для чистого шифра

.

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

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 09.03.01. (c) 2001 Андрей Винокуров.