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:

$\begin{array}{rl}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)\text{ (bo M i K są niezależne) }\\ & =\sum _{u\in {ℳ}}\frac{1}{2^n}\cdot p(M=u)\\ & =\frac{1}{2^n}\end{array}$

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

$\begin{array}{rl}p(C=w\wedge M=u)& =p(K=w\oplus v\wedge M=u)\\ & =\frac{1}{2^n}\cdot p(M=u)\end{array}$

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$

Kryptografia kwantowa

Korzystanie z szyfru Vernama jest bardzo niewygodne z powodu konieczności wcześniejszego ustalenia klucza równie długiego, jak przesyłana wiadomość. Dlatego w większości zastosowań rezygnuje się z idealnej tajności na rzecz bezpieczeństwa złożonościowego. W takich metodach (stosowanych praktycznie wszędzie w sieci) bezpieczeństwo opiera się na trudności obliczeniowej rozwiązania pewnych problemów algorytmicznych. Odszyfrowanie wiadomości bez znajomości klucza jest możliwe, ale zakłada się że nikt nie dysponuje wystarczająco potężną mocą obliczeniową, aby tego dokonać. Z punktu widzenia teorii informacji, zaszyfrowane wiadomości zawierają jednak pełną informację, czyli $I(C;M)=H(M)$.

Obecnie jedyną metodą pozwalającą uzyskać idealną tajność bez wcześniejszego ustalenia klucza jest zastosowanie kryptografii kwantowej. W ogólności kwantowa teoria informacji nie mieści się w zakresie tego kursu, ale ogólne idee postaramy się tu przedstawić.

W kwantowej teorii zastępuje się klasyczne bity ich odpowiednikami, tzw. kubitami. Kubit jest najmniejszą porcją kwantowej informacji. Tak jak klasyczny bit może przyjmować wartości $0$ i $1$. W odróżnieniu od niego, może jednak przyjmować też dowolną superpozycję tych wartości, czyli być w stanie „pomiędzy” $0$ a $1$. Formalnie jego stan można opisać wektorem z dwuwymiarowej przestrzeni

$|\psi ⟩=\alpha |0⟩+\beta |1⟩$

gdzie $|0⟩$ i $|1⟩$ oznaczają wektory bazowe, a liczby zespolone $\alpha$ i $\beta$ nazywane są amplitudami.

Pomiar takiego kubitu daje w wyniku $0$ z prawdopodobieństwem $|\alpha {|}^2$ i $1$ z prawdopodobieństwem $|\beta {|}^2$ (dlatego zawsze $|\alpha {|}^2+|\beta {|}^2=1$).

Po dokonaniu pomiaru stan kubitu ustala się na zmierzonym wektorze (a więc po pomiarze $|\psi ⟩=|0⟩$ lub $|\psi ⟩=|1⟩$). Ta własność jest kluczowa dla bezpieczeństwa kryptografii kwantowej.

Na kubitach można dokonywać operacji unitarnych (to znaczy takich, które nie zmieniają wartości $|\alpha {|}^2+|\beta {|}^2$). Przykładem takiej operacji jest bramka Hadamarda

$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

Warto zauważyć, że ta bramka jest inwolucją

$H^2=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\cdot \frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)=\frac{1}{2}\left(\begin{array}{cc}1+1& 1-1\\ 1-1& 1+1\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$

Układy wielu kubitów opisuje się analogicznie do jednego kubitu: dwa bity mogą przyjmować 4 możliwe wartości, dlatego układ dwóch kubitów opisywany jest jako wektor z czterowymiarowej przestrzeni. Układ trzech kubitów opisywany jest jako wektor z ośmiowymiarowej przestrzeni itd. Również w tym przypadku jedyne dopuszczalne operacje na takich układach to pomiary oraz operacje unitarne.

Istotną cechą operacji unitarnych jest ich odwracalność - dla każdej z nich istnieje macierz odwrotna. Pociąga to za sobą krytyczną własność informatyki kwantowej, nie mającą odpowiednika w informatyce klasycznej:

Twierdzenie [Brak klonowania]

Nie istnieje operacja kwantowa kopiująca wiernie dowolne kubity, tzn. taka $U$, że dla dowolnego $|\psi ⟩$:

$U|\psi ⟩|0⟩=|\psi ⟩|\psi ⟩$

Przy pomocy operacji unitarnych na układach kubitów można projektować bardzo efektywne algorytmy, w niektórych przypadkach wykładniczo efektywniejsze od najlepszych znanych algorytmów klasycznych (jak algorytm faktoryzacji Shora). Praktyczna ich implementacja jest jednak bardzo trudna i do tej pory nikomu nie udało się przeprowadzić dużego obliczenia kwantowego. Operowanie na pojedynczych kubitach jest za to dosyć proste; istnieją komercyjne urządzenia używające ich do bezpiecznego przesyłania danych. W takich urządzeniach kubity realizowane są jako pojedyncze fotony, przesyłane pomiędzy nadawcą a odbiorcą.

Przykładowy protokół uzgadniania klucza przy ich użyciu wygląda następująco:

Protokół BB84
1. Gracz A przygotowuje losowy ciąg kubitów z następującym rozkładem:
$|\psi ⟩=\{\begin{array}{ccc}|0⟩& \text{z prawd.}& \frac{1}{2}\\ |1⟩& \text{z prawd.}& \frac{1}{2}\end{array}$
2. Gracz A do każdego kubitu aplikuje z prawdopodobieństwem $\frac{1}{2}$ bramkę Hadamarda.
3. Gracz A wysyła tak przygotowane kubity do gracza B
4. Gracz B do każdego otrzymanego kubitu aplikuje z prawdopodobieństwem $\frac{1}{2}$ bramkę Hadamarda.
5. Gracz B dokonuje pomiaru wszystkich kubitów.
6. Gracze A i B ogłaszają publicznie, do których kubitów aplikowali bramkę Hadamarda
7. Tajnym kluczem stają się wartości kubitów, przy których obaj gracze zachowali się tak samo 
(to znaczy obaj aplikowali bramkę lub obaj nie aplikowali).

Ustalony w ten sposób klucz gracze mogą wykorzystać do zwykłego zaszyfrowania wiadomości (np. szyfrem Vernama).

Dla każdego bitu, dla którego gracze zachowali się tak samo, wynik pomiaru B powinien być identyczny ze stanem w jakim A początkowo przygotował kubit. W przypadku, gdy tylko jeden z graczy zaaplikował bramkę Hadamarda, wynik pomiaru powinien być dokładnie losowy (dać $0$ i $1$ z prawdopodobieństwem $\frac{1}{2}$).

Trzeci gracz, usiłujący podsłuchać przesyłany klucz, musi to zrobić w punkcie 3. Teoretycznie może tu przeprowadzić dowolną kombinację operacji unitarnych i pomiarów. Gdyby wiedział, na których kubitach gracz A użył bramki Hadamarda, mógłby odwrócić jej działanie, zmierzyć wartości kubitów, przygotować je ponownie i przesłać do B. Nie mając tej informacji i nie mogąc skopiować wiernie przesyłanych bitów, ryzykuje że, zaburzy przygotowane wcześniej stany. Do wykrycia podsłuchującego wystarczy zatem, że po zakończeniu protokołu A i B ogłoszą kilka bitów ustalonego przez siebie klucza (usuwając je z klucza) - jeśli część z nich nie będzie się zgadzać, oznacza to, że kanał komunikacyjny nie jest bezpieczny. Formalnie dowód tego bezpieczeństwa jest bardziej skomplikowany, tutaj sygnalizujemy tylko, jak to wygląda z punktu widzenia teorii informacji. Jeśli przesyłane pierwotnie wiadomości oznaczymy jako $X_A$, informacje które docierają do B jako $X_B$, a informacje odczytane przez C jako $X_C$, to otrzymamy następującą interesującą własność:

$H(X_A)\ge I(X_A;X_B)+I(X_A;X_C)$

Innymi słowy, tyle informacji, ile gracz C „podsłucha”, musi być przez B „stracone”. Jest to konsekwencja zasady nieoznaczoności i powoduje, że gracze A i B są w stanie z dużym prawdopodobieństwem wykryć ingerencję w kanał.

Istnieją bardziej skomplikowane kwantowe protokoły kryptograficzne, np. wykorzystujące teleportację kwantową. Ich zasada działania jest jednak bardzo podobna. Bezpieczeństwo zawsze opiera się na zasadzie nieoznaczoności i wykrywaniu komunikatów, które zostały zmodyfikowane przez podsłuchującego.