Teoria informacji/TI Wykład 6

Z Studia Informatyczne
< Teoria informacji
Wersja z dnia 10:01, 16 lip 2006 autorstwa Stromy (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 :

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 dla pewnego i


Gdzie oznacza XOR po bitach (np. ). Tym samym

Dodatkowo zakładamy że K jest wybierana z rozkładem jednostajnym na , czyli , 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 . (link TODO)

Zaczynamy od:

(bo M i K są niezależne)

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

QED.


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


Twierdzenie [Pesymistyczne Twierdzenie Shannona]

Każdy idealnie bezpieczny kryptosystem musi zapewniać:

W konsekwencji (link TODO):


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

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

Rozbijając analogicznie H(K) uzyskujemy:

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 ), to
.

Dowód

Skorzystajmy z zasady łańcuchowej:

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

QED.


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,

Dowód Na podstawie lematu, gdyż