Teoria informacji/TI Wykład 6

Doskonale bezpieczne szyfrowanie

Pokażemy teraz jak przy pomocy teorii informacji możemy udowodnić że jakiś system kryptograficzny jest całkowicie bezpieczny.

Definicja [Kryptosystem]

Kryptosystemem nazywamy trójkę zmiennych losowych:

• M – ze skończonego zbioru wartości ${ℳ}$ (wiadomości)
• K – ze skończonego zbioru wartości ${𝒦}$ (klucze)
• C – ze skończonego zbioru wartości ${𝒞}$ (zaszyfrowane wiadomości)

Dodatkowo musi istnieć funkcja deszyfrująca${D}{e}{c}:{𝒞}\times {𝒦}\to {ℳ}$:

$M=Dec(C,K)$

(czyli z szyfru i klucza uzyskuje się w sposób jednoznaczny pierwotną wiadomość).

Kryptosystem jest idealnie bezpieczny jeśli $I(C;M)=0$.

Przykład [Szyfr Vernama (one-time pad)]

Definiujemy ${ℳ}={𝒦}={𝒞}=\{0,1{\}}^n$ dla pewnego $n\in \mathbb{\mathbb{N}}$ i

$C=M\oplus K$

Gdzie $\oplus$ oznacza XOR po bitach (np. $101101\oplus 110110=011011$). Tym samym ${D}{e}{c}(v,w)=v\oplus w$

Dodatkowo zakładamy że K jest wybierana z rozkładem jednostajnym na $\{0,1{\}}^n$, czyli ${\mathrm{\forall }}_{v\in \{0,1{\}}^n}p(K=v)=\frac{1}{2^n}$, i że M jest zmienną niezależną od K.

Przy powyższych założeniach Szyfr Vernama jest idealnie bezpieczny. Aby to udowodnić, wystarczy pokazać że M i C są niezależne, czyli że $p(C=w\wedge M=u)=p(C=w)\cdot p(M=u)$ (patrz twierdzenie o entropii łącznej).

Zaczynamy od:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned p(C = w) & = \sum_{u \in {\mathcal M}} p (K = u \oplus w | M = u) \cdot p(M = u)\\ & = \sum_{u \in {\mathcal M}} p (K = u \oplus w) \cdot p(M = u) \mbox{ (bo M i K są niezależne) } \\ & = \sum_{u \in {\mathcal M}} \frac{1}{2^n} \cdot p(M = u) \\ & = \frac{1}{2^n} \endaligned }

Jeśli teraz skorzystamy z definicji C i niezależności M i K dostajemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned p (C = w \, \wedge \, M = u) & = p (K = w \oplus v \, \wedge \, M = u)\\ & = \frac{1}{2^n} \cdot p ( M = u) \endaligned }

Twierdzenie [Pesymistyczne Twierdzenie Shannona]

Każdy idealnie bezpieczny kryptosystem musi zapewniać:

$H(K)\ge H(M)$

W konsekwencji (na postawie kodowania Shannona-Fano):

$L_r(K)\ge H_r(K)\ge H_r(M)\ge L_r(M)-1$

Czyli aby uzyskać idealną tajność, musimy użyć klucza równie długiego jak przesyłana wiadomość. Jest to oczywiście bardzo niepraktyczne, ale w niektórych zastosowaniach konieczne.

Dowód

Rozpisujemy: $H(M)=H(M|C,K)+\underset{=H(M)-H(M|C)}{\underbrace{I(M;C)}}+\underset{=H(M|C)-H(M|K,C)}{\underbrace{I(M;K|C)}}$

Ale z definicji M jest funkcją (C,K), czyli $H(M|C;K)=0$. Wymagamy żeby $I(M;C)=0$, a więc:

$H(M)=I(M;K|C)$

Rozpisując analogicznie H(K) uzyskujemy:

$H(K)=H(K|M,C)+I(K;C)+\underset{=H(M)}{\underbrace{I(K;M|C)}}$

Ważną cechą informacji jest niemożliwość jej powiększenia przez lokalne obliczenia. Niech A i B będą zmiennymi losowymi. Przykładowo wyobraźmy sobie że A określa jakieś dane eksperymentalne, a B naszą wiedzę o nich. Okazuje się że wszelkie operacje jakich dokonamy na B (analiza, przetwarzanie danych itp.) mogą jedynie zmniejszyć naszą informację o A.

Lemat

Jeśli A i C są niezależne warunkowo przy danym B (czyli $I(A;C|B)=0$), to $I(A;C)\le I(A;B)$.

Dowód

Skorzystajmy z zasady łańcuchowej:

$\underset{=H(A)-H(A|B,C)}{\underbrace{I(A;(B,C))}}=\underset{=H(A)-H(A|C)}{\underbrace{I(A;C)}}+\underset{=H(A|C)-H(A|B,C)}{\underbrace{I(A;B|C)}}$

Z symetrii, używając niezależności warunkowej A i C dostaniemy:

$I(A;(B,C))=I(A;B)+\underset{=0}{\underbrace{I(A;C|B)}}$

Zauważmy że nierówność staje się równością, o ile dodatkowo A i B są warunkowo niezależne przy danym C (czyli $I(A;B|C)=0$).

Wniosek

Dla dowolnej funkcji f, $I(A;f(B))\le I(A;B)$

Dowód

Na podstawie lematu, gdyż $I(A;f(B)|B)=\underset{=0}{\underbrace{H(f(B)|B)}}-\underset{=0}{\underbrace{H(f(B)|A,B)}}=0$