Ehdottomasti vahva salaus

Ehdottoman vahva salaus on salaus, jolle on tunnusomaista se, että kryptanalyytikko ei voi pohjimmiltaan poimia tilastotietoja valituista avaimista siepatusta salatekstistä .

Matemaattisesti täysin turvallisen salauksen käsitteen esitteli Claude Shannon vuonna 1945 teoksessaan "The Mathematical Theory of Cryptography".

Apukäsitteet

Antaa ja olla selkoteksti- ja salakirjoitusaakkoset siten, että . $X$ $Y$ $|X|>1,$ $|Y|>1,$ $|Y|\geq |X|$

Salaus annetaan injektiokuvauksella , salauksen purku kartoituksella . $e_{k}:X\rightarrow Y$ $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\))$ - salaus- ja salauksenpurkusäännöt.

Mahdollisten kartoitusten enimmäismäärä on yhtä suuri kuin järjestelyjen lukumäärä joukosta (tapoja valita koon osajoukkoja joukosta elementtien järjestyksen mukaan). $|E|=n$ $|Y|$ $|X|$ $|X|$ $Y$

Seuraavan merkin esiintyminen, avaimen valinta (eli näytön valinta ), salatekstin vastaanotto toteutetaan joillakin todennäköisyyksillä: $x\in X$ $k\in K$ $e_{k}$ $y\in Y$

$P(X^{l})=\{p_{X^{l}}({\vec {x}}),{\vec {x}}\in X^{l}}\}$ on selväkielisen tekstin todennäköisyysjakauma ,

$P(K^{l})=\{p_{K^{l}}({\vec {k}}),{\vec {k}}\in K^{l}}\}$ on näyttönumeroiden yhdistelmän todennäköisyysjakauma,

$P(Y^{l})=\{p_{Y^{l}}({\vec {y}}),{\vec {y}}\in Y^{l}}\}$ on salatekstin todennäköisyysjakauma, jossa

${\displaystyle X^{l},K^{l},Y^{l))$ ovat sarjojen karteesiset potenssit , on selkeän tekstin merkkien lukumäärä. ${\näyttötyyli X,K,Y}$ $l$

Oletetaan, että selkeän tekstin ja avaimen ulkonäköä vastaavat satunnaismuuttujat ovat riippumattomia . Sitten: ${\vec {x}}$ $\vec{k}$

$p_{Y^{l}}({\vec {y}})=\sum _{}p_{X^{l}}({\vec {x}})p_{K^{l} }({\vec {k)))$ , jossa summa on yli kaiken ja sellainen, että . ${\vec {x}}$ $\vec{k}$ $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))$ — salaus- ja salauksenpurkusääntöjen joukot (joukkojen karteesiset potenssit ). ${\näyttötyyli E,D}$

Ottaen huomioon, että kaikki aakkosten pituusmerkkien yhdistelmät eivät voi esiintyä selkeässä tekstissä, kirjoitetaan: . $l$ $X$ $X^{(l)}=\{{\vec {x}}:p_{X^{l}}({\vec {x}})>0\},Y^{(l)} =\{{\vec {y}}:p_{Y^{l}}({\vec {y}})>0\}$

Rajattomalla avaimella varustettu korvaussalaus on salausperhe , jossa on joukko , while . ${\displaystyle S_{H}=\{S_{H}^{(l)},l\in \mathbb {N} \))$ ${\displaystyle S_{H}^{(l)))$ ${\näyttötyyli 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}$

Rajoittamattoman avaimen korvaavan salauksen avaimen pituus on sama kuin tavallisen tekstin koko . $l$

Antaa olla rajallinen joukko avaimia (jotkut luonnollisten lukujen kokoelmat). Avaimen pituus alkaen voi olla pienempi kuin . Jokaiselle avaimelle on mahdollista asettaa avainvirran deterministisen rakentamisen sääntö . Tällä tavalla saatu avainvirtojen joukko kaikille avaimille lähteestä on merkitty . Esimerkiksi avaimelle tämän avaimen säännöllinen toisto voidaan pitää avainvirtana . Huomaa, että . ${\tilde {K}}$ ${\tilde {K}}$ $l$ ${\tilde {K}}$ ${\vec {k}}=(k_{1},...,k_{l})^{T}\in K^{l}$ ${\tilde {K}}$ $K^{(l)}$ $(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))$

Rajoitetun avaimen korvaava salaus on salausperhe, jossa on sama joukko kuin edellä määritellyllä rajoittamattomalla avaimella varustetulla salauksella, jossa joukkoa ja jakelua käytetään ja sijaan . ${\displaystyle S_{O}=\{S_{O}^{(l)},l\in \mathbb {N} \))$ ${\displaystyle S_{O}^{(l)))$ ${\displaystyle K^{l))$ $P(K^{l})$ $K^{(l)}$ $P(K^{(l)})$

Muodollinen määritelmä

Olkoon todennäköisyys, että viesti salattiin salatekstiä rekisteröitäessä . Salauksen sanotaan olevan täysin turvallinen, jos: $p_{X^{(l)}|Y^{(l)))({\vec {x}}|{\vec {y)))$ ${\displaystyle {\vec {x}}\in X^{(l)))$ ${\displaystyle {\vec {y}}\in 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 }$ .

Toisin sanoen posteriori todennäköisyysjakauma on sama kuin aiempi jakauma . Tietoteorian kannalta tämä tarkoittaa, että tunnetun salatekstin sisältävän viestin ehdollinen entropia on yhtä suuri kuin ehdoton. Salatekstin tunteminen ei anna kryptanalyytikolle mitään hyödyllistä hankittavaa tietoa (salauksen purku on mahdollista vain kattavalla haulla ). $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}}$

Perusominaisuudet

Mikään rajoitettu avaimen salaus ei ole täydellinen. $S_{O}$

Todiste

Ehdollinen todennäköisyys rajoitetulle avainsalaukselle:

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

Osoittakaamme, että täydelliselle salaukselle se on totta: . Todellakin, jos joillekin ja , niin . Siitä lähtien ( absoluuttisen turvallisuuden määritelmän mukaan), mikä on ristiriidassa rajoitetun avaimen salauksen määritelmän kanssa. $|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)))$

Nyt voidaan väittää, että täydelliselle salaukselle , koska jokaiselle kiinteälle salaukselle on avain sellainen, että . Mutta tämä epätasa-arvo on mahdotonta , koska joukko on rajallinen, mutta kasvaa loputtomasti kasvun mukana , koska . $|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)}|$

Jos salaus on täydellinen, niin . $|X|\leq |Y|\leq |K|$

Todiste

Jos suoritamme argumentteja, jotka ovat samankaltaisia kuin edellisen ominaisuuden todistus, mutta käytämme joukon sijaan , niin saamme myös: . Mutta tässä tapauksessa meillä ei ole rajoituksia joukon kardinaalisuudesta . Ensimmäisen ominaisuuden mukaan epätasa-arvo pätee myös . $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$

Shannonin lause

Sanamuoto

Rajoittamaton avaimen salaus , joka on täydellinen jos ja vain, jos: $S_{H}$ $|X|=|Y|=|K|$

$yksi.$ $|K(x,y)|=1$ $\forall x\in X,\forall y\in Y$ , jossa , eli kaikille ja kaikille on vain yksi avain sellainen, että ; ${\displaystyle 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$ , eli avainten on oltava yhtä todennäköisiä.

Todiste

$(\Oikeanuoli 1)$

Koska , se seuraa , että seuraa . $|Y|=|K|$ $|K(x,y)|\geq 1$ ${\displaystyle k_{1}\neq k_{2))$ $e_{k_{1}}(x)\neq e_{k_{2}}(x)$ $\forall x\in X$

$(\Rightarrow 2)$

Luetteloimme avaimet seuraavasti kiinteälle : . Saamme: $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|}}$ .

$(\Lefttarrow 1,2)$

Käytämme samaa numerointia kuin edellisessä kappaleessa, pitäen sitä kiinteänä. Hakeminen : $y$ $yksi$

$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}}$ . Hakeminen ja : $yksi$ $2$

$p(x_{j}|y)={\frac {p(x_{j})\cdot p(y|x_{j})}{p(y)))=p(x_{j} )$ . Saatiin absoluuttisen lujuuden määritelmä.

Yleisnäkymä

Shannonin lauseen perusteella salaussääntö korvaussalaukselle , jonka , voidaan esittää latinalaisena neliöksi : ${\displaystyle 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\|})$

Tasaisella todennäköisyydellä järjestelmä on täysin vakaa. Tällaisen järjestelmän käytännön toteutus on esimerkiksi Vernam-salaus . $k_{1},...,k_{|X|}$

Huomautus

On ehdottoman vahvoja salauksia, joiden merkkien määrä selväkielisissä aakkosissa on pienempi kuin . Esimerkiksi: $|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))$	$yksi$	$2$
$k_{2},p(k_{2})={\frac {3}{20))$	$yksi$	$3$
$k_{3},p(k_{3})={\frac {21}{80))$	$2$	$yksi$
$k_{4},p(k_{4})={\frac {1}{10))$	$2$	$3$
$k_{5},p(k_{5})={\frac {1}{8))$	$3$	$yksi$
$k_{6},p(k_{6})={\frac {1}{8))$	$3$	$2$

Tämän salauksen absoluuttinen vahvuus on helppo tarkistaa määritelmän mukaan kaavalla: . $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)))$

Tämä salaus on täysin turvallinen kaikissa jakeluissa . $P(X)$

Katso myös

Kirjallisuus

Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Tietoturva : oppikirja - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
K. Shannon. Viestintäteoria salaisissa järjestelmissä // Tietoteoriaa ja kybernetiikkaa käsitteleviä teoksia / Kääntäjä S. Karpov. - M .: IL, 1963. - S. 243-322. — 830 s. Arkistoitu 22. joulukuuta 2014 Wayback Machinessa
Zubov A. Yu. Tietosuojan kryptografiset menetelmät. Täydelliset salakirjoitukset. M. .: Helios ARV, 2005. - 160 s.