Абсолютно стойкий шифр (GQvklZmuk vmkwtnw onsj)

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

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

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

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

Шифрование задаётся инъективным отображением $e_{k}:X\rightarrow Y$, дешифрование — отображением $d_{k}:e_{k}(X)\rightarrow X,$ $k\in K=\{1,2,...,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}}({\vec {x}}),{\vec {x}}\in X^{l}\}$ — распределение вероятностей для открытого текста,

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

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

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

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

$p_{Y^{l}}({\vec {y}})=\sum _{}p_{X^{l}}({\vec {x}})p_{K^{l}}({\vec {k}})$, где сумма ведётся по всем ${\vec {x}}$ и ${\vec {k}}$ таким, что $e_{\vec {k}}({\vec {x}})={\bigl (}e_{k_{1}}(x_{1}),...,e_{k_{l}}(x_{l}){\bigr )}^{T}={\vec {y}}$.

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

Учитывая, что не каждая комбинация символов длины $l$ из алфавита $X$ может появиться в открытом тексте, введём: $X^{(l)}=\{{\vec {x}}:p_{X^{l}}({\vec {x}})>0\},Y^{(l)}=\{{\vec {y}}:p_{Y^{l}}({\vec {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}}({\vec {k}})>0,\forall {\vec {k}}\in K^{l}$.

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

Пусть ${\tilde {K}}$ — конечное множество некоторых ключей (некоторых наборов натуральных чисел). Длина ключа из ${\tilde {K}}$ может быть меньше $l$. Для каждого ключа из ${\tilde {K}}$ можно задать правило детерминированного построения ключевого потока ${\vec {k}}=(k_{1},...,k_{l})^{T}\in K^{l}$. Полученный таким образом набор ключевых потоков для всех ключей из ${\tilde {K}}$ обозначим $K^{(l)}$. Например, для ключа $(k_{1},...,k_{p})^{T}\in {\tilde {K}},1<p<l$ в качестве ключевого потока можно взять периодическое повторение этого ключа $(k_{1},...,k_{p},k_{1},...,k_{p},...)^{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)}}({\vec {x}}|{\vec {y}})$ — вероятность, что было зашифровано сообщение ${\vec {x}}\in X^{(l)}$ при регистрации шифротекста ${\vec {y}}\in Y^{(l)}$. Шифр называется абсолютно стойким, если выполнено:

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

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

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

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

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

Условная вероятность для шифра с ограниченным ключом:

$p_{Y^{(l)}|X^{(l)}}({\vec {y}}|{\vec {x}})=\sum _{{\vec {k}}\in K^{(l)}({\vec {x}},{\vec {y}})}p_{K^{(l)}}({\vec {k}})$, где $K^{(l)}({\vec {x}},{\vec {y}})=\{{\vec {k}}\in K^{(l)}:e_{k_{i}}(x_{i})=y_{i},i={\overline {1,l}}\}$.

Покажем, что для совершенного шифра верно: $|K^{(l)}({\vec {x}},{\vec {y}})|\geq 1$ $\forall {\vec {x}}\in X^{(l)},\forall {\vec {y}}\in Y^{(l)},\forall l\in \mathbb {N}$. Действительно, если бы $|K^{(l)}({\vec {x}},{\vec {y}})|=0$ при некоторых ${\vec {x}}$ и ${\vec {y}}$, то $p_{Y^{(l)}|X^{(l)}}({\vec {y}}|{\vec {x}})=0$. Так как $p_{X^{(l)}|Y^{(l)}}({\vec {x}}|{\vec {y}})={\frac {p_{X^{(l)}}({\vec {x}})\cdot p_{Y^{(l)}|X^{(l)}}({\vec {y}}|{\vec {x}})}{p_{Y^{(l)}}({\vec {y}})}}$, то $p_{X^{(l)}}({\vec {x}})=0$ ( $p_{X^{(l)}|Y^{(l)}}({\vec {x}}|{\vec {y}})=p_{X^{(l)}}({\vec {x}})$ по определению абсолютной стойкости), что противоречит определению шифра с ограниченным ключом.

Теперь можно утверждать, что для совершенного шифра $|K^{(l)}|\geqslant |Y^{(l)}|$, так как для любого фиксированного ${\vec {x}}$ существует ключ ${\vec {k}}$ такой, что $e_{\vec {k}}({\vec {x}})={\vec {y}}$. Но это неравенство невозможно $\forall l\in \mathbb {N}$, так как множество ${\tilde {K}}$ конечно, а $|Y^{(l)}|$ неограниченно возрастает при росте $l$ , ведь $|Y^{(l)}|\geqslant |X^{(l)}|,$ $|X^{(l+1)}|>|X^{(l)}|$.

Если шифр совершенный, то $|X|\leq |Y|\leq |K|$.

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

Если провести рассуждения, аналогичные доказательству предыдущего свойства, но вместо множества $K^{(l)}({\vec {x}},{\vec {y}})$ использовать $K^{l}({\vec {x}},{\vec {y}})=\{{\vec {k}}\in K^{l}:e_{k_{i}}(x_{i})=y_{i},i={\overline {1,l}}\}$, то также получим: $|K^{(l)}|\geqslant |Y^{(l)}|$. Но в этом случае у нас нет ограничения на мощность множества $K^{(l)}$. По первому свойству неравенство будет выполняться и при $l=1$.

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

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

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

$1.$ $|K(x,y)|=1$ $\forall x\in X,\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|}}$ $\forall k\in K$, то есть ключи должны быть равновероятны.

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

$(\Rightarrow 1)$

Так как $|Y|=|K|$, то из $|K(x,y)|\geq 1$ следует, что при $k_{1}\neq k_{2}$следует $e_{k_{1}}(x)\neq e_{k_{2}}(x)$ $\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)$ $\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}$	$...$	$x_{|X|}$
$k_{1}$	$e_{k_{1}}(x_{1})$	$...$	$e_{k_{1}}(x_{|X|})$
$...$	$...$	$...$	$...$
$k_{|X|}$	$e_{k_{|X|}}(x_{1})$	$...$	$e_{k_{|X|}}(x_{|X|})$

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

Замечание

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

$X=\{x_{1},x_{2}\},Y=\{1,2,3\},K=\{k_{1},..,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'}p(x')p(y|x')}}={\frac {p(x)\sum _{k}p(k)}{\sum _{x',k\in K(x',y)}p(x')p(k)}}$ .

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

См. также

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

Литература

• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
• К. Шеннон. Теория связи в секретных системах // Работы по теории информации и кибернетике / Перевод С. Карпова. — М.: ИЛ, 1963. — С. 243—322. — 830 с. Архивировано 22 декабря 2014 года.
• Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры. М..: Гелиос АРВ, 2005. — 160 с.