Teljesen erős titkosítás

Abszolút erős rejtjelnek nevezzük azt a rejtjelezést, amelyre jellemző, hogy a titkosítási elemző alapvetően nem tud statisztikai információt kinyerni a választott kulcsokra vonatkozóan az elfogott rejtjelszövegből .

Matematikailag az abszolút biztonságos rejtjel fogalmát Claude Shannon vezette be 1945-ben "A kriptográfia matematikai elmélete" című munkájában.

Segédfogalmak

Legyen és legyen a nyílt és titkosított ábécé úgy, hogy . $x$ $Y$ $|X|>1,$ $|Y|>1,$ $|Y|\geq |X|$

A titkosítást injektív leképezés , a dekódolást leképezés adja . $e_{k}:X\rightarrow Y$ $d_{k}:e_{k}(X)\jobbra mutató X,$ ${\displaystyle k\in K=\{1,2,...,n\))$

${\displaystyle E=\{e_{k},k\in K\},D=\{d_{k},k\in K\))$ - titkosítási és visszafejtési szabályok készletei.

A lehetséges leképezések maximális száma megegyezik a by -tól származó elrendezések számával ( a készletben lévő méret részhalmazok kiválasztásának módjainak száma, az elemek sorrendje alapján). $|E|=n$ $|Y|$ $|X|$ $|X|$ $Y$

A következő karakter előfordulása, a kulcs kiválasztása (vagyis a megjelenítés kiválasztása ), a rejtjelezett szöveg fogadása bizonyos valószínűségekkel megvalósul: $x\X-ben$ $k\in K$ $e_{k}$ $y\-ban Y$

$P(X^{l})=\{p_{X^{l}}({\vec {x}}),{\vec {x}}\in X^{l}}\}$ az egyszerű szöveg valószínűségi eloszlása ,

$P(K^{l})=\{p_{K^{l}}({\vec {k}}),{\vec {k}}\in K^{l}}\}$ a megjelenített számok kombinációjának valószínűségi eloszlása,

$P(Y^{l})=\{p_{Y^{l}}({\vec {y}}),{\vec {y}}\in Y^{l}}\}$ a rejtjelezett szöveg valószínűségi eloszlása, ahol

${\displaystyle X^{l},K^{l},Y^{l))$ a halmazok derékszögű hatványai , a karakterek száma a nyílt szövegben. $X,K,Y$ $l$

Feltételezzük, hogy a nyílt szöveg és a kulcs megjelenésének megfelelő valószínűségi változók függetlenek . Akkor: ${\vec {x}}$ $\vec{k}$

$p_{Y^{l}}({\vec {y}})=\sum _{}p_{X^{l}}({\vec {x}})p_{K^{l} }({\vec {k)))$ , ahol az összeg minden felett van, és olyan, hogy . ${\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}$ — titkosítási és visszafejtési szabályok halmazai (halmazok derékszögű hatványai ). $E,D$

Figyelembe véve, hogy az ábécé hosszúságú karaktereinek nem minden kombinációja jelenhet meg a nyílt szövegben, írjuk be: . $l$ $x$ $X^{(l)}=\{{\vec {x}}:p_{X^{l}}({\vec {x}})>0\},Y^{(l)} =\{{\vec {y}}:p_{Y^{l}}({\vec {y}})>0\}$

A korlátlan kulcsú helyettesítő rejtjel a rejtjelek családja , ahol a , while halmaza . ${\displaystyle S_{H}=\{S_{H}^{(l)},l\in \mathbb {N} \))$ ${\displaystyle 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}$

A korlátlan kulcsot helyettesítő titkosítás kulcshossza megegyezik a nyílt szöveg méretével . $l$

Legyen néhány kulcs véges halmaza (természetes számok néhány gyűjteménye). A kulcs hossza től kisebb lehet, mint . Minden egyes kulcshoz beállítható a kulcsfolyam determinisztikus felépítésének szabálya . Az így kapott kulcsfolyamok halmazát az összes kulcshoz innen jelöli . Például egy kulcs esetében ennek a kulcsnak a rendszeres ismétlődése tekinthető kulcsfolyamnak . Jegyezze meg, hogy . ${\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))$

A korlátozott kulcsú helyettesítő rejtjel olyan rejtjelcsalád, amelyben ugyanaz a halmaz van, mint a fent meghatározott korlátlan kulcsú rejtjelnél, amelyben a és helyett a halmaz és az elosztás használatos . ${\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)})$

Formális definíció

Legyen annak a valószínűsége, hogy az üzenetet a titkosított szöveg regisztrálásakor titkosították . A titkosításról azt mondják, hogy teljesen biztonságos, ha: $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 }$ .

Más szóval, az utólagos valószínűségi eloszlás megegyezik az előző eloszlással . Az információelmélet szempontjából ez azt jelenti, hogy egy ismert rejtjelezett szöveggel rendelkező üzenet feltételes entrópiája egyenlő a feltétel nélkülivel. A rejtjelezett szöveg ismerete nem ad a kriptográfiai elemző számára hasznos ismereteket (a visszafejtés csak kimerítő kereséssel lehetséges ). $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}}$

Alaptulajdonságok

Egyetlen korlátozott kulcsú titkosítás sem tökéletes. $S_{O}$

Bizonyíték

Feltételes valószínűség korlátozott kulcsú titkosításhoz:

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

Mutassuk meg, hogy egy tökéletes titkosításra igaz: . Valóban, ha néhány és , akkor . Mivel , akkor ( az abszolút biztonság definíciója szerint), ami ellentmond a korlátozott kulcsú rejtjel definíciójának. $|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)))$

Most már vitatható, hogy a tökéletes titkosításhoz , mivel minden rögzített rejtjelhez van olyan kulcs , hogy . De ez az egyenlőtlenség lehetetlen , mivel a halmaz véges, de a növekedéssel korlátlanul növekszik , mert . $|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)}|$

Ha a titkosítás tökéletes, akkor . $|X|\leq |Y|\leq |K|$

Bizonyíték

Ha az előző tulajdonság bizonyításához hasonló argumentumokat hajtunk végre, de halmaz helyett használjuk , akkor azt is kapjuk, hogy: . De ebben az esetben nincs megkötésünk a halmaz kardinalitásában . Az első tulajdonság szerint az egyenlőtlenség a -ra is érvényes lesz . $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$

Shannon tétele

Megfogalmazás

Egy korlátlan kulcsrejtjel , amely akkor és csak akkor tökéletes, ha: $S_{H}$ $|X|=|Y|=|K|$

$egy.$ $|K(x,y)|=1$ $\forall x\in X,\forall y\in Y$ , ahol , azaz bármely és bármelyikhez csak egy olyan kulcs van , hogy ; ${\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$ , vagyis a kulcsoknak egyformán valószínűnek kell lenniük.

Bizonyítás

$(\Jobbra 1)$

Mivel , ebből az következik . $|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$

$(\Jobbra 2)$

A kulcsokat a következőképpen soroljuk fel egy fix : . Kapunk: $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)}}\Jobbra p(k_{j})=p(y)$ $\forall j={\overline {1,|X|}}$ .

$(\Leftarrow 1,2)$

Ugyanazt a számozást használjuk, mint az előző bekezdésben, rögzítettnek tekintve. Jelentkezés : $y$ $egy$

$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}}$ . Jelentkezés és : $egy$ $2$

$p(x_{j}|y)={\frac {p(x_{j})\cdot p(y|x_{j})}{p(y)))=p(x_{j} )$ . Az abszolút szilárdság megkapott definíciója.

Általános nézet

Shannon tétele alapján a titkosítási szabály a helyettesítő titkosításhoz , amelyre , latin négyzetként ábrázolható : ${\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\|})$

Kiegyensúlyozott használat mellett a rendszer abszolút stabilitást biztosít. Egy ilyen rendszer gyakorlati megvalósítása például a Vernam-rejtjel . $k_{1},...,k_{|X|}$

Megjegyzés

Vannak teljesen erős titkosítások, amelyeknél az egyszerű szöveges ábécé karaktereinek száma kevesebb, mint . Például: $|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))$	$egy$	$2$
$k_{2},p(k_{2})={\frac {3}{20))$	$egy$	$3$
$k_{3},p(k_{3})={\frac {21}{80))$	$2$	$egy$
$k_{4},p(k_{4})={\frac {1}{10))$	$2$	$3$
$k_{5},p(k_{5})={\frac {1}{8))$	$3$	$egy$
$k_{6},p(k_{6})={\frac {1}{8))$	$3$	$2$

Ennek a rejtjelnek az abszolút erőssége könnyen ellenőrizhető a következő képlettel: . $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)))$

Ez a titkosítás minden terjesztéshez teljesen biztonságos marad . $P(X)$

Lásd még

Irodalom

Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Információbiztonság : tankönyv - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
K. Shannon. Kommunikációelmélet titkos rendszerekben // Információelméleti és kibernetikai munkák / S. Karpov fordítása. - M. : IL, 1963. - S. 243-322. — 830 p. Archivált : 2014. december 22. a Wayback Machine -nál
Zubov A. Yu. Az információvédelem kriptográfiai módszerei. Tökéletes titkosítások. M. .: Helios ARV, 2005. - 160 p.