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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle (\Rightarrow 1)}$

Так как ${\displaystyle |Y|=|K|}$ , то из ${\displaystyle |K(x,y)|\geq 1}$ следует, что при ${\displaystyle k_{1}\neq k_{2}}$ следует ${\displaystyle e_{k_{1}}(x)\neq e_{k_{2}}(x)}$ ${\displaystyle \forall x\in X}$ .

${\displaystyle (\Rightarrow 2)}$

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

${\displaystyle 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)}$ ${\displaystyle \forall j={\overline {1,|X|}}}$ .

${\displaystyle (\Leftarrow 1,2)}$

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

${\displaystyle 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}}}$ . Применяя ${\displaystyle 1}$ и ${\displaystyle 2}$ :

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

Общий вид

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

${\displaystyle K/X}$	${\displaystyle x_{1}}$	${\displaystyle ...}$	${\displaystyle x_{|X|}}$
${\displaystyle k_{1}}$	${\displaystyle e_{k_{1}}(x_{1})}$	${\displaystyle ...}$	${\displaystyle e_{k_{1}}(x_{|X|})}$
${\displaystyle ...}$	${\displaystyle ...}$	${\displaystyle ...}$	${\displaystyle ...}$
${\displaystyle k_{|X|}}$	${\displaystyle e_{k_{|X|}}(x_{1})}$	${\displaystyle ...}$	${\displaystyle e_{k_{|X|}}(x_{|X|})}$

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

Замечание

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

${\displaystyle X=\{x_{1},x_{2}\},Y=\{1,2,3\},K=\{k_{1},..,k_{6}\}}$

${\displaystyle K/X}$	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$
${\displaystyle k_{1},p(k_{1})={\frac {19}{80}}}$	${\displaystyle 1}$	${\displaystyle 2}$
${\displaystyle k_{2},p(k_{2})={\frac {3}{20}}}$	${\displaystyle 1}$	${\displaystyle 3}$
${\displaystyle k_{3},p(k_{3})={\frac {21}{80}}}$	${\displaystyle 2}$	${\displaystyle 1}$
${\displaystyle k_{4},p(k_{4})={\frac {1}{10}}}$	${\displaystyle 2}$	${\displaystyle 3}$
${\displaystyle k_{5},p(k_{5})={\frac {1}{8}}}$	${\displaystyle 3}$	${\displaystyle 1}$
${\displaystyle k_{6},p(k_{6})={\frac {1}{8}}}$	${\displaystyle 3}$	${\displaystyle 2}$

Абсолютная стойкость данного шифра легко проверяется по определению по формуле: ${\displaystyle 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)}}}$ .

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

См. также

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

Литература

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