10. Совершенная секретность

Next: 11. Ненадежность Up: Часть II. ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ Previous: 9. Введение Contents: Содержание

10. Совершенная секретность

Предположим, что имеется конечное число возможных сообщений $M_1,\dots, M_n$ с априорными вероятностями $Р(М_1),\dots, Р (М_n)$ и что эти сообщения преобразуются в возможные криптограммы $E_1,\dots,E_m$ , так что

$\begin{displaymath}E=T_iM.\end{displaymath}$

После того как шифровальщик противника перехватил некоторую криптограмму , он может вычислить, по крайней мере в принципе, апостериорные вероятности различных сообщений . Естественно определить совершенную секретность с помощью следующего условия: для всех апостериорные вероятности равны априорным вероятностям независимо от величины этих последних. В этом случае перехват сообщения не дает шифровальщику противника никакой информации1). Теперь он не может корректировать никакие свои действия в зависимости от информации, содержащейся в криптограмме, так как все вероятности, относящиеся к содержанию криптограммы, не изменяются. С другой стороны, если это условие равенства вероятностей не выполнено, то имеются такие случаи, в которых для определенного ключа и определенных выборов сообщений апостериорные вероятности противника отличаются от априорных. А это в свою очередь может повлиять на выбор противником своих действий и, таким образом, совершенной секретности не получится. Следовательно, приведенное определение неизбежным образом следует из нашего интуитивного представления о совершенной секретности.

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

$\begin{displaymath}P_E(M)=\frac{P(M)\cdot P_M(E)}{P(E)},\end{displaymath}$

где

-- априорная вероятность сообщения ;

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

-- вероятность получения криптограммы ;

-- апостериорная вероятность сообщения при условии, что перехвачена криптограмма .

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

$\begin{displaymath}P_M(E)=Р(Е)\end{displaymath}$

для любых

Наоборот, если , то

$\begin{displaymath}P_E(M)=P(M),\end{displaymath}$

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

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

$\begin{displaymath}P_M(Е)=Р(Е)\end{displaymath}$

для всех

, т.е.

не должно зависеть от

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

Далее, должно существовать по крайней мере столько же криптограмм , сколько и сообщений , так как для фиксированного отображение дает взаимнооднозначное соответствие между всеми и некоторыми из . Для совершенно секретных систем для каждого из этих и любого $P_M(Е) = Р (Е)\ne0$ . Следовательно, найдется по крайней мере один ключ, отображающий данное в любое из . Но все ключи, отображающие фиксированное в различные , должны быть различными, и поэтому число различных ключей не меньше числа сообщений . Как показывает следующий пример, можно получить совершенную секретность, когда число сообщений точно равно числу ключей. Пусть занумерованы числами от 1 до , так же как и , и пусть используются ключей. Тогда

$\begin{displaymath}T_iM_j=E_s,\end{displaymath}$

где $s = i+j \pmod n$ . В этом случае оказывается справедливым равенство $P_Е (М) =\frac{1}{n} = Р (Е)$ и система является совершенно секретной. Один пример такой системы показан на рис. 5, где

$\begin{displaymath}s= j +i- 1\pmod 5.\end{displaymath}$

Рис. 5. Совершенная система.

$\begin{figure}\begin{center} \epsfverbosetrue \begin{displaymath}\vcenter{\epsfbox{shannon.5}}\end{displaymath} \end{center} \vskip-10pt \end{figure}$

Совершенно секретные системы, в которых число криптограмм равно числу сообщений, а также числу ключей, характеризуются следующими двумя свойствами: 1) каждое связывается с каждым только одной линией; 2) все ключи равновероятны. Таким образом, матричное представление такой системы является ``латинским квадратом''.

В ``Математической теории связи'' показано, что количественно информацию удобно измерять с помощью энтропии. Если имеется некоторая совокупность возможностей с вероятностями $p_1,\dots, p_n$ , то энтропия дается выражением

$\begin{displaymath}H=-\sum_{}^{}p_i\log p_i.\end{displaymath}$

Секретная система включает в себя два статистических выбора: выбор сообщения и выбор ключа. Можно измерять количество информации, создаваемой при выборе сообщения, через

$\begin{displaymath}Н (М) = - \sum_{}^{} Р(М) \log Р (М),\end{displaymath}$

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

$\begin{displaymath}H(K)=-\sum_{}^{}P(K)\log P(K).\end{displaymath}$

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

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

$\begin{displaymath}R_ML_M\leq R_KL_K.\end{displaymath}$

Такой вид совершенной секретности реализован в системе Вернама.

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

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

Совершенно секретные системы могут применяться и на практике, их можно использовать или в том случае, когда полной секретности придается чрезвычайно большое значение, например, для кодирования документов высших военных инстанций управления или же в случаях, где число возможных сообщений мало. Так, беря крайний пример, когда имеются в виду только два сообщения -- ``да'' или ``нет'', -- можно, конечно, использовать совершенно секретную систему со следующей таблицей отображений:

да 0 1

нет 1 0

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

Next: 11. Ненадежность Up: Часть II. ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ Previous: 9. Введение Contents: Содержание