WikiSort.ru - Не сортированное

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

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

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

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

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

Опорный шифр замены — совокупность ${\displaystyle S=(X,K,Y,E,D)}$ .

${\displaystyle P(X^{l})=\{p_{X^{l}}({\overrightarrow {x}}),{\overrightarrow {x}}\in X^{l}\}}$ — распределение вероятностей для открытого текста, ${\displaystyle P(K^{l})=\{p_{K^{l}}({\overrightarrow {k}}),{\overrightarrow {k}}\in K^{l}\}}$ — для комбинации номеров отображений, ${\displaystyle P(Y^{l})=\{p_{Y^{l}}({\overrightarrow {y}}),{\overrightarrow {y}}\in Y^{l}\}}$ — для шифротекста, где ${\displaystyle X^{l},K^{l},Y^{l}}$ — декартовы степени множеств ${\displaystyle X,K,Y}$ .

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

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

• ${\displaystyle E^{(l)}=\{e_{\overrightarrow {k}}=e_{k_{1}}(x_{1})...e_{k_{l}}(x_{l})\in Y^{l},{\overrightarrow {k}}\in K^{l}\},}$ ${\displaystyle D^{(l)}=\{d_{\overrightarrow {k}}=d_{k_{1}}(y_{1})...d_{k_{l}}(y_{l})\in X^{l},{\overrightarrow {k}}\in K^{l}\}}$ ${\displaystyle {\overrightarrow {k}}=k_{1}...k_{l},e_{k_{i}}\in E,x_{i}\in X,d_{k_{i}}\in D,y_{i}\in e_{i}(X),i={\overline {1,l}}}$

• ${\displaystyle p_{X^{(l)}}({\overrightarrow {x}})>0,\forall {\overrightarrow {x}}\in X^{(l)}}$

• ${\displaystyle p_{K^{l}}({\overrightarrow {k}})>0,\forall {\overrightarrow {k}}\in K^{l}}$ .

Введём конечное множество ${\displaystyle K^{(l)}=\{f({\boldsymbol {k}},l),{\boldsymbol {k}}\in {\boldsymbol {K}}\}}$ , где ${\displaystyle {\boldsymbol {K}}}$ — конечное множество ключей шифра, ${\displaystyle f({\boldsymbol {k}},l)=k_{1}...k_{l}}$ — ключевой поток, отвечающий ключу ${\displaystyle {\boldsymbol {k}}}$ и числу ${\displaystyle l}$ .

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

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

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

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

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

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

Шифр замены с неограниченным ключом ${\displaystyle S_{H}}$ является совершенным, если и только если опорный шифр ${\displaystyle S_{H}^{(l)}}$ — совершенный.

Это утверждение следует из определения абсолютной стойкости. Поэтому далее для шифров с неограниченным ключом можем рассматривать лишь их опорные шифры.

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

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

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

Общий вид

Исходя из теоремы Шеннона, правило шифрования опорного шифра замены ${\displaystyle S}$ , у которого ${\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}$

См. также

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

Литература

• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
  <a href='https://wikidata.org/wiki/Track:Q4130888'></a><a href='https://wikidata.org/wiki/Track:Q26887236'></a><a href='https://wikidata.org/wiki/Track:Q26887244'></a><a href='https://wikidata.org/wiki/Track:Q26887242'></a>
• К. Шеннон. Теория связи в секретных системах // Работы по теории информации и кибернетике / Перевод С. Карпова. — М.: ИЛ, 1963. — С. 243-322. — 830 с.
• Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры. М..: Гелиос АРВ, 2005. — 160 с.