Cifru absolut puternic

Un cifr absolut puternic este un cifr caracterizat prin faptul că criptoanalistul nu poate extrage în mod fundamental informații statistice cu privire la cheile alese din textul cifrat interceptat .

Din punct de vedere matematic, conceptul de cifru absolut sigur a fost introdus de Claude Shannon în 1945 în lucrarea sa „The Mathematical Theory of Cryptography”.

Concepte auxiliare

Fie și să fie alfabetul text simplu și text cifrat astfel încât . $X$ $Y$ $|X|>1,$ $|Y|>1,$ $|Y|\geq |X|$

Criptarea este dată printr -o mapare injectivă , decriptarea printr-o mapare . $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\)$ - seturi de reguli de criptare și decriptare.

Numărul maxim de mapări posibile este egal cu numărul de aranjamente de la by (numărul de moduri de a selecta subseturi de mărime din set , dată fiind ordinea elementelor). $|E|=n$ $|Y|$ $|X|$ $|X|$ $Y$

Apariția următorului caracter , alegerea cheii (adică alegerea afișajului ), primirea textului cifrat sunt implementate cu unele probabilități: $x\în X$ $k\în K$ $e_{k}$ $y\în Y$

$P(X^{l})=\{p_{X^{l}}({\vec {x}}),{\vec {x}}\in X^{l}}\}$ este distribuția de probabilitate pentru textul simplu,

$P(K^{l})=\{p_{K^{l}}({\vec {k}}),{\vec {k}}\in K^{l}}\}$ este distribuția de probabilitate pentru combinația de numere afișate,

$P(Y^{l})=\{p_{Y^{l}}({\vec {y}}), {\vec {y}}\in Y^{l}}\}$ este distribuția de probabilitate pentru textul cifrat, unde

$X^{l},K^{l},Y^{l}$ sunt puterile carteziene ale mulțimilor , este numărul de caractere din textul simplu. $X,K,Y$ $l$

Vom presupune că variabilele aleatoare corespunzătoare aspectului textului simplu și cheii sunt independente . Apoi: ${\vec {x}}$ $\vec{k}$

$p_{Y^{l}}({\vec {y}})=\sum _{}p_{X^{l}}({\vec {x}})p_{K^{l} }({\vec {k)))$ , unde suma este peste toate și astfel încât . ${\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}$ — seturi de reguli de criptare și decriptare (puterile carteziane ale seturilor ). $E,D$

Având în vedere că nu orice combinație de caractere de lungime din alfabet poate apărea în text simplu, să introducem: . $l$ $X$ $X^{(l)}=\{{\vec {x}}:p_{X^{l}}({\vec {x}})>0\},Y^{(l)} =\{{\vec {y}}:p_{Y^{l}}({\vec {y}})>0\}$

Un cifr de substituție cu o cheie nelimitată este o familie de cifruri , unde este un set de , în timp ce . $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}$

Lungimea cheii a unui cifr de înlocuire a cheii fără restricții este aceeași cu dimensiunea textului simplu . $l$

Să fie un set finit de chei (unele colecții de numere naturale). Lungimea cheii de la poate fi mai mică de . Pentru fiecare cheie din aceasta este posibilă setarea regulii de construcție deterministă a fluxului de chei . Setul de fluxuri de chei obținute în acest fel pentru toate cheile de la este notat cu . De exemplu, pentru o cheie , o repetare periodică a acestei chei poate fi luată ca flux de chei . Rețineți că . ${\tilde {K}}$ ${\tilde {K}}$ $l$ ${\tilde {K}}$ ${\vec {k}}=(k_{1},...,k_{l})^{T}\în 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}\în K^{l)$ $K^{(l)}\subseteq K^{l)$

Un cifr de substituție cu o cheie limitată este o familie de cifruri în care există același set ca și pentru cifrul cu o cheie nelimitată definit mai sus, în care setul și distribuția sunt utilizate în loc de și . $S_{O}=\{S_{O}^{(l)},l\in \mathbb {N} \)$ $S_{O}^{(l))$ $K^{l)$ $P(K^{l})$ $K^{(l)}$ $P(K^{(l)})$

Definiție formală

Fie probabilitatea ca mesajul să fi fost criptat la înregistrarea textului cifrat . Se spune că un cifr este absolut sigur dacă: $p_{X^{(l)}|Y^{(l)))({\vec {x}}|{\vec {y))}$ ${\vec {x}}\in X^{(l))$ ${\vec {y}}\în 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 }$ .

Cu alte cuvinte, distribuția de probabilitate posterioară este aceeași cu distribuția anterioară . Din punct de vedere al teoriei informațiilor, aceasta înseamnă că entropia condiționată a unui mesaj cu un text cifrat cunoscut este egală cu cea necondiționată. Cunoașterea textului cifrat nu oferă criptoanalistului nicio cunoaștere utilă de obținut (decriptarea este posibilă numai prin căutare exhaustivă ). $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}}$

Proprietăți de bază

Nici o cheie limitată nu este perfectă. $S_{O}$

Dovada

Probabilitate condiționată pentru un cifru cheie limitat:

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

Să arătăm că pentru un cifr perfect este adevărat: . Într-adevăr, dacă pentru unii și , atunci . Din moment ce , atunci ( prin definiția securității absolute), ceea ce contrazice definiția unui cifr cu o cheie limitată. $|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)))$

Acum se poate argumenta că pentru un cifr perfect , deoarece pentru orice cifr fix există o cheie astfel încât . Dar această inegalitate este imposibilă , deoarece mulțimea este finită, dar crește la infinit odată cu creșterea , deoarece . $|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)}|$

Dacă cifrul este perfect, atunci . $|X|\leq |Y|\leq |K|$

Dovada

Dacă realizăm argumente similare cu demonstrația proprietății anterioare, dar folosim în loc de o mulțime , atunci obținem și: . Dar în acest caz nu avem nicio restricție asupra cardinalității mulțimii . Conform primei proprietăți, inegalitatea va fi valabilă și pentru . $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$

Teorema lui Shannon

Formulare

Un cifru cheie nerestricționat care este perfect dacă și numai dacă: $S_{H}$ $|X|=|Y|=|K|$

$unu.$ $|K(x,y)|=1$ $\forall x\in X,\forall y\in Y$ , unde , adică pentru orice și orice există o singură cheie astfel încât ; $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$ , adică cheile trebuie să fie la fel de probabile.

Dovada

$(\Rightarrow 1)$

Din moment ce rezultă că urmează . $|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)$

Enumerăm cheile după cum urmează pentru un fix : . Primim: $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)$

Folosim aceeași numerotare ca în paragraful anterior, considerând fixă. Aplicare : $y$ $unu$

$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}}$ . Aplicarea și : $unu$ $2$

$p(x_{j}|y)={\frac {p(x_{j})\cdot p(y|x_{j})}{p(y)))=p(x_{j} )$ . Definiția primită a fermității absolute.

Vedere generală

Pe baza teoremei lui Shannon, regula de criptare pentru un cifr de substituție pentru , pentru care , poate fi reprezentată ca un pătrat latin : $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\|})$

Cu o utilizare echiprobabilă, sistemul va avea o stabilitate absolută. O implementare practică a unui astfel de sistem, de exemplu, este cifrul Vernam . $k_{1},...,k_{|X|}$

Notă

Există cifruri absolut puternice pentru care numărul de caractere din alfabetul text simplu este mai mic de . De exemplu: $|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))$	$unu$	$2$
$k_{2},p(k_{2})={\frac {3}{20))$	$unu$	$3$
$k_{3},p(k_{3})={\frac {21}{80))$	$2$	$unu$
$k_{4},p(k_{4})={\frac {1}{10))$	$2$	$3$
$k_{5},p(k_{5})={\frac {1}{8)}$	$3$	$unu$
$k_{6},p(k_{6})={\frac {1}{8)}$	$3$	$2$

Puterea absolută a acestui cifr este ușor de verificat prin definiție folosind formula: . $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)))$

Acest cifru rămâne absolut sigur pentru orice distribuție . $P(X)$

Vezi și

Literatură

Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
K. Shannon. Teoria comunicării în sisteme secrete // Lucrări despre teoria informaţiei şi cibernetică / Traducere de S. Karpov. - M. : IL, 1963. - S. 243-322. — 830 p. Arhivat pe 22 decembrie 2014 la Wayback Machine
Zubov A.Yu. Metode criptografice de protecție a informațiilor. Cifre perfecte. M. .: Helios ARV, 2005. - 160 p.