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

Неоднозначность сообщения

equivocation of message

Пусть $S=((e_i\,|\, i\in K),\mathfrak K)$ — система секретной связи в смысле теории Шеннона [1], причем $e_i\colon M\to C$ для всех $i\in K$. Пусть также $\mathfrak M$ — некоторое априорное распределение вероятностей на пространстве сообщений $M$. Обозначим через $\widetilde k$ и $\widetilde m$ независимые случайные величины, имеющие распределения $\mathfrak K$ и $\mathfrak M$ соответственно. Тогда неоднозначностью сообщения называется условная энтропия $\mathbf H_S^{(m)}=H\left(\widetilde m\,\left|\,e_{\widetilde k}(\widetilde m)\right.\right)$. Неоднозначность сообщения является естественной мерой неопределенности сообщения для противника, перехватившего соответствующую криптограмму. Это понятие было введено в основополагающей работе [1] (см. также [2]).

Приведем основные свойства неоднозначности сообщения, полученные в [1].
  • $\mathbf H_S^{(m)}=H(\widetilde m)+H\left(\left.e_{\widetilde k}(\widetilde m)\,\right|\,\widetilde m\right)-H\left(e_{\widetilde k}(\widetilde m)\right)$.
  • $\mathbf H_S^{(m)}\leqslant\mathbf H_S^{(k)}$, где $\mathbf H_S^{(k)}$ — неоднозначность ключа.
  • Пусть для каждого $j\in\{1,\dots,n\}$ определена система секретной связи $S_j=\left(\left(e_{j,i}\,\right|\, i\in K_j),\mathfrak K_j\right)$, причем $e_{j,i}\colon M\to C$ при всех $j\in\{1,\dots,n\}$ и $i\in K_j$. Пусть также $p_1,\dots,p_n$ — вещественные неотрицательные числа такие, что $p_1+\dots+p_n=1$. Тогда \[ \sum_{j=1}^np_j\mathbf H_{S_j}^{(m)}\leqslant\mathbf H_{p_1S_1+\dots+p_nS_n}^{(m)}\leqslant \sum_{j=1}^np_j\mathbf H_{S_j}^{(m)}-\sum_{j=1}^np_j\log p_j, \] причем обе эти оценки для $\mathbf H_{p_1S_1+\dots+p_nS_n}^{(m)}$ достигаются.
  • Если $T=((f_j\,|\, j\in L),\mathfrak L)$ — система секретной связи, причем $f_j\colon D\to M$ для всех $j\in L$, то $\mathbf H_{ST}^{(m)}\geqslant\mathbf H_{T}^{(m)}$.
Всюду в этой статье через $H$ обозначается энтропия, а через $\log$ — логарифм по тому же основанию, что используется в определении энтропии.

Литература

  • [1] Shannon, C. E. «Communication theory of secrecy systems» 1949
  • [2] Shannon, C. E. «A mathematical theory of communication» 1948

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