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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ p_{Y^l}(\vec{y})=\sum_{}p_{X^l}(\vec{x}) p_{K^l}(\vec{k}) }[/math], где сумма ведётся по всем [math]\displaystyle{ \vec{x} }[/math] и [math]\displaystyle{ \vec{k} }[/math] таким, что [math]\displaystyle{ e_{\vec{k}}(\vec{x})=\bigl(e_{k_1}(x_1), ..., e_{k_l}(x_l)\bigr)^T=\vec{y} }[/math].

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

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

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

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

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

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

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

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

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

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

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

Никакой шифр с ограниченным ключом [math]\displaystyle{ S_O }[/math] не является совершенным.

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

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

[math]\displaystyle{ p_{Y^{(l)}|X^{(l)}}(\vec{y}|\vec{x})=\sum_{\vec{k}\in K^{(l)}(\vec{x},\vec{y})}p_{K^{(l)}}(\vec{k}) }[/math], где [math]\displaystyle{ K^{(l)}(\vec{x},\vec{y})=\{\vec{k}\in K^{(l)}: e_{k_i}(x_i)=y_i, i=\overline{1,l}\} }[/math].

Покажем, что для совершенного шифра верно: [math]\displaystyle{ |K^{(l)}(\vec{x},\vec{y})|\geq 1 }[/math] [math]\displaystyle{ \forall \vec{x}\in X^{(l)}, \forall \vec{y}\in Y^{(l)}, \forall l\in\mathbb N }[/math]. Действительно, если бы [math]\displaystyle{ |K^{(l)}(\vec{x},\vec{y})|= 0 }[/math] при некоторых [math]\displaystyle{ \vec{x} }[/math] и [math]\displaystyle{ \vec{y} }[/math], то [math]\displaystyle{ p_{Y^{(l)}|X^{(l)}}(\vec{y}|\vec{x})=0 }[/math]. Так как [math]\displaystyle{ 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})} }[/math], то [math]\displaystyle{ p_{X^{(l)}}(\vec{x})=0 }[/math] ( [math]\displaystyle{ p_{X^{(l)}|Y^{(l)}}(\vec{x}|\vec{y})=p_{X^{(l)}}(\vec{x}) }[/math] по определению абсолютной стойкости), что противоречит определению шифра с ограниченным ключом.

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ (\Rightarrow 1) }[/math]

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

[math]\displaystyle{ (\Rightarrow 2) }[/math]

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

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

[math]\displaystyle{ (\Leftarrow 1, 2) }[/math]

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

[math]\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}^Np(x_j)=\frac{1}{N} }[/math]. Применяя [math]\displaystyle{ 1 }[/math] и [math]\displaystyle{ 2 }[/math]:

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

Общий вид

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

[math]\displaystyle{ K/X }[/math]	[math]\displaystyle{ x_1 }[/math]	[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ x_{|X|} }[/math]
[math]\displaystyle{ k_1 }[/math]	[math]\displaystyle{ e_{k_1}(x_1) }[/math]	[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ e_{k_1}(x_{|X|}) }[/math]
[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ ... }[/math]
[math]\displaystyle{ k_{|X|} }[/math]	[math]\displaystyle{ e_{k_{|X|}}(x_{1}) }[/math]	[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ e_{k_{|X|}}(x_{|X|}) }[/math]

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

Замечание

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

[math]\displaystyle{ X = \{x_1, x_2\}, Y = \{1,2,3\}, K = \{k_1,..,k_6\} }[/math]

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

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

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

См. также

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

Литература

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