Абсолютно стойкий шифр

Абсолютно стойкий шифр — шифр, характеризующийся тем, что криптоаналитик принципиально не сможет извлечь статистическую информацию относительно выбираемых ключей из перехватываемого шифротекста.

Математически понятие абсолютно стойкого шифра было введено Клодом Шенноном в 1945 году в работе «Математическая теория криптографии».

Вспомогательные понятия

Пусть $X$ и $Y$ — алфавиты открытого и шифрованного текста такие, что $|X|>1,$ $|Y|>1,$ $|Y|\ge |X|$.

Шифрование задаётся инъективным отображением $e_k:X\to Y$, дешифрование — отображением $d_k:e_k(X)\to X,$ $k\in K=\{1,2,\mathrm{...},n\}$.

$E=\{e_k,k\in K\},D=\{d_k,k\in K\}$ — наборы правил шифрования и дешифрования.

Максимальное число $|E|=n$ возможных отображений равно количеству размещений из $|Y|$ по $|X|$ (числу способов выбрать подмножества размером $|X|$ в множестве $Y$, учитывая порядок элементов).

Возникновение очередного символа $x\in X$, выбор ключа $k\in K$ (то есть выбор отображения $e_k$), получение шифротекста $y\in Y$ реализуются с некоторыми вероятностями:

$P(X^l)=\{p_{X^l}(\overrightarrow{x}),\overrightarrow{x}\in X^l\}$ — распределение вероятностей для открытого текста,

$P(K^l)=\{p_{K^l}(\overrightarrow{k}),\overrightarrow{k}\in K^l\}$ — распределение вероятностей для комбинации номеров отображений,

$P(Y^l)=\{p_{Y^l}(\overrightarrow{y}),\overrightarrow{y}\in Y^l\}$ — распределение вероятностей для шифротекста, где

$X^l,K^l,Y^l$ — декартовы степени множеств $X,K,Y$, $l$ — количество символов в открытом тексте.

Будем считать, что случайные величины, соответствующие появлению открытого текста $\overrightarrow{x}$ и ключа $\overrightarrow{k}$, независимыми. Тогда:

$p_{Y^l}(\overrightarrow{y})=\sum _{}{p}_{X^l}(\overrightarrow{x})p_{K^l}(\overrightarrow{k})$, где сумма ведётся по всем $\overrightarrow{x}$ и $\overrightarrow{k}$ таким, что $e_{\overrightarrow{k}}(\overrightarrow{x})=(e_{k_1}(x_1),\mathrm{...},e_{k_l}(x_l){)}^T=\overrightarrow{y}$.

$E^l,D^l$ — множества правил шифрования и дешифрования (декартовы степени множеств $E,D$).

Учитывая, что не каждая комбинация символов длины $l$ из алфавита $X$ может появиться в открытом тексте, введём: $X^{(l)}=\{\overrightarrow{x}:p_{X^l}(\overrightarrow{x})>0\},Y^{(l)}=\{\overrightarrow{y}:p_{Y^l}(\overrightarrow{y})>0\}$.

Шифр замены с неограниченным ключом — семейство шифров $S_H=\{S_H^{(l)},l\in \mathbb{N}\}$, где $S_H^{(l)}$ — представляет собой совокупность $X^{(l)},K^l,Y^{(l)},E^l,D^l,P(X^{(l)}),P(K^l),P(Y^{(l)})$, при этом $p_{K^l}(\overrightarrow{k})>0,\mathrm{\forall }\overrightarrow{k}\in K^l$.

Длина ключа шифра замены с неограниченным ключом совпадает с размером открытого текста $l$.

Пусть $\tilde{K}$ — конечное множество некоторых ключей (некоторых наборов натуральных чисел). Длина ключа из $\tilde{K}$ может быть меньше $l$. Для каждого ключа из $\tilde{K}$ можно задать правило детерминированного построения ключевого потока $\overrightarrow{k}=(k_1,\mathrm{...},k_l{)}^T\in K^l$. Полученный таким образом набор ключевых потоков для всех ключей из $\tilde{K}$ обозначим $K^{(l)}$. Например, для ключа $(k_1,\mathrm{...},k_p{)}^T\in \tilde{K},1<p<l$ в качестве ключевого потока можно взять периодическое повторение этого ключа $(k_1,\mathrm{...},k_p,k_1,\mathrm{...},k_p,\mathrm{...}{)}^T\in K^l$. Заметим, что $K^{(l)}\subseteq K^l$.

Шифр замены с ограниченным ключом — семейство шифров $S_O=\{S_O^{(l)},l\in \mathbb{N}\}$, где $S_O^{(l)}$ есть та же совокупность, что и для определённого выше шифра с неограниченным ключом, в которой вместо $K^l$ и $P(K^l)$ используется множество $K^{(l)}$ и распределение $P(K^{(l)})$.

Формальное определение

Пусть $p_{X^{(l)}|Y^{(l)}}(\overrightarrow{x}|\overrightarrow{y})$ — вероятность, что было зашифровано сообщение $\overrightarrow{x}\in X^{(l)}$ при регистрации шифротекста $\overrightarrow{y}\in Y^{(l)}$. Шифр называется абсолютно стойким, если выполнено:

$p_{X^{(l)}|Y^{(l)}}(\overrightarrow{x}|\overrightarrow{y})=p_{X^{(l)}}(\overrightarrow{x})$ $\mathrm{\forall }\overrightarrow{x}\in X^{(l)},\mathrm{\forall }\overrightarrow{y}\in Y^{(l)},\mathrm{\forall }l\in \mathbb{N}$.

Другими словами, апостериорное распределение вероятностей $P_{X^{(l)}|Y^{(l)}}=\{p_{X^{(l)}|Y^{(l)}}(\overrightarrow{x}|\overrightarrow{y}),x\in X^{(l)},y\in Y^{(l)}\}$ совпадает с априорным распределением $P(X^{(l)})$. В терминах теории информации это означает, что условная энтропия сообщения при известном шифрованном тексте равна безусловной. Знание шифротекста $\overrightarrow{y}$ не даёт криптоаналитику никакого полезного знания для получения $\overrightarrow{x}$ (расшифровка возможна только полным перебором).

Основные свойства

Никакой шифр с ограниченным ключом $S_O$ не является совершенным.

Шаблон:Hider Если шифр совершенный, то $|X|\le |Y|\le |K|$.

Теорема Шеннона

Формулировка

Шифр с неограниченным ключом $S_H$, у которого $|X|=|Y|=|K|$ является совершенным тогда и только тогда, когда:

$1.$ $|K(x,y)|=1$ $\mathrm{\forall }x\in X,\mathrm{\forall }y\in Y$, где $K(x,y)=\{k\in K:e_k(x)=y\}$, то есть для любого $x$ и любого $y$ существует только один ключ $k$ такой, что $e_k(x)=y$;

$2.$ $p_K(k)\equiv p(k)=\frac{1}{|K|}$ $\mathrm{\forall }k\in K$, то есть ключи должны быть равновероятны.

Доказательство

$(\Rightarrow 1)$

Так как $|Y|=|K|$, то из $|K(x,y)|\ge 1$ следует, что при $k_1\ne k_2$следует $e_{k_1}(x)\ne e_{k_2}(x)$ $\mathrm{\forall }x\in X$.

$(\Rightarrow 2)$

Занумеруем ключи следующим образом при фиксированном $y$: $e_{k_j}(x_j)=y,j=\overline{1,|X|}$. Получим:

$p(x_j)=p(x_j|y)=\frac{p(y|x_j)\cdot p(x_j)}{p(y)}=\frac{p(k_j)\cdot p(x_j)}{p(y)}\Rightarrow p(k_j)=p(y)$ $\mathrm{\forall }j=\overline{1,|X|}$.

$(\Leftarrow 1,2)$

Используем ту же нумерацию, что и в предыдущем пункте, считая $y$ фиксированным. Применяя $1$:

$p(y)=\sum _{(x_j,k_j):e_{k_j}(x_j)=y}p(x_j)\cdot p(k_j)=\frac{1}{N}\cdot \sum _{j=1}^{N}p(x_j)=\frac{1}{N}$. Применяя $1$ и $2$:

$p(x_j|y)=\frac{p(x_j)\cdot p(y|x_j)}{p(y)}=p(x_j)$. Получили определение абсолютной стойкости.

Общий вид

Исходя из теоремы Шеннона, правило шифрования шифра замены $S_H^{(l)}$ при $l=1$, у которого $|X|=|Y|=|K|$, можно представить в виде латинского квадрата:

$K/X$	$x_1$	$\mathrm{...}$	$x_{|X|}$
$k_1$	$e_{k_1}(x_1)$	$\mathrm{...}$	$e_{k_1}(x_{|X|})$
$\mathrm{...}$	$\mathrm{...}$	$\mathrm{...}$	$\mathrm{...}$
$k_{|X|}$	$e_{k_{|X|}}(x_1)$	$\mathrm{...}$	$e_{k_{|X|}}(x_{|X|})$

При равновероятном использовании $k_1,\mathrm{...},k_{|X|}$ система будет обладать абсолютной стойкостью. Практической реализацией такой системы, например, является шифр Вернама.

Замечание

Существуют абсолютно стойкие шифры, для которых количество символов в алфавите $|X|$ открытого текста меньше $|Y|$. Например:

$X=\{x_1,x_2\},Y=\{1,2,3\},K=\{k_1,\mathrm{..},k_6\}$

$K/X$	$x_1$	$x_2$
$k_1,p(k_1)=\frac{19}{80}$	$1$	$2$
$k_2,p(k_2)=\frac{3}{20}$	$1$	$3$
$k_3,p(k_3)=\frac{21}{80}$	$2$	$1$
$k_4,p(k_4)=\frac{1}{10}$	$2$	$3$
$k_5,p(k_5)=\frac{1}{8}$	$3$	$1$
$k_6,p(k_6)=\frac{1}{8}$	$3$	$2$

Абсолютная стойкость данного шифра легко проверяется по определению по формуле: $p(x|y)=\frac{p(y|x)p(x)}{\sum _{x^{\prime }}p(x^{\prime })p(y|x^{\prime })}=\frac{p(x)\sum _{k}p(k)}{\sum _{x^{\prime },k\in K(x^{\prime },y)}p(x^{\prime })p(k)}$ .

Этот шифр остаётся абсолютно стойким для любого распределения $P(X)$.

См. также

• Криптографическая стойкость
• Шифрование

Литература

• Шаблон:Source
• Шаблон:Книга
• Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры. Шаблон:М.: Гелиос АРВ, 2005. — 160 с.