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

Клод Шеннон. Теория связи в секретных системах.1Материал, изложенный в данной статье, первоначально составлял содержаниесекретного доклада «Математическая теория криптографии», датированного1 сентября 1945 г, который в настоящее время2 рассекречен.1. Введение и краткое содержание.Вопросы криптографии и секретных систем открывают возможность для интересныхприменений теории связи.

В настоящей статье развивается теория секретных систем.Изложение ведется в теоретическом плане и имеет своей целью дополнить положения,приводимые в обычных работах по криптографии. В этих работах детально изучаютсямногие стандартные типы кодов и шифров, а также способы их расшифровки. Мы будемиметь дело с общей математической структурой и свойствами секретных систем.Наше изложение будет ограничено в нескольких отношениях. Во-первых, имеютсятри общих типа секретных систем: 1) системы маскировки, которые включают применениетаких методов, как невидимые чернила, представление сообщения в форме безобидноготекста или маскировки криптограммы, и другие методы, при помощи которых факт наличиясообщения скрывается от противника; 2) тайные системы (например, инвертирование речи),в которых для раскрытия сообщения требуется специальное оборудование; 3) «собственно»секретные системы, где смысл сообщения скрывается при помощи шифра, кода и т.д., носамо существование сообщения не скрывается и предполагается, что противник обладаетлюбым специальным оборудованием, необходимым для перехвата и записи переданныхсигналов.

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

Эти символымогут быть буквами или словами некоторого языка, амплитудными уровнями«квантованной» речи или видеосигнала и т.д., но главный акцент будет сделан на случаебукв.Статья делится на три части. Резюмируем теперь кратко основные результатыисследования. В первой части излагается основная математическая структура секретныхсистем. В теории связи считается, что язык может рассматриваться как некоторыйвероятностный процесс, который создает дискретную последовательность символов всоответствии с некоторой системой вероятностей. С каждым языком связан некоторыйпараметр D, который можно назвать избыточностью этого языка.

Избыточность измеряет внекотором смысле, насколько может быть уменьшена длина некоторого текста в данномязыке без потери какой-либо части информации. Простой пример: так как в словаханглийского языка за буквой q всегда следует только буква и, то и может быть без ущербаопущена. Значительные сокращения в английском языке можно осуществить, используя егостатистическую структуру, частую повторяемость определенных букв или слов, и т.д.Избыточность играет центральную роль в изучении секретных систем.Секретная система определяется абстрактно как некоторое множество отображенийодного пространства (множества возможных сообщений) в другое пространство (множество1Печатается по изданию: К.

Шеннон «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 333-369(перевод В.Ф.Писаренко) с корректировкой терминологии переводчика.21949 год — прим. ред.2возможных криптограмм). Каждое конкретное отображение из этого множествасоответствует способу шифрования при помощи конкретного ключа.Предполагается, что отображения являются взаимно-однозначными, так что еслиизвестен ключ) то в результате процесса расшифрования возможен лить единственный ответ.Предполагается далее, что каждому ключу (и, следовательно, каждомуотображению) соответствует некоторая априорная вероятность – вероятность выбрать этотключ. Аналогично каждому возможному сообщению соответствует априорная вероятность,определяемая задающим сообщение вероятностным процессом.

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

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

«Сведения»,таким образом, представляют собой некоторое множество предположений, которымприписаны вероятности. Вычисление апостериорных вероятностей является общей задачейдешифрования.Проиллюстрируем эти понятия простым примером. В шифре простой подстановкисо случайным ключом имеется 26! отображений, соответствующих 26! способам,которыми мы можем заменить 26 различных букв. Все эти способы равновозможны, ипоэтому каждый имеет априорную вероятность 1/26! Если такой шифр применяется к«нормативному английскому языку» и предполагается, что шифровальщик противника незнает ничего об источнике сообщений, кроме того, что он создает английский текст, тоаприорными вероятностями различных сообщений из N букв являются просто ихотносительные частоты в нормативном английском тексте.Если противник перехватил такую криптограмму из N букв, его апостериорныевероятности изменятся.

Если N достаточно велико (скажем, 50 букв), имеется обычноединственное сообщение с апостериорной вероятностью, близкой к единице, в то время каквсе другие сообщения имеют суммарную вероятность, близкую к нулю. Таким образом,имеется, по существу, единственное «решение» такой криптограммы. Для меньших N(скажем, N = 15) обычно найдется много сообщений и ключей, вероятности которыхсравнимы, и не найдется ни одного сообщения и ключа с вероятностью, близкой к единице.В этом случае «решение» криптограммы неоднозначно.В результате рассмотрения секретных систем, которые могут быть представлены каксовокупность отображений одного множества элементов в другое, возникают двеестественные операции комбинирования, производящие из двух данных систем третью.Первая операция комбинирования называется операцией «умножения» (произведением) исоответствует зашифрованию сообщения с помощью системы R с последующимзашифрованием полученной криптограммы с помощью системы S, причем ключи R и Sвыбираются независимо.

Полный результат этой операции представляет собой секретнуюсистему, отображения которой состоят из всех произведений (в обычном смыслепроизведений отображений) отображений из S на отображения из R. Вероятностирезультирующих отображений являются произведениями вероятностей двух исходныхотображений.3Вторая операция комбинирования является «взвешенным сложением»:T = pR + qS, p + q = 1.Она представляет собой следующее.

Сначала делается предварительный выбор, какая изсистем R или S будет использоваться, причем система R выбирается с вероятностью p, асистема S с вероятностью q. После этого выбранная система используется описаннымвыше способом.Будет показано, что секретные системы с этими двумя операциями комбинированияобразуют, по существу, «линейную ассоциативную алгебру» с единицей, – алгебраическийобъект) подробно изучавшийся математиками.Среди многих возможных секретных систем имеется один тип с многочисленнымиособыми свойствами.

Этот тип назовем «чистой» системой. Система является чистой, есливсе ключи равновероятны и если для любых трех отображений Ti, Tj, Tk из множестваотображений данной системы произведениеTiT j-1Tkтакже является отображением из этого множества. То есть зашифрование, расшифрование иснова зашифрование с любыми тремя ключами должно быть эквивалентно одномузашифрованию с некоторым ключом.Можно показать, что для чистого шифра все ключи по существу эквивалентны – всеони приводят к тому же самому множеству апостериорных вероятностей.

Больше того,каждой криптограмме соответствует некоторое множество сообщений («остаточный класс»),из которых могла бы получиться эта криптограмма, а апостериорные вероятности сообщенийв этом классе пропорциональны априорным вероятностям. Вся информация, которуюпротивник получил бы в результате перехвата криптограммы, заключается в установленииостаточного класса. Многие из обычных шифров являются чистыми системами, в том числепростая подстановка со случайным ключом. В этом случае остаточный класс состоит из всехсообщений с таким же набором буквенных повторений, как в перехваченной криптограмме.По определению, две системы R и S являются «подобными», если существуетфиксированное отображение A (имеющее обратное A–1) такое, что R = AS.Если R и S подобны, то между получающимися в результате применения этихсистем множествами криптограмм можно установить взаимнооднозначное соответствие,приводящее к тем же самым апостериорным вероятностям.

Такие две системы аналитическизаписываются одинаково.Во второй части статьи рассматривается проблема «теоретической секретности».Насколько легко некоторая система поддается раскрытию при условии, что для анализаперехваченной криптограммы противник располагает неограниченным количеством времении специалистов? Эта проблема тесно связана с вопросами связи при наличии шумов, ипонятия энтропии и неопределенности, введенные в теории связи, находят прямоеприменение в этом разделе криптографии.«Совершенная секретность» определяется следующими требованиями к системе.Требуется, чтобы апостериорные вероятности различных сообщений, полученные послеперехвата противником данной криптограммы, были бы в точности равны априорнымвероятностям тех же сообщений до перехвата.