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 ${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.

{{przyklad|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:

$p(C=w)=\sum _{u\in {ℳ}}p(K=u\oplus w|M=u)\cdot p(M=u)$

$=\sum _{u\in {ℳ}}p(K=u\oplus w)\cdot p(M=u)$ (bo M i K są niezależne)

$=\sum _{u\in {ℳ}}\frac{1}{2^n}\cdot p(M=u)$

$=\frac{1}{2^n}$

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

$p(C=w\wedge M=u)=p(K=w\oplus v\wedge M=u)$

$=\frac{1}{2^n}\cdot p(M=u)$

QED.

(TODO na ćwiczeniach: Niezależność M i K jest warunkiem koniecznym)

Twierdzenie [Pesymistyczne Twierdzenie Shannona]

Każdy idealnie bezpieczny kryptosystem musi zapewniać:

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

W konsekwencji (link TODO):

$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

$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

Ważną cechą informacji jest niemożliwość jej powiększenia przez lokalne obliczenia. Przykładowo niech A i B będą zmiennymi losowymi. 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$