Клод Шеннон - Теория связи в секретных системах, страница 8

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

Эта условная энтропия для удобства будетназываться ненадежностью.С криптографической точки зрения секретная система почти тождественна системесвязи при наличии шума. На сообщение (передаваемый сигнал) действует некоторыйстатистический элемент (секретная система с ее статистически выбранным ключом). Врезультате получается криптограмма (аналог искаженного сигнала), подлежащаядешифрованию. Основное различие заключается в следующем: во-первых, в том, чтопреобразование при помощи шифра имеет обычно более сложную природу, чемвозникающее за счет шума в канале; и, во-вторых, ключ в секретной системе обычновыбирается из конечного множества, в то время как шум в канале чаще являетсянепрерывным, выбранным по существу из бесконечного множества.Учитывая эти соображения, естественно использовать ненадежность в качестветеоретической меры секретности. Следует отметить, что имеются две основныененадежности: ненадежность ключа и ненадежность сообщения.

Они будут обозначатьсячерез HE(K) и HE(M) соответственно. Их величины определяются соотношениямиH E ( K ) = - å P ( E , K ) log PE ( K ) ,E ,KH E ( M ) = - å P ( E , M ) log PE ( M ) ,E ,Mгде E, M и K – криптограмма, сообщение и ключ;P(E,K) – вероятность ключа K и криптограммы E;PE(K) – апостериорная вероятность ключа K, если перехвачена криптограмма E;P(E,M) и PE(M) – аналогичные вероятности, но не для ключа, а для сообщения.Суммирование в HE(K) проводится по всем возможным криптограммамопределенной длины (скажем, N) и по всем возможным ключам. Для HE(M) суммированиепроводится по всем сообщениям и криптограммам длины N. Таким образом, HE(K) и27HE(M) являются функциями от N – числа перехваченных букв.

Это будет иногдауказываться в обозначении так: HE(K,N), HE(M,N). Заметим, что эти ненадежностиявляются «полными», т.е. не делятся на N с тем, чтобы получить скорость ненадежности,которая рассматривалась в работе «Математическая теория связи».Те же самые рассуждения, которые были использованы в «Математической теориисвязи» для обоснования введения ненадежности в качестве меры неопределенности в теориисвязи, применимы и здесь. Так, из того, что ненадежность равна нулю, следует, что односообщение (или ключ) имеет единичную вероятность, а все другие – нулевую. Этот случайсоответствует полной осведомленности шифровальщика.

Постепенное убываниененадежности с ростом N соответствует увеличению сведений об исходном ключе илисообщении. Кривые ненадежности сообщения и ключа, нанесенные на график как функцииот N, мы будем называть характеристиками ненадежности рассматриваемой секретнойсистемы.Величины HE(K,N) и HE(M,N) для криптограммы шифра Цезаря, рассмотреннойвыше, сосчитаны и приведены в нижней строке табл. 1. Числа HE(K,N) и HE(M,N) в этомслучае равны и даны в десятичных единицах (т.е.

при вычислениях в качестве основаниялогарифма бралось 10). Следует отметить, что ненадежность здесь сосчитана для частнойкриптограммы, так как суммирование ведется только по M (или K), но не по E. В общемслучае суммирование должно было бы проводиться по всем перехваченным криптограммамдлины N, в результате чего получилась бы средняя неопределенность. Вычислительныетрудности не позволяют сделать это практически.12.Свойства ненадежности.Можно показать, что ненадежность обладает некоторыми интересными свойствами,большинство из которых соответствует нашему интуитивному представлению о поведениивеличины такого рода. Покажем сначала, что ненадежность ключа или фиксированной частисообщения уменьшается при увеличении количества перехваченного зашифрованного текста.Теорема 7. Ненадежность ключа НЕ(K,N) — невозрастающая функция N7.Ненадежность первых А букв сообщения является невозрастающей функцией N.

Еслиперехвачено N букв, то ненадежность первых N букв сообщения меньше или равнаненадежности ключа. Это можно записать следующим образом:HE (K,S) £ HE (K,S), S ³ N,HE (M,S) £ HE (M,N),HE (M,N) £ HE (K,N).Введенное во втором утверждении ограничение A буквами означает, что ненадежность вычисляется по отношению к первым буквам сообщения, а не ко всему объемуперехваченного сообщения. Если отказаться от этого ограничения, то можно получитьвозрастание ненадежности сообщения (и обычно это имеет место) с увеличением временипросто из-за того, что большее количество букв допускает и большее разнообразиевозможных сообщений. Выводы этой теоремы соответствуют тому, на что можно было бынадеяться при разумной мере секретности, так как едва ли можно оказаться в худшемположении при увеличении объема перехваченного текста. Тот факт, что эти выводы могутбыть доказаны, дает лучшее подтверждение полезности принятой нами количественноймеры ненадежности.Справедливость утверждений этой теоремы вытекает из некоторых свойств условной энтропии, доказанных в работе «Математическая теория связи».

Так, для доказательства7Здесь предполагается, что ключ фиксирован и не зависит от длины криптограммы N и длины сообщения А.— Прим. ред.28первого или второго утверждения теоремы воспользуемся тем, что для любых случайныхсобытий A и BH(B) ³ HA(B).Если отождествить B с ключом (при условии, что известны первые S букв криптограммы),а А с остающимися N – S буквами, то мы получим первое утверждение. Аналогично, еслиотождествить B с сообщением, то получится второе утверждение.

Последнее утверждениеследует из неравенстваHE (M) £ HE (K,M) = HE (K) + HE,K (M)и из того, что HE,K (M) = 0, так как K и E полностью определяют M.Так как сообщение и ключ выбираются независимо, тоH(M,K) = H(M) + H(K).Кроме того,H(M,K) = H(E,K) = H(E) + HE (K),что вытекает из того факта, что знание M и K или E и K эквивалентно знанию всех трехвеличин M, K и E.

Преобразуя эти две формулы, мы получаем формулу для ненадежностиключа:HE (K) = H(M) + H(K) – H(E),В частности, если H(M) = H(E) то ненадежность ключа HE (K) равна априорнойнеопределенности ключа H(K). Это имеет место в совершенно секретных системах,описанных выше.Формула для ненадежности сообщения может быть получена аналогичным способом. Мыимеем:H(M,E) = H(E) + HE (M) = H(M) + HM (E),HE (M) = H(M) + HM (E) – H(E).Если имеется произведение секретных систем S = TR, то следует ожидать, чтоповторный процесс шифрования не уменьшит ненадежности сообщения. То, что этодействительно так, можно показать следующим образом. Пусть M, E1, E2 – сообщение ипервая и вторая криптограммы соответственно.

ТогдаPE1E2 ( M ) = PE1 ( M )Следовательно,H E1 , E2 ( M ) = H E1 ( M )так как для любых случайных величин х, у, z справедливо Hxy(z) £ Hy(z) то получаемжелаемый результат: H E2 ( M ) ³ H E1 ( M ) .Теорема 8. Ненадежность сообщения для произведения секретных систем S = TR неменьше ненадежности для одной системы R.Предположим, что имеется система T, которая может быть записана как взвешенная сумманескольких систем R,S,…,UT = p1R + p2S + … + pmU,åpi= 1,и системы R,S,…,U имеют ненадежности H1,H2,…,Hm.Теорема 9. Ненадежность для взвешенной суммы систем ограничена неравенствами29åpHii£ H £ å pi H i - å pi log piЭти границы нельзя улучшить. Здесь Hi могут означать ненадежность ключа илисообщения.Верхняя граница достигается, например, в строго идеальных системах (которыебудут описаны ниже), где разложение производится на простые преобразования системы.Нижняя граница достигается, если все системы R,S,…,U приводят к полностью различнымпространствам криптограмм.

Эта теорема также доказывается с помощью общихнеравенств, которым подчиняется ненадежность:HA (B) £ H(B) £ H(A) + HA (B),где A может обозначать данную используемую систему, а B – ключ или сообщение.Имеется аналогичная теорема для взвешенных сумм языков. Для ее доказательстваобозначим данный язык буквой A.Теорема 10. Предположим, что система может быть применена к языкам L1,L2,…,Lm ипри этом получаются ненадежности H1,H2,…,Hm.

Если система применяется к взвешенной сумме å pi Li то ненадежность H ограничена неравенствамиåpHii£ H £ å pi H i - å pi log pi .Эти границы нельзя улучшить. Рассматриваемая ненадежность может относиться как кключу, так и к сообщению.Полная избыточность DN для N букв сообщения определяется с помощьюсоотношенияDN = logG – H(M),где G – полное число сообщений длины N, а H(M) – неопределенность выбора одного изних.