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


На домашнюю страничку Титульный лист Предыдущий раздел Следующий раздел

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,0280,03770,11110,36731
DSFBT 0,0380,0314   
ETGCU 0,1310,0881   
FUNDV 0,0290,0189   
GVIEW 0,020    
HWJFX 0,0530,0063   
IXKGY 0,0630,0126   
JYLHZ 0,001    
KZMIA 0,004    
LANJB 0,0340,13210,2500  
МВОКС 0,025 0,0222  
NCPLD 0,0710,1195   
ODQME 0,0800,0377   
PERNF 0,0200,08180,43890,6327 
QFSOG 0,001    
RGTPH 0,0680,0126   
SHUQI 0,0610,08810,0056  
TIVRJ 0,1050,28300,1667  
UJWSK 0,025    
VKXTL 0,009    
WLYUM 0,015 0,0056  
XMZVN 0,002    
YNAWO 0,020    
ZOBXP 0,001    
APCYQ 0,0820,0503   
BQDZR 0,014    
H (десятичных единиц) 1,24250,96860,60340,2850

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

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

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

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

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

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

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

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

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

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

Учитывая эти соображения, естественно использовать ненадежность в качестве теоретической меры секретности. Следует отметить, что имеются две основные ненадежности: ненадежность ключа и ненадежность сообщения. Они будут обозначаться через HE(K) и HE(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) и HE(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, в результате чего получилась бы средняя неопределенность. Вычислительные трудности не позволяют сделать это практически.

На домашнюю страничку Титульный лист Предыдущий раздел Следующий раздел


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

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