Список обозначений

Система секретной связи чистая

pure secrecy system
Пусть $S=((e_i\,|\, i\in K),\mathfrak K)$ — замкнутая система секретной связи в смысле теории Шеннона [1], причем $e_i\colon M\to C$ для всех $i\in K$. Предположим, что $e_i\ne e_j$ при $i\ne j$ ($i,j\in K$). Тогда система секретной связи $S$ называется чистой, если
  • для любых $i,j,k\in K$ существует $l\in K$ такой, что $e_ie_j^{-1}e_k=e_l$;
  • распределение вероятностей $\mathfrak K$ равномерно на множестве $K$.
Здесь и далее в этой статье под произведением отображений понимается их композиция, взятая справа налево. Понятие чистой системы секретной связи было введено в основополагающей работе [1]. Вышеуказанная система секретной связи $S$ чиста тогда и только тогда, когда $e_ie_j^{-1}S=S$ для всех $i,j\in K$. Пусть рассматриваемая система секретной связи $S$ чиста. Тогда \[ G=\left\{\left.e_i^{-1}e_j\,\right|\,i,j\in K\right\}=\left\{\left.e_i^{-1}e_k\,\right|\,i\in K\right\}=\left\{\left.e_k^{-1}e_j\,\right|\,j\in K\right\} \] для любого $k\in K$, причем это множество $G$ является подгруппой группы всех перестановок множества $M$ и $\#G=\#K$. Группа $G$ естественно действует на множестве $M$; орбиты этого действия называются остаточными классами сообщений. Каждому остаточному классу сообщений $X$ ставится в соответствие множество $E(X)=\{e_i(x)\,|\, i\in K,\, x\in X\}\subseteq C$. Тогда $C$ является объединением попарно не пересекающихся множеств $E(X)$, причем различным остаточным классам сообщений $X$ соответствуют различные множества $E(X)$. Эти множества $E(X)$ называются остаточными классами криптограмм. Кроме того, для любого остаточного класса сообщений $X$
  • $\#E(X)$ совпадает с $\#X$ и делит $\#K$;
  • $\#\{i\in K\,|\, e_i(m)=c\}=\#\{g\in G\,|\, g(m)=m\}=\#K/\#X$ при произвольных $m\in X$ и $c\in E(X)$.

Говоря неформально, чистая система секретной связи $S$ разлагается в «дизъюнктное объединение» совершенных (при любом априорном распределении вероятностей на пространстве сообщений) систем секретной связи $S_X=((e_i|_X\,|\, i\in K),\mathfrak K)$ по всем остаточным классам сообщений $X$. Пространством сообщений системы секретной связи $S_X$ является $X$, а пространством криптограмм этой системы — $E(X)$. Вся новая информация о зашифрованном сообщении, которую получает противник в результате перехвата криптограммы в чистой системе секретной связи, состоит в том, к какому остаточному классу принадлежит это сообщение.

Обозначим через $\mathfrak M$ некоторое априорное распределение вероятностей на пространстве сообщений $M$. Пусть также $\widetilde k$ и $\widetilde m$ — независимые случайные величины, имеющие распределения $\mathfrak K$ и $\mathfrak M$ соответственно. Приведем формулы для апостериорных вероятностей произвольного сообщения $m\in\mathop{\mathrm{supp}}\mathfrak M$ и произвольного ключа $k\in K$: \begin{align*} \Pr\left(\widetilde m=m\,\left|\,e_{\widetilde k}(\widetilde m)=c\right.\right)&=\begin{cases}\Pr_{\mathfrak M}(m)/\Pr_{\mathfrak M}([m]),&\text{если }c\in E([m]);\\0&\text{в противном случае};\end{cases}\\\Pr\left(\left.\widetilde k=k\,\right|\,e_{\widetilde k}(\widetilde m)=c\right)&=\begin{cases} \frac{\#\left[e_k^{-1}(c)\right]}{\#K}\cdot\frac{\Pr_{\mathfrak M}\left(e_k^{-1}(c)\right)}{\Pr_{\mathfrak M}\left(\left[e_k^{-1}(c)\right]\right)},&\text{если }e_k^{-1}(c)\in\mathop{\mathrm{supp}}\mathfrak M;\\0&\text{в противном случае}.\end{cases} \end{align*} Здесь $c\in\mathop{\mathrm{supp}} e_{\widetilde k}(\widetilde m)$, а $[x]$ обозначает остаточный класс сообщений, содержащий сообщение $x\in M$.

Произведение двух чистых коммутирующих систем секретной связи (см. умножение систем секретной связи) является чистой системой секретной связи. См. также [1].

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

Литература

  • [1] Shannon, C. E. «Communication theory of secrecy systems» 1949

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна