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

11. Ненадежность.

Предположим теперь, что для английского текста используется шифр простой подстановки и что перехвачено определенное число, скажем N, букв зашифрованного текста. Если N достаточно велико, скажем более 50, то почти всегда существует единственное решение шифра, т.е. единственная последовательность, имеющая смысл на английском языке, в которую переводится перехваченный материал с помощью простой подстановки. Для меньших N шансы на неединственность решения увеличиваются; для N = 15, вообще говоря, будет существовать некоторое число подходящих отрывков осмысленного английского текста, в то время как для N = 8 окажется подходящей значительная часть (порядка 1/8) всех возможных значащих английских последовательностей такой длины, так как из восьми букв редко повторится больше чем одна. При N = 1, очевидно, возможна любая буква и апостериорная вероятность любой буквы будет равна ее априорной вероятности. Для одной буквы система является совершенно секретной.

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

Для самых простых систем эти вычисления можно эффективно выполнить. Таблица 1 дает апостериорные вероятности для шифра Цезаря, примененного к английскому тексту, причем ключ выбирался случайно из 26 возможных ключей. Для того, чтобы можно было использовать обычные таблицы частот букв, диграмм и триграмм, текст был начат в случайном месте (на страницу открытой наугад книги был случайно опущен карандаш). Сообщение, выбранное таким способом, начинается с "creases to" (карандаш опущен на третью букву слова increases). Если известно, что сообщение начинается не с середины, а с начала некоторого предложения, то нужно пользоваться иной таблицей, соответствующей частотам букв, диграмм и триграмм, стоящих в начале предложения.

Таблица 1. Апостериорные вероятности для криптограммы типа Цезаря.

Расшифровки	N = 1	N = 2	N = 3	N = 4	N = 5
CREAS	0,028	0,0377	0,1111	0,3673	1
DSFBT	0,038	0,0314
ETGCU	0,131	0,0881
FUNDV	0,029	0,0189
GVIEW	0,020
HWJFX	0,053	0,0063
IXKGY	0,063	0,0126
JYLHZ	0,001
KZMIA	0,004
LANJB	0,034	0,1321	0,2500
МВОКС	0,025		0,0222
NCPLD	0,071	0,1195
ODQME	0,080	0,0377
PERNF	0,020	0,0818	0,4389	0,6327
QFSOG	0,001
RGTPH	0,068	0,0126
SHUQI	0,061	0,0881	0,0056
TIVRJ	0,105	0,2830	0,1667
UJWSK	0,025
VKXTL	0,009
WLYUM	0,015		0,0056
XMZVN	0,002
YNAWO	0,020
ZOBXP	0,001
APCYQ	0,082	0,0503
BQDZR	0,014
H (десятичных единиц)	1,2425	0,9686	0,6034	0,285	0

Шифр Цезаря со случайным ключом является чистым, и выбор частного ключа не влияет на апостериорные вероятности. Чтобы определить эти вероятности, надо просто выписать возможные расшифровки с помощью всех ключей и вычислить их априорные вероятности. Апостериорные вероятности получатся из этих последних в результате деления их на их сумму. Эти возможные расшифровки, образующие остаточный класс этого сообщения, найдены с помощью стандартного процесса последовательного "пробегания алфавита", в таблице 1 они даны слева. Для одной перехваченной буквы апостериорные вероятности равны априорным вероятностям для всех букв (они приведены в таблице под рубрикой N = 1).

Для двух перехваченных букв эти вероятности равны априорным вероятностям диграмм, пронормированным на их сумму (они приведены в столбце N = 2). Триграммные частоты получены аналогично и приведены в столбце N = 3. Для четырех- и пятибуквенных последовательностей вероятности находились из триграммных частот с помощью умножения, так как с некоторым приближением

p(ijkl) = p(ijk)p_jk(l).

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

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

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

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

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

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

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

Учитывая эти соображения, естественно использовать ненадежность в качестве теоретической меры секретности. Следует отметить, что имеются две основные ненадежности: ненадежность ключа и ненадежность сообщения. Они будут обозначаться через H_E(K) и H_E(M) соответственно. Их величины определяются соотношениями

,

,

где E, M и K – криптограмма, сообщение и ключ;
   P(E,K) – вероятность ключа K и криптограммы E;
   P_E(K) – апостериорная вероятность ключа K, если перехвачена криптограмма E;
   P(E,M) и P_E(M) – аналогичные вероятности, но не для ключа, а для сообщения.

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

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

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

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

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