Теория связи в секретных системах

Теория связи в секретных системах
Communication Theory of Secrecy Systems
Автор:	Шеннон К.
Жанр:	Криптология
Язык оригинала:	английский
Оригинал издан:	1949
Издательство:	John Wiley & Sons
Страниц:	59

Теория связи в секретных системах (англ. Communication Theory of Secrecy Systems, 1949) - статья Клода Шеннона опубликованная в The Bell System Technical Journal в 1948 году. Данная статья послужила началом обширных исследований в теории кодирования и передачи информации, и, по всеобщему мнению, придала криптографии статус науки, а также ознаменовала наступление эры научной криптологии с секретными ключами.. В ней определены фундаментальные понятия теории криптографии.

Весной 1941 года К. Шеннон вернулся в компанию Белл. С началом Второй мировой войны Т.Фрай возглавил работу над программой для систем управления огнем для противовоздушной обороны. Шеннон присоединился к группе Фрая и работал над устройствами, засекавшими самолеты противника и нацеливавшими зенитные установки, также он разрабатывал криптографические системы, в том числе и правительственную связь, которая обеспечивала переговоры Черчилля и Рузвельта через океан. В 1945 году, Шенноном был представлен секретный доклад, который и был опубликован в «Bell System Technical Journal».

Об авторе

Клод Э́лвуд Ше́ннон (англ. Claude Elwood Shannon) — американский математик и инженер, основатель теории информации, автор многих книг и статей по кибернетике.

Содержание

Математическая структура секретных систем

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

Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

1. мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
2. в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
3. должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.

Поэтому функция энтропии $H$ должна удовлетворять условиям:

1. $H(p_1,\;\ldots,\;p_n)$ определена и непрерывна для всех $p_1,\;\ldots,\;p_n$, где $p_i\in[0,\;1]$ для всех $i=1,\;\ldots,\;n$ и $p_1+\ldots+p_n=1$. (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита.)
2. Для целых положительных $n$, должно выполняться следующее неравенство:

   $H\underbrace{\left(\frac{1}{n},\;\ldots,\;\frac{1}{n}\right)}_n<H\underbrace{\left(\frac{1}{n+1},\;\ldots,\;\frac{1}{n+1}\right)}_{n+1}.$

3. Для целых положительных $b_i$, где $b_1+\ldots+b_k=n$, должно выполняться равенство:

   $H\underbrace{\left(\frac{1}{n},\;\ldots,\;\frac{1}{n}\right)}_n= H\left(\frac{b_1}{n},\;\ldots,\;\frac{b_k}{n}\right)+\sum_{i=1}^k\frac{b_i}{n}H\underbrace{\left(\frac{1}{b_i},\;\ldots,\;\frac{1}{b_i}\right)}_{b_i}.$

Шеннон показал, что единственная функция, удовлетворяющая этим требованиям, имеет вид:

$-K\sum_{i=1}^np(i)\log_2 p(i),$

где $K$ — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии ($H=-p_1\log_2 p_1-\ldots-p_n\log_2 p_n$), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. (см. цепи Маркова). Избыточность играет центральную роль в изучении секретных систем.

Секретная система определяется абстрактно как некоторое множество отображений одного пространства (множества возможных сообщений) в другое пространство (множество возможных криптограмм). Каждое конкретное отображение из этого множества соответствует способу шифрования при помощи конкретного ключа.

Так же делается несколько предположений:

• Отображения являются взаимно однозначными, так что если известен ключ, то в результате процесса расшифрования возможен лишь единственный ответ.
• Каждому ключу (и, следовательно, каждому отображению) соответствует некоторая априорная вероятность - вероятность выбрать этот ключ. Аналогично каждому возможному сообщению соответствует априорная вероятность, определяемая задающим сообщение вероятностным процессом. Эти вероятности различных ключей и сообщений являются фактически априорными вероятностями для шифровальщика противника и характеризуют его априорные знания относительно интересующей его проблемы.

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

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

Так же в первой части приводятся примеры шифров:

• простой подстановки.
• Виженера и его варианты.
• диграммная, триграммная и n-граммнная подстановки.
• матричная система.
• Плэйфера.
• с автоключом.
• дробные шифры.

Теоретическая секретность

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

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

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

$P_E(M) = {P(M)P_M(E) \over P(E)}.$

где

P(M) – априорная вероятность сообщения M;

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

P(E) – вероятность получения криптограммы E;

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

Для совершенной секретности системы величины P_E(M) и P(M) должны быть равны для всех E и M. Следовательно, должно быть выполнено одно из равенств: или P(M) = 0 [это решение должно быть отброшено, так как требуется, чтобы равенство осуществлялось при любых значениях P(M)], или же

P_M(E) = P(E)

для любых M и E. Наоборот, если P_M(E) = P(E), то

P_E(M) = P(M),

и система совершенно секретна. Таким образом, можно сформулировать следующее:

Необходимое и достаточное условие для совершенной секретности состоит в том, что

P_M(E) = P(E).

для всех M и E, т.е. P_M(E) не должно зависеть от M.

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

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

Рассматриваются идеальные системы - секретные системы с конечным ключом, в которых неопределенность не стремится к нулю при N. В любом языке можно аппроксимировать такую ситуацию, т.е. отсрочить приближение H(N) к нулю до сколь угодно больших N. Однако такие системы имеют много недостатков, таких как сложность и чувствительность к ошибкам при передаче криптограммы.

Вводятся пять основных критериев оценки секретных систем:

• Количество секретности.
• Объем ключа.
• Сложность операции зашифрования и расшифрования.
• Разрастание числа ошибок.
• Увеличение объема сообщения.

Практическая секретность

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

См. также

• История криптографии
• Математическая теория связи

Ссылки

• Communication Theory of Secrecy Systems
• Scanned version of the published BSTJ paper
• Теория связи в секретных системах