shannon (1014203), страница 8
Текст из файла (страница 8)
Для одной перехваченной буквы апостериорныевероятности равны априорным вероятностям для всех букв6 (они приведены в таблице подрубрикой N = 1).6Вероятности в приводимой таблице были взяты из таблиц частот, данных в книге Pratt F., Secret and Urgent,Blue Ribbon Books, New York, 1939. Хотя эти таблицы и не являются полными, но для настоящих целей ихдостаточно.26Для двух перехваченных букв эти вероятности равны априорным вероятностямдиграмм, пронормированным на их сумму (они приведены в столбце N = 2).
Триграммныечастоты получены аналогично и приведены в столбце N = 3. Для четырех- и пятибуквенныхпоследовательностей вероятности находились из триграммных частот с помощьюумножения, так как с некоторым приближениемp(ijkl) = p(ijk)pjk(l).Заметим, что для трех букв число возможных сообщений снижается до четырех сообщенийдостаточно высокой вероятности, причем вероятности всех других сообщений малы посравнению с вероятностями этих четырех сообщений. Для четырех букв имеются двавозможных сообщения и для пяти – только одно, а именно правильная дешифровка.В принципе это может быть проведено для любой системы, однако в том случае,когда объем ключа не очень мал, число возможных сообщений настолько велико, чтовычисления становятся практически невыполнимыми.Получаемое таким образом множество апостериорных вероятностей описывает, какпостепенно, по мере получения зашифрованного материала, становятся более точнымисведения шифровальщика противника относительно сообщения и ключа.Это описание, однако, является слишком исчерпывающим и слишком сложным длянаших целей.
Хотелось бы иметь упрощенное описание такого приближения кединственности возможного решения.Аналогичная ситуация возникает в теории связи, когда передаваемый сигналискажается шумом. Здесь необходимо ввести подходящую меру неопределенности того, чтодействительно было передано, при условии, что известен только искаженный шумом вариант– принятый сигнал.В «Математической теории связи» показано, что естественной математическоймерой этой неопределенности является условная энтропия передаваемого сигнала приусловии, что принятый сигнал известен. Эта условная энтропия для удобства будетназываться ненадежностью.С криптографической точки зрения секретная система почти тождественна системесвязи при наличии шума. На сообщение (передаваемый сигнал) действует некоторыйстатистический элемент (секретная система с ее статистически выбранным ключом). Врезультате получается криптограмма (аналог искаженного сигнала), подлежащаядешифрованию.
Основное различие заключается в следующем: во-первых, в том, чтопреобразование при помощи шифра имеет обычно более сложную природу, чемвозникающее за счет шума в канале; и, во-вторых, ключ в секретной системе обычновыбирается из конечного множества, в то время как шум в канале чаще являетсянепрерывным, выбранным по существу из бесконечного множества.Учитывая эти соображения, естественно использовать ненадежность в качестветеоретической меры секретности.
Следует отметить, что имеются две основныененадежности: ненадежность ключа и ненадежность сообщения. Они будут обозначатьсячерез 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, то следует ожидать, чтоповторный процесс шифрования не уменьшит ненадежности сообщения. То, что этодействительно так, можно показать следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
