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 ${\mathcal {M}}$ (wiadomości)
K – ze skończonego zbioru wartości ${\mathcal {K}}$ (klucze)
C – ze skończonego zbioru wartości ${\mathcal {C}}$ (zaszyfrowane wiadomości)

Dodatkowo musi istnieć funkcja ${\mathit {Dec}}:{\mathcal {C}}\times {\mathcal {K}}\to {\mathcal {M}}$ :

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 ${\mathcal {M}}={\mathcal {K}}={\mathcal {C}}=\{0,1\}^{n}$ dla pewnego $n\in \mathbb {N}$ i

C=M\oplus K

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

Dodatkowo zakładamy że K jest wybierana z rozkładem jednostajnym na $\{0,1\}^{n}$ , czyli $\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)$ . (link TODO)

Zaczynamy od:

$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)

(bo M i K są niezależne)

=\sum _{u\in {\mathcal {M}}}{\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.

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

Twierdzenie [Pesymistyczne Twierdzenie Shannona]

Każdy idealnie bezpieczny kryptosystem musi zapewniać:

H(K)\geq H(M)

W konsekwencji (link TODO):

L_{r}(K)\geq H_{r}(K)\geq H_{r}(M)\geq 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)+\underbrace {I(M;C)} _{H(M)-H(M|C)}+\underbrace {I(M;K|C)} _{H(M|C)-H(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)

Rozbijając analogicznie H(K) uzyskujemy:

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

QED.

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