Теория связи в секретных системах.
Клод Шеннон.
Материал, изложенный в данной статье, первоначально составлял содержание секретного доклада "математическая теория криптографии", датированного 1 сентября 1945 года. Затем он был рассекречен, и в 1949 году опубликован в техническом журнале корпорации Bell System.
1. Введение и краткое содержание.
Вопросы криптографии и секретных систем открывают возможность для интересных применений теории связи. В настоящей статье развивается теория секретных систем. Изложение ведется в теоретическом плане и имеет своей целью дополнить положения, приводимые в обычных работах по криптографии. В этих работах детально изучаются многие стандартные типы кодов и шифров, а также способы их расшифровки. Мы будем иметь дело с общей математической структурой и свойствами секретных систем.
Наше изложение будет ограничено в нескольких отношениях. Во-первых, имеются три общих типа секретных систем:
1) системы маскировки, которые включают применение таких методов, как невидимые чернила, представление сообщения в форме безобидного текста или маскировки криптограммы, и другие методы, при помощи которых факт наличия сообщения скрывается от противника;
2) тайные системы (например, инвертирование речи), в которых для раскрытия сообщения требуется специальное оборудование;
3) "собственно" секретные системы, где смысл сообщения скрывается при помощи шифра, кода и т.д., но само существование сообщения не скрывается и предполагается, что противник обладает любым специальным оборудованием, необходимым для перехвата и записи переданных сигналов. Здесь будет рассмотрен только третий тип систем, так как системы маскировки представляют в основном психологическую проблему, а тайные системы - техническую проблему.
Во-вторых, наше изложение будет ограничено случаем дискретной информации, где сообщение, которое должно быть зашифровано, состоит из последовательных дискретных символов, каждый из которых выбран из некоторого конечного множества. Эти символы могут быть буквами или словами некоторого языка, амплитудными уровнями "квантованной" речи или видеосигнала и т.д., но главный акцент будет сделан на случае букв.
Статья делится на три части. Резюмируем теперь кратко основные результаты исследования. В первой части излагается основная математическая структура секретных систем. В теории связи считается, что язык может рассматриваться как некоторый вероятностный процесс, который создает дискретную последовательность символов в соответствии с некоторой системой вероятностей.
С каждым языком связан некоторый параметр D, который можно назвать избыточностью этого языка. Избыточность измеряет в некотором смысле, насколько может быть уменьшена длина некоторого текста в данном языке без потери какой-либо части информации. Простой пример: так как в словах английского языка за буквой q всегда следует только буква u, то u может быть без ущерба опущена. Значительные сокращения в английском языке можно осуществить, используя его статистическую структуру, частую повторяемость определенных букв или слов, и т.д. Избыточность играет центральную роль в изучении секретных систем.
Секретная система определяется абстрактно как некоторое множество отображений одного пространства (множества возможных сообщений) в другое ространство (множество возможных криптограмм). Каждое конкретное отображение из этого множества соответствует способу шифрования при помощи конкретного ключа.
Предполагается, что отображения являются взаимнооднозначными, так что если известен ключ, то в результате процесса расшифрования возможен лишь единственный ответ.
Предполагается далее, что каждому ключу (и, следовательно, каждому отображению) соответствует некоторая априорная вероятность - вероятность выбрать этот ключ. Аналогично каждому возможному сообщению соответствует априорная вероятность, определяемая задающим сообщение вероятностным процессом. Эти вероятности различных ключей и сообщений являются фактически априорными вероятностями для шифровальщика противника и характеризуют его априорные знания относительно интересующей его проблемы.
Чтобы использовать такую секретную систему, сначала выбирается некоторый ключ и посылается в точку приема. Выбор ключа определяет конкретное отображение из множества отображений, образующих систему. Затем выбирается сообщение и с помощью отображения, соответствующего выбранному ключу, из этого сообщения формируется криптограмма. Эта криптограмма передается в точку приема по некоторому каналу и может быть перехвачена противником. На приемном конце с помощью отображения, обратного выбранному, из криптограммы восстанавливают первоначальное сообщение.
Если противник перехватит криптограмму, он может с ее помощью сосчитать апостериорные вероятности различных возможных сообщений и ключей, которые могли быть использованы для составления такой криптограммы. Это множество апостериорных вероятностей образует его сведения о ключах и сообщениях после перехвата. "Сведения", таким образом, представляют собой некоторое множество предположений, которым приписаны вероятности. Вычисление апостериорных вероятностей является общей задачей дешифрования.
Проиллюстрируем эти понятия простым примером. В шифре простой подстановки со случайным ключом имеется 26! отображений, соответствующих 26! способам, которыми мы можем заменить 26 различных букв. Все эти способы равновозможны, и поэтому каждый имеет априорную вероятность 1/26! Если такой шифр применяется к "нормативному английскому языку" и предполагается, что шифровальщик противника не знает ничего об источнике сообщений, кроме того, что он создает английский текст, то априорными вероятностями различных сообщений из N букв являются просто их относительные частоты в нормативном английском тексте.
Если противник перехватил такую криптограмму из N букв, его апостериорные вероятности изменятся. Если N достаточно велико (скажем, 50 букв), имеется обычно единственное сообщение с апостериорной вероятностью, близкой к единице, в то время как все другие сообщения имею суммарную вероятность, близкую к нулю. Таким образом, имеется, по существу, единственное "решение" такой криптограммы. Для меньших N (скажем, N = 15) обычно найдется много сообщений и ключей, вероятности которых сравнимы, и не найдется ни одного сообщения и ключа с вероятностью, близкой к единице. В этом случае "решение" криптограммы неоднозначно.
В результате рассмотрения секретных систем, которые могут быть представлены как совокупность отображений одного множества элементов в другое, возникают две естественные операции комбинирования, производящие из двух данных систем третью. Первая операция комбинирования называется операцией "умножения" (произведением) и соответствует зашифрованию сообщения с помощью системы R с последующим зашифрованием полученной криптограммы с помощью системы S, причем ключи R и S выбираются независимо. Полный результат этой операции представляет собой секретную систему, отображения которой состоят из всех произведений (в обычном смысле R на отображения из S. Вероятности результирующих отображений являются произведениями вероятностей двух исходных отображений.
Вторая операция комбинирования является "взвешенным сложением":
T = pR + qS, p + q = 1.
Она представляет собой следующее. Сначала делается предварительный выбор, какая из систем R или S будет использоваться, причем система R выбирается с вероятностью p, а система S с вероятностью q. После этого выбранная система используется описанным выше способом.
Будет показано, что секретные системы с этими двумя операциями комбинирования образуют, по существу, "линейную ассоциативную алгебру" с единицей, - алгебраический объект) подробно изученный математиками.
Среди многих возможных секретных систем имеется один тип с многочисленными особыми свойствами. Этот тип назовем "чистой" системой. Система является чистой, если все ключи равновероятны и если для любых трех отображений Ti, Tj, Tk из множества отображений данной системы произведение
TiTj-1Tk
также является отображением из этого множества. То есть зашифрование, расшифрование и снова зашифрование с любыми тремя ключами должно быть эквивалентно одному зашифрованию с некоторым ключом.
Можно показать, что для чистого шифра все ключи по существу эквивалентны - все они приводят к тому же самому множеству апостериорных вероятностей. Больше того, каждой криптограмме соответствует некоторое множество сообщений ("остаточный класс"), из которых могла бы получиться эта криптограмма, а апостериорные вероятности сообщений в этом классе пропорциональны априорным вероятностям. Вся информация, которую противник получил бы в результате перехвата криптограммы, заключается в установлении остаточного класса. Многие из обычных шифров являются чистыми системами, в том числе простая подстановка со случайным ключом. В этом случае остаточный класс состоит из всех сообщений с таким же набором буквенных повторений, как в перехваченной криптограмме.
По определению, две системы R и S являются "подобными", если существует фиксированное отображение A (имеющее обратное A-1) такое, что
R = AS.
Если R и S подобны, то между получающимися в результате применения этих систем множествами криптограмм можно установить взаимнооднозначное соответствие, приводящее к тем же самым апостериорным вероятностям. Такие две системы аналитически записываются одинаково.
Во второй части статьи рассматривается проблема "теоретической секретности". Насколько легко некоторая система поддается раскрытию при условии, что для анализа перехваченной криптограммы противник располагает неограниченным количеством времени и специалистов? Эта проблема тесно связана с вопросами связи при наличии шумов, и понятия энтропии и неопределенности, введенные в теории связи, находят прямое применение в этом разделе криптографии.