Абсолютно стойкий шифр — шифр, характеризующийся тем, что криптоаналитик принципиально не сможет извлечь статистическую информацию относительно выбираемых ключей из перехватываемого шифротекста .
Математически понятие абсолютно стойкого шифра было введено Клодом Шенноном в 1945 году в работе «Математическая теория криптографии».
Пусть X {\displaystyle X} и Y {\displaystyle Y} — алфавиты открытого и шифрованного текста такие, что | X | > 1 , {\displaystyle |X|>1,} | Y | > 1 , {\displaystyle |Y|>1,} | Y | ≥ | X | {\displaystyle |Y|\geq |X|} .
Шифрование задаётся инъективным отображением e k : X → Y {\displaystyle e_{k}:X\rightarrow Y} , дешифрование — отображением d k : e k ( X ) → X , {\displaystyle d_{k}:e_{k}(X)\rightarrow X,} k ∈ K = { 1 , 2 , . . . , n } {\displaystyle k\in K=\{1,2,...,n\}} .
E = { e k , k ∈ K } , D = { d k , k ∈ K } {\displaystyle E=\{e_{k},k\in K\},D=\{d_{k},k\in K\}} — наборы правил шифрования и дешифрования.
Максимальное число | E | = n {\displaystyle |E|=n} возможных отображений равно количеству размещений из | Y | {\displaystyle |Y|} по | X | {\displaystyle |X|} (числу способов выбрать подмножества размером | X | {\displaystyle |X|} в множестве Y {\displaystyle Y} , учитывая порядок элементов).
Возникновение очередного символа x ∈ X {\displaystyle x\in X} , выбор ключа k ∈ K {\displaystyle k\in K} (то есть выбор отображения e k {\displaystyle e_{k}} ), получение шифротекста y ∈ Y {\displaystyle y\in Y} реализуются с некоторыми вероятностями:
P ( X l ) = { p X l ( x → ) , x → ∈ X l } {\displaystyle P(X^{l})=\{p_{X^{l}}({\vec {x}}),{\vec {x}}\in X^{l}\}} — распределение вероятностей для открытого текста,
P ( K l ) = { p K l ( k → ) , k → ∈ K l } {\displaystyle P(K^{l})=\{p_{K^{l}}({\vec {k}}),{\vec {k}}\in K^{l}\}} — распределение вероятностей для комбинации номеров отображений,
P ( Y l ) = { p Y l ( y → ) , y → ∈ Y l } {\displaystyle P(Y^{l})=\{p_{Y^{l}}({\vec {y}}),{\vec {y}}\in Y^{l}\}} — распределение вероятностей для шифротекста, где
X l , K l , Y l {\displaystyle X^{l},K^{l},Y^{l}} — декартовы степени множеств X , K , Y {\displaystyle X,K,Y} , l {\displaystyle l} — количество символов в открытом тексте.
Будем считать, что случайные величины, соответствующие появлению открытого текста x → {\displaystyle {\vec {x}}} и ключа k → {\displaystyle {\vec {k}}} , независимыми . Тогда:
p Y l ( y → ) = ∑ p X l ( x → ) p K l ( k → ) {\displaystyle p_{Y^{l}}({\vec {y}})=\sum _{}p_{X^{l}}({\vec {x}})p_{K^{l}}({\vec {k}})} , где сумма ведётся по всем x → {\displaystyle {\vec {x}}} и k → {\displaystyle {\vec {k}}} таким, что e k → ( x → ) = ( e k 1 ( x 1 ) , . . . , e k l ( x l ) ) T = y → {\displaystyle e_{\vec {k}}({\vec {x}})={\bigl (}e_{k_{1}}(x_{1}),...,e_{k_{l}}(x_{l}){\bigr )}^{T}={\vec {y}}} .
E l , D l {\displaystyle E^{l},D^{l}} — множества правил шифрования и дешифрования (декартовы степени множеств E , D {\displaystyle E,D} ).
Учитывая, что не каждая комбинация символов длины l {\displaystyle l} из алфавита X {\displaystyle X} может появиться в открытом тексте, введём: X ( l ) = { x → : p X l ( x → ) > 0 } , Y ( l ) = { y → : p Y l ( y → ) > 0 } {\displaystyle 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 ∈ N } {\displaystyle S_{H}=\{S_{H}^{(l)},l\in \mathbb {N} \}} , где S H ( l ) {\displaystyle S_{H}^{(l)}} — представляет собой совокупность X ( l ) , K l , Y ( l ) , E l , D l , P ( X ( l ) ) , P ( K l ) , P ( Y ( l ) ) {\displaystyle X^{(l)},K^{l},Y^{(l)},E^{l},D^{l},P(X^{(l)}),P(K^{l}),P(Y^{(l)})} , при этом p K l ( k → ) > 0 , ∀ k → ∈ K l {\displaystyle p_{K^{l}}({\vec {k}})>0,\forall {\vec {k}}\in K^{l}} .
Длина ключа шифра замены с неограниченным ключом совпадает с размером открытого текста l {\displaystyle l} .
Пусть K ~ {\displaystyle {\tilde {K}}} — конечное множество некоторых ключей (некоторых наборов натуральных чисел). Длина ключа из K ~ {\displaystyle {\tilde {K}}} может быть меньше l {\displaystyle l} . Для каждого ключа из K ~ {\displaystyle {\tilde {K}}} можно задать правило детерминированного построения ключевого потока k → = ( k 1 , . . . , k l ) T ∈ K l {\displaystyle {\vec {k}}=(k_{1},...,k_{l})^{T}\in K^{l}} . Полученный таким образом набор ключевых потоков для всех ключей из K ~ {\displaystyle {\tilde {K}}} обозначим K ( l ) {\displaystyle K^{(l)}} . Например, для ключа ( k 1 , . . . , k p ) T ∈ K ~ , 1 < p < l {\displaystyle (k_{1},...,k_{p})^{T}\in {\tilde {K}},1<p<l} в качестве ключевого потока можно взять периодическое повторение этого ключа ( k 1 , . . . , k p , k 1 , . . . , k p , . . . ) T ∈ K l {\displaystyle (k_{1},...,k_{p},k_{1},...,k_{p},...)^{T}\in K^{l}} . Заметим, что K ( l ) ⊆ K l {\displaystyle K^{(l)}\subseteq K^{l}} .
Шифр замены с ограниченным ключом — семейство шифров S O = { S O ( l ) , l ∈ N } {\displaystyle S_{O}=\{S_{O}^{(l)},l\in \mathbb {N} \}} , где S O ( l ) {\displaystyle S_{O}^{(l)}} есть та же совокупность, что и для определённого выше шифра с неограниченным ключом, в которой вместо K l {\displaystyle K^{l}} и P ( K l ) {\displaystyle P(K^{l})} используется множество K ( l ) {\displaystyle K^{(l)}} и распределение P ( K ( l ) ) {\displaystyle P(K^{(l)})} .
Пусть p X ( l ) | Y ( l ) ( x → | y → ) {\displaystyle p_{X^{(l)}|Y^{(l)}}({\vec {x}}|{\vec {y}})} — вероятность, что было зашифровано сообщение x → ∈ X ( l ) {\displaystyle {\vec {x}}\in X^{(l)}} при регистрации шифротекста y → ∈ Y ( l ) {\displaystyle {\vec {y}}\in Y^{(l)}} . Шифр называется абсолютно стойким, если выполнено:
p X ( l ) | Y ( l ) ( x → | y → ) = p X ( l ) ( x → ) {\displaystyle p_{X^{(l)}|Y^{(l)}}({\vec {x}}|{\vec {y}})=p_{X^{(l)}}({\vec {x}})} ∀ x → ∈ X ( l ) , ∀ y → ∈ Y ( l ) , ∀ l ∈ N {\displaystyle \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 ) ( x → | y → ) , x ∈ X ( l ) , y ∈ Y ( l ) } {\displaystyle 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 ) ) {\displaystyle P(X^{(l)})} . В терминах теории информации это означает, что условная энтропия сообщения при известном шифрованном тексте равна безусловной. Знание шифротекста y → {\displaystyle {\vec {y}}} не даёт криптоаналитику никакого полезного знания для получения x → {\displaystyle {\vec {x}}} (расшифровка возможна только полным перебором ).
Никакой шифр с ограниченным ключом S O {\displaystyle S_{O}} не является совершенным.
Условная вероятность для шифра с ограниченным ключом:
p Y ( l ) | X ( l ) ( y → | x → ) = ∑ k → ∈ K ( l ) ( x → , y → ) p K ( l ) ( k → ) {\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}})} , где K ( l ) ( x → , y → ) = { k → ∈ K ( l ) : e k i ( x i ) = y i , i = 1 , l ¯ } {\displaystyle K^{(l)}({\vec {x}},{\vec {y}})=\{{\vec {k}}\in K^{(l)}:e_{k_{i}}(x_{i})=y_{i},i={\overline {1,l}}\}} .
Покажем, что для совершенного шифра верно: | K ( l ) ( x → , y → ) | ≥ 1 {\displaystyle |K^{(l)}({\vec {x}},{\vec {y}})|\geq 1} ∀ x → ∈ X ( l ) , ∀ y → ∈ Y ( l ) , ∀ l ∈ N {\displaystyle \forall {\vec {x}}\in X^{(l)},\forall {\vec {y}}\in Y^{(l)},\forall l\in \mathbb {N} } . Действительно, если бы | K ( l ) ( x → , y → ) | = 0 {\displaystyle |K^{(l)}({\vec {x}},{\vec {y}})|=0} при некоторых x → {\displaystyle {\vec {x}}} и y → {\displaystyle {\vec {y}}} , то p Y ( l ) | X ( l ) ( y → | x → ) = 0 {\displaystyle p_{Y^{(l)}|X^{(l)}}({\vec {y}}|{\vec {x}})=0} . Так как p X ( l ) | Y ( l ) ( x → | y → ) = p X ( l ) ( x → ) ⋅ p Y ( l ) | X ( l ) ( y → | x → ) p Y ( l ) ( y → ) {\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}})}}} , то p X ( l ) ( x → ) = 0 {\displaystyle p_{X^{(l)}}({\vec {x}})=0} ( p X ( l ) | Y ( l ) ( x → | y → ) = p X ( l ) ( x → ) {\displaystyle p_{X^{(l)}|Y^{(l)}}({\vec {x}}|{\vec {y}})=p_{X^{(l)}}({\vec {x}})} по определению абсолютной стойкости), что противоречит определению шифра с ограниченным ключом.
Теперь можно утверждать, что для совершенного шифра | K ( l ) | ⩾ | Y ( l ) | {\displaystyle |K^{(l)}|\geqslant |Y^{(l)}|} , так как для любого фиксированного x → {\displaystyle {\vec {x}}} существует ключ k → {\displaystyle {\vec {k}}} такой, что e k → ( x → ) = y → {\displaystyle e_{\vec {k}}({\vec {x}})={\vec {y}}} . Но это неравенство невозможно ∀ l ∈ N {\displaystyle \forall l\in \mathbb {N} } , так как множество K ~ {\displaystyle {\tilde {K}}} конечно, а | Y ( l ) | {\displaystyle |Y^{(l)}|} неограниченно возрастает при росте l {\displaystyle l} , ведь | Y ( l ) | ⩾ | X ( l ) | , {\displaystyle |Y^{(l)}|\geqslant |X^{(l)}|,} | X ( l + 1 ) | > | X ( l ) | {\displaystyle |X^{(l+1)}|>|X^{(l)}|} .
Если шифр совершенный, то | X | ≤ | Y | ≤ | K | {\displaystyle |X|\leq |Y|\leq |K|} .
Если провести рассуждения, аналогичные доказательству предыдущего свойства, но вместо множества K ( l ) ( x → , y → ) {\displaystyle K^{(l)}({\vec {x}},{\vec {y}})} использовать K l ( x → , y → ) = { k → ∈ K l : e k i ( x i ) = y i , i = 1 , l ¯ } {\displaystyle K^{l}({\vec {x}},{\vec {y}})=\{{\vec {k}}\in K^{l}:e_{k_{i}}(x_{i})=y_{i},i={\overline {1,l}}\}} , то также получим: | K ( l ) | ⩾ | Y ( l ) | {\displaystyle |K^{(l)}|\geqslant |Y^{(l)}|} . Но в этом случае у нас нет ограничения на мощность множества K ( l ) {\displaystyle K^{(l)}} . По первому свойству неравенство будет выполняться и при l = 1 {\displaystyle l=1} .
Шифр с неограниченным ключом S H {\displaystyle S_{H}} , у которого | X | = | Y | = | K | {\displaystyle |X|=|Y|=|K|} является совершенным тогда и только тогда, когда:
1. {\displaystyle 1.} | K ( x , y ) | = 1 {\displaystyle |K(x,y)|=1} ∀ x ∈ X , ∀ y ∈ Y {\displaystyle \forall x\in X,\forall y\in Y} , где K ( x , y ) = { k ∈ K : e k ( x ) = y } {\displaystyle K(x,y)=\{k\in K:e_{k}(x)=y\}} , то есть для любого x {\displaystyle x} и любого y {\displaystyle y} существует только один ключ k {\displaystyle k} такой, что e k ( x ) = y {\displaystyle e_{k}(x)=y} ;
2. {\displaystyle 2.} p K ( k ) ≡ p ( k ) = 1 | K | {\displaystyle p_{K}(k)\equiv p(k)={\frac {1}{|K|}}} ∀ k ∈ K {\displaystyle \forall k\in K} , то есть ключи должны быть равновероятны.
( ⇒ 1 ) {\displaystyle (\Rightarrow 1)}
Так как | Y | = | K | {\displaystyle |Y|=|K|} , то из | K ( x , y ) | ≥ 1 {\displaystyle |K(x,y)|\geq 1} следует, что при k 1 ≠ k 2 {\displaystyle k_{1}\neq k_{2}} следует e k 1 ( x ) ≠ e k 2 ( x ) {\displaystyle e_{k_{1}}(x)\neq e_{k_{2}}(x)} ∀ x ∈ X {\displaystyle \forall x\in X} .
( ⇒ 2 ) {\displaystyle (\Rightarrow 2)}
Занумеруем ключи следующим образом при фиксированном y {\displaystyle y} : e k j ( x j ) = y , j = 1 , | X | ¯ {\displaystyle e_{k_{j}}(x_{j})=y,j={\overline {1,|X|}}} . Получим:
p ( x j ) = p ( x j | y ) = p ( y | x j ) ⋅ p ( x j ) p ( y ) = p ( k j ) ⋅ p ( x j ) p ( y ) ⇒ p ( k j ) = p ( y ) {\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)} ∀ j = 1 , | X | ¯ {\displaystyle \forall j={\overline {1,|X|}}} .
( ⇐ 1 , 2 ) {\displaystyle (\Leftarrow 1,2)}
Используем ту же нумерацию, что и в предыдущем пункте, считая y {\displaystyle y} фиксированным. Применяя 1 {\displaystyle 1} :
p ( y ) = ∑ ( x j , k j ) : e k j ( x j ) = y p ( x j ) ⋅ p ( k j ) = 1 N ⋅ ∑ j = 1 N p ( x j ) = 1 N {\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}}} . Применяя 1 {\displaystyle 1} и 2 {\displaystyle 2} :
p ( x j | y ) = p ( x j ) ⋅ p ( y | x j ) p ( y ) = p ( x j ) {\displaystyle p(x_{j}|y)={\frac {p(x_{j})\cdot p(y|x_{j})}{p(y)}}=p(x_{j})} . Получили определение абсолютной стойкости.
Исходя из теоремы Шеннона, правило шифрования шифра замены S H ( l ) {\displaystyle S_{H}^{(l)}} при l = 1 {\displaystyle l=1} , у которого | X | = | Y | = | K | {\displaystyle |X|=|Y|=|K|} , можно представить в виде латинского квадрата :
K / X {\displaystyle K/X} x 1 {\displaystyle x_{1}} . . . {\displaystyle ...} x | X | {\displaystyle x_{|X|}} k 1 {\displaystyle k_{1}} e k 1 ( x 1 ) {\displaystyle e_{k_{1}}(x_{1})} . . . {\displaystyle ...} e k 1 ( x | X | ) {\displaystyle e_{k_{1}}(x_{|X|})} . . . {\displaystyle ...} . . . {\displaystyle ...} . . . {\displaystyle ...} . . . {\displaystyle ...} k | X | {\displaystyle k_{|X|}} e k | X | ( x 1 ) {\displaystyle e_{k_{|X|}}(x_{1})} . . . {\displaystyle ...} e k | X | ( x | X | ) {\displaystyle e_{k_{|X|}}(x_{|X|})}
При равновероятном использовании k 1 , . . . , k | X | {\displaystyle k_{1},...,k_{|X|}} система будет обладать абсолютной стойкостью. Практической реализацией такой системы, например, является шифр Вернама .
Существуют абсолютно стойкие шифры, для которых количество символов в алфавите | X | {\displaystyle |X|} открытого текста меньше | Y | {\displaystyle |Y|} . Например:
X = { x 1 , x 2 } , Y = { 1 , 2 , 3 } , K = { k 1 , . . , k 6 } {\displaystyle X=\{x_{1},x_{2}\},Y=\{1,2,3\},K=\{k_{1},..,k_{6}\}}
K / X {\displaystyle K/X} x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} k 1 , p ( k 1 ) = 19 80 {\displaystyle k_{1},p(k_{1})={\frac {19}{80}}} 1 {\displaystyle 1} 2 {\displaystyle 2} k 2 , p ( k 2 ) = 3 20 {\displaystyle k_{2},p(k_{2})={\frac {3}{20}}} 1 {\displaystyle 1} 3 {\displaystyle 3} k 3 , p ( k 3 ) = 21 80 {\displaystyle k_{3},p(k_{3})={\frac {21}{80}}} 2 {\displaystyle 2} 1 {\displaystyle 1} k 4 , p ( k 4 ) = 1 10 {\displaystyle k_{4},p(k_{4})={\frac {1}{10}}} 2 {\displaystyle 2} 3 {\displaystyle 3} k 5 , p ( k 5 ) = 1 8 {\displaystyle k_{5},p(k_{5})={\frac {1}{8}}} 3 {\displaystyle 3} 1 {\displaystyle 1} k 6 , p ( k 6 ) = 1 8 {\displaystyle k_{6},p(k_{6})={\frac {1}{8}}} 3 {\displaystyle 3} 2 {\displaystyle 2}
Абсолютная стойкость данного шифра легко проверяется по определению по формуле: p ( x | y ) = p ( y | x ) p ( x ) ∑ x ′ p ( x ′ ) p ( y | x ′ ) = p ( x ) ∑ k p ( k ) ∑ x ′ , k ∈ K ( x ′ , y ) p ( x ′ ) p ( k ) {\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)}}} .
Этот шифр остаётся абсолютно стойким для любого распределения P ( X ) {\displaystyle P(X)} .