Teoria informacji/TI Wykład 7: Różnice pomiędzy wersjami

Wersja z 12:25, 11 sie 2006

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 = D e c (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 ℕ$ 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 $\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 \land 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) \geq H (M)

W konsekwencji (na postawie kodowania Shannona-Fano):

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

Rozpisujemy:

H (M) = H (M | C, K) + \underset{= H (M) - H (M | C)}{\underset{⏟}{I (M; C)}} + \underset{= H (M | C) - H (M | K, C)}{\underset{⏟}{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)}{\underset{⏟}{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) \leq I (A; B)

.

Dowód

Skorzystajmy z zasady łańcuchowej:

\underset{= H (A) - H (A | B, C)}{\underset{⏟}{I (A; (B, C))}} = \underset{= H (A) - H (A | C)}{\underset{⏟}{I (A; C)}} + \underset{= H (A | C) - H (A | B, C)}{\underset{⏟}{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}{\underset{⏟}{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)) \leq I (A; B)

Dowód

Na podstawie lematu, gdyż

I (A; f (B) | B) = \underset{= 0}{\underset{⏟}{H (f (B) | B)}} - \underset{= 0}{\underset{⏟}{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

| ψ ⟩ = α | 0 ⟩ + β | 1 ⟩

gdzie $| 0 ⟩$ i $| 1 ⟩$ oznaczają wektory bazowe, a liczby zespolone $α$ i $β$ nazywane są amplitudami.

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

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

Na kubitach można dokonywać operacji unitarnych (to znaczy takich które nie zmieniają $| α |^{2} + | β |^{2} = 1$ ). Przykładem takiej operacji jest bramka Hadamarda

H = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})

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

H^{2} = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) \cdot \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) = \frac{1}{2} (\begin{matrix} 1 + 1 & 1 - 1 \\ 1 - 1 & 1 + 1 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})

Analogicznie opisuje się układy wielu kubitów: dwa bity mogą przyjmować 4 możliwe wartośći, 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. Jedyne dopuszczalne ingerowanie w takie układy 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 $| ψ ⟩$ :

U | ψ ⟩ | 0 ⟩ = | ψ ⟩ | ψ ⟩

Układy wielu kubitów teoretycznie pozwalają na znacznie efektywniejsze obliczenia niż przy użyciu klasycznych komputerów. 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, i istnieją komercyjne urządzenia używające ich do bezpiecznego przesyłania danych. W takich urządzeniach kubity realizowane są jako pojedyncze fotony. Najprostszy protokół ustalania klucza wygląda następująco:

Protokół BB84
1. Gracz A przygotowuje losowy ciąg kubitów z następującym rozkładem:
 $| ψ ⟩ = {\begin{matrix} | 0 ⟩ & z prawd. & \frac{1}{2} \\ | 1 ⟩ & z prawd. & \frac{1}{2} \end{matrix}$ 
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ł qubit. 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 pokażemy 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}) \geq 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ł.

Inne kwantowe protokoły kryptograficzne wykorzystują teleportację kwantową, ale ich zasada jest bardzo podobna. Bezpieczeństwo zawsze opiera się na zasadzie nieoznaczoności, i odrzucaniu komunikatów które zostały zmodyfikowane przez podsłuchującego.

Teoria informacji/TI Wykład 7: Różnice pomiędzy wersjami

Wersja z 12:25, 11 sie 2006

Doskonale bezpieczne szyfrowanie

Kryptografia kwantowa

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-===Kanały===
+===Doskonale bezpieczne szyfrowanie===
-{{definicja|[Kanał komunikacyjny]|kanał|'''Kanałem komunikacyjnym''' <math>\Gamma</math> nazywamy trójkę:}}
+Pokażemy teraz jak przy pomocy teorii informacji możemy udowodnić że jakiś system kryptograficzny jest całkowicie bezpieczny.
-* skończony zbiór <math>\mathcal{A}</math> symboli ''wejściowych''
-* skończony zbiór <math>\mathcal{B}</math> symboli ''wyjściowych''
-* mapowanie <math>\mathcal{A} \times \mathcal{B} \to [0,1]</math> określające dla każdej pary (a,b) prawdopodobieństwo <math>P(a \to b)</math> zamiany symbolu a na B, spełniające warunek:
-<center><math>\forall_{a \in \mathcal{A}} \sum_{b \in {\mathcal B}} P (a \to b) = 1</math></center>
+{{definicja|[Kryptosystem]|kryptosystem|'''Kryptosystemem''' nazywamy trójkę zmiennych losowych:}}
-Zmienne losowe A i B o wartościach odpowiednio z <math>\mathcal{A}</math> i <math>\mathcal{B}</math> stanowią parę ''wejście-wyjście'' dla kanału <math>\Gamma</math> jeśli dla dowolnych <math>a \in \mathcal{A},b \in \mathcal{B}</math>
+* M – ze skończonego zbioru wartości <math>{\mathcal M}</math> (wiadomości)
+* K – ze skończonego zbioru wartości <math>{\mathcal K}</math> (klucze)
+* C – ze skończonego zbioru wartości <math>{\mathcal C}</math> (zaszyfrowane wiadomości)
-<center><math>p (B = b | A = a) = P (a \to b)</math></center>
+Dodatkowo musi istnieć funkcja deszyfrująca<math>\mathit{Dec} : {\mathcal C} \times {\mathcal K} \to {\mathcal M}</math>:
+<center><math>M = Dec(C,K)</math></center>
-Kanał taki możemy zobrazować jako
+(czyli z szyfru i klucza uzyskuje się w sposób jednoznaczny pierwotną wiadomość).
-<center><math>A \to</math>[[grafika:Gamma.PNG]]<math>\to B</math></center>
+Kryptosystem jest '''idealnie bezpieczny''' jeśli <math>I(C;M)=0</math>.
-Możemy od razu zauważyć że
-<center><math>p ( A = a \, \wedge \, B = b)  = P (a \to b) \cdot p ( A = a )</math></center>
-A więc rozkład (A,B) jest jednoznacznie wyznaczony przez A (dla ustalonego <math>\Gamma</math>. W szczególności odpowiednie B zawsze istnieje i jest zdefiniowane jako <math>p (B = b)  = \sum_{a \in {\mathcal A}} P (a \to b) \cdot p ( A = a )</math>
+{{przyklad|[Szyfr Vernama (one-time pad)]||
-Więdząc to, można bezpośrednio policzyć <math>H(A,B)</math>, <math>H(B|A)</math>, <math>I(A;B)</math> itp. (w zależności od <math>\Gamma</math> i A).
+Definiujemy <math>{\mathcal M} ={\mathcal K} ={\mathcal C} = \{0,1\}^n</math> dla pewnego <math>n \in \mathbb{N}</math> i
+<center><math>C = M \oplus K</math></center>
+Gdzie <math>\oplus</math> oznacza XOR po bitach (np. <math>101101 \oplus 110110 = 011011</math>). Tym samym <math>\mathit{Dec} (v,w) = v \oplus w</math>
-{{definicja|[Przepustowość kanału]|przepustowość|'''Przepustowość kanału komunikacyjnego''' definiujemy jako
+Dodatkowo zakładamy że K jest wybierana z rozkładem jednostajnym na <math>\{0,1\}^n</math>, czyli <math>\forall_{v \in \{0,1\}^n} p(K=v)=\frac{1}{2^n}</math>, i że M jest zmienną niezależną od K.
-<center><math>C_{\Gamma } = \max_{A} I (A;B)</math></center>}}
-(dla ustalenia uwagi, tutaj<math>I=I_2</math>). Maksimum jest tutaj brane po wszystkich rozkładach zmiennej losowej A na <math>\mathcal{A}</math>. Istnieje ono zawsze, ponieważ <math>I(A;B)</math> jest ciągłym odwzorowaniem ze zbioru zwartego <math>\{ p \in [0,1]^{{\mathcal A}} : \sum_{a \in {\mathcal A}} p(a) = 1 \}</math> w <math>\mathbb{R}</math>, i dodatkowo ograniczonym (<math>I(A;B) \le H(A) \le \log|\mathcal{A}|</math>).
-Jeśli <math>\mathcal{A}= \{ a_1, \ldots , a_m \}</math> i <math>\mathcal{B}= \{ b_1, \ldots , b_n \}</math>, to możemy kanał reprezentować jako macierz:
+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 <math> p (C = w \, \wedge \, M = u) = p (C = w) \cdot p ( M = u)</math>
+(patrz [[Teoria informacji/TI Wykład 5#do_łącznej|twierdzenie o entropii łącznej]]).
-<center><math>\left(
+Zaczynamy od:
-\begin{matrix}
+<center><math>\aligned
-P_{1 1} & \ldots & P_{1 n} \\
+p(C = w) & = \sum_{u \in {\mathcal M}} p (K = u \oplus w | M = u) \cdot p(M = u)\\
-\ldots  & \ldots & \ldots \\
+& = \sum_{u \in {\mathcal M}}  p (K = u \oplus w) \cdot p(M = u) \mbox{ (bo M i K są niezależne) } \\
-P_{m 1} & \ldots & P_{m n}
+& = \sum_{u \in {\mathcal M}} \frac{1}{2^n} \cdot p(M = u) \\
-\end{matrix}
+& = \frac{1}{2^n}
-\right) </math></center>
+\endaligned
+</math></center>
-gdzie <math> P_{i j} = p (a_i \to b_j )</math>
+Jeśli teraz skorzystamy z definicji C i niezależności M i K dostajemy:
+<center><math>\aligned
-W tej postaci wzór na rozkład zmiennej losowej B ma postać:
+p (C = w \, \wedge \, M = u) & = p (K = w \oplus v \, \wedge \,  M = u)\\
+& = \frac{1}{2^n} \cdot p ( M = u)
-<center><math>\left( p (a_1) , \ldots , p (a_m) \right)
+\endaligned
-\cdot
+</math></center>}}
-\left(
-\begin{matrix}
-P_{1 1} & \ldots & P_{1 n} \\
-\ldots  & \ldots & \ldots \\
-P_{m 1} & \ldots & P_{m n},
-\end{matrix}
-\right)
-=
-\left( p (b_1) , \ldots , p (b_n)\right)</math></center>
-===Przykłady===
-Proste kanały łatwo przedstawiać jako dwudzielne grafy skierowane o wierzchołkach z <math>\mathcal{A}</math> i <math>\mathcal{B}</math>, i krawędziach <math>a \to b</math> etykietowanych przez <math>P(a \to b)</math>
-(rysowanych o ile <math>P(a \to b) > 0</math>).
-{{przyklad|[Wierny (bezszumowy) kanał]|wierny_kanal|
-Niech <math>\mathcal{A}=\mathcal{B}=\{0,1\}</math>. Wierny kanał przekazuje informację bez przekłamań:
-<center>[[grafika:faithful.PNG]]</center>
-Macierz reprezentująca ten kanał to
-<center><math>\left(
-\begin{matrix}
-& 0 \\
-& 1
-\end{matrix}
-\right)</math></center>
-Skoro A jest zawsze równe B, to <math>I(A;B)=H(A)</math>, a więc przepustowość tego kanału jest równa
-<center><math> C_{\Gamma } = \max_{A} I(A;B) =  \max_{A} H(A) = \log_2 |{\mathcal A}| = 1</math></center>}}
-{{przyklad|[Wierny kanał odwracający]|odwracajacy_kanal|
-Kanał analogiczny do poprzedniego, ale odwracający wszystkie przekazywane bity:
-<center>[[grafika:inverse.PNG]]</center>
-Reprezentacja macierzowa to
-<center><math>\left(
-\begin{matrix}
-& 1 \\
-& 0
-\end{matrix}
-\right)</math></center>
-przepustowość tak jak w poprzednim przykładzie <math> C_{\Gamma } = 1</math>}}
-{{przyklad|[Kanał zaszumiony bez nakładania]|bez_nakladania_kanal|
+{{twierdzenie|[Pesymistyczne Twierdzenie Shannona]|pesymistyczne|
-<math>\mathcal{A}= \{0,1\}, \mathcal{B}=\{0,1,2,3\}</math>
-<center>[[grafika:wooverlap.PNG]]</center>
+Każdy idealnie bezpieczny kryptosystem musi zapewniać:
+<center><math>H(K) \ge H(M)</math></center>
-Macierz ma postać:
+W konsekwencji (na postawie [[Teoria informacji/TI Wykład 4#shannon_fano|kodowania Shannona-Fano]]):
-<center><math>\left(
+<center><math>L_r (K) \ge H_r (K) \ge  H_r (M) \ge L_r (M)-1</math></center>}}
-\begin{matrix}
-\frac{1}{2} & \frac{1}{2} & 0 & 0  \\
-& 0 & \frac{1}{3} & \frac{2}{3}
-\end{matrix}
-\right)
-</math></center>
-Jak widać, A jest tutaj funkcją B, a więc <math>I(A;B)=H(A)-H(A|B)=H(A)</math>.
+Czyli aby uzyskać idealną tajność, musimy użyć klucza równie długiego jak przesyłana wiadomość.
-Czyli znów <math> C_{\Gamma } = 1</math>}}
+Jest to oczywiście bardzo niepraktyczne, ale w niektórych zastosowaniach konieczne.
+{{dowod|||Rozpisujemy:
+<center><math>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)}</math></center>
-{{przyklad|[Wadliwa maszyna do pisania]|maszyna_kanal|
+Ale z definicji M jest funkcją (C,K), czyli <math>H(M|C;K)=0</math>. Wymagamy żeby <math>I(M;C)=0</math>, a więc:
-Niech <math>\mathcal{A}=\mathcal{B}=\{a,b,\ldots z\}</math> (załóżmy 26 liter), i
+<center><math>H(M)=I(M;K|C)</math></center>
-<center><math> p (\alpha \to \alpha ) = p (\alpha \to \mathit{next} ( \alpha ) ) = \frac{1}{2}</math></center>
-gdzie
+Rozpisując analogicznie H(K) uzyskujemy:
-<math>\mathit{next} (a) = b</math>,
+<center><math>H(K) = H(K | M,C) + I(K;C) + \underbrace{I(K;M|C)}_{=H(M)}</math></center>}}
-<math>\mathit{next} (b) = c</math>, . . .
-<math>\mathit{next} (y) = z</math>,
-<math>\mathit{next} (z) = a</math>.
-(wyobrażenie sobie reprezentacji grafowej i macierzowej zostawiamy czytelnikowi).
-Aby obliczyć przepustowość, zacznijmy od obserwacji:
+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.
-<center><math>H(B | \alpha ) = p ( \alpha | \alpha ) \cdot \log \frac{1}{p ( \alpha | \alpha )} + p ( \mathit{next} ( \alpha )| \alpha ) \cdot \log \frac{1}{p ( \mathit{next} (\alpha )| \alpha )} = (\frac{1}{2} + \frac{1}{2}) \cdot \log_ 2 = 1</math></center>
-A skoro tak, to możemy łatwo policzyć przepustowość rozpisując ją następująco:
-<center><math>C_{\Gamma } = \max_{A} I(A;B) = \max_{A} H(B) - \underbrace{H(B|A)}_{=1} = \log 26  - 1 = \log 13</math></center>
-(ponieważ możemy uzyskać maksymalną entropię B, np. dla jednostajnego rozkładu prawdopodobieństwa na A).}}
+{{lemat||przetwarzanie|Jeśli A i C są niezależne warunkowo przy danym B (czyli <math>I(A;C|B)=0</math>), to
+<center><math>I(A;C) \le I(A;B)</math>.</center>}}
-Czytelnik być może już ma intuicyjne pojęcie przepustowości kanału jako konkretnej liczby, tak jak informacja lub entropia. Zadamy zatem kolejne pytanie: jakie kanały mają zerową przepustowość?
+{{dowod|||
+Skorzystajmy z zasady łańcuchowej:
+<center><math>\underbrace{I(A; (B,C))}_{=H(A) - H(A|B,C)}= \underbrace{I(A;C)}_{=H(A) - H(A|C)} + \underbrace{I(A; B|C)}_{=H(A|C) - H(A|B,C)}</math></center>
+Z symetrii, używając niezależności warunkowej A i C dostaniemy:
+<center><math> I(A; (B,C)) = I(A;B) + \underbrace{I(A; C | B)}_{=0}</math></center>}}
-'''Złe kanały''' Aby uzyskać <math> C_{\Gamma } = 0</math>, musimy mieć I(A;B)=0 dla dowolnego rozkładu danych wejściowych, czyli pary A i B zawsze muszą być niezależne. Formalnie to wymaganie oznacza że <math>p(B=b|A=a)=p(B=b)</math>, dla wszystkich <math>a \in \mathcal{A}, b \in \mathcal{B}</math>. Przykładowymi złymi kanałami są:
+Zauważmy że nierówność staje się równością, o ile dodatkowo A i B są warunkowo niezależne przy danym C (czyli <math>I(A;B|C)=0</math>).
-<math>\left(
-\begin{matrix}
-\frac{1}{2} & \frac{1}{2} \\
-\frac{1}{2} & \frac{1}{2}
-\end{matrix}
-\right)
-</math>
-<math>\left(
+{{wniosek||do_przetwarzania|Dla dowolnej funkcji f,
-\begin{matrix}
+<center><math>I(A;f(B)) \le I(A;B)</math></center>}}
-\frac{1}{2} & 0 & \frac{1}{6} &\frac{1}{3}  \\
-\frac{1}{2} & 0 & \frac{1}{6} &\frac{1}{3}
-\end{matrix}
-\right)
-</math>
-<math>\left(
+{{dowod|||Na podstawie lematu, gdyż
-\begin{matrix}
+<center><math>I(A; f(B) | B) = \underbrace{H (f(B) | B)}_{=0}-\underbrace{H (f(B) | A, B)}_{=0} = 0 </math></center>}}
-& 0 & 1 \\
-& 0 & 1 \\
-& 0 & 1
-\end{matrix}
-\right)
-</math>
-Ostatni przykład przedstawia szczególnie bezużyteczny kanał, który na wyjściu zawsze daje taką samą wartość. W tym przypadku <math>H(B)=0</math>, co pokazuje że entropia może czasem maleć przy przesyłaniu wiadomości przez kanał. Najbardziej interesujące są jednak przypadki gdy ta entropia rośnie. Jednym z takich przypadków zajmiemy się teraz dokładniej:
-===Binarny kanał symetryczny (BSC)===
+===Kryptografia kwantowa===
-W tym przypadku znów <math>\mathcal{A}=\mathcal{B}=\{0,1\}</math>
+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 <math>I(C;M)=H(M)</math>.
-<center>[[grafika:BSC.PNG]]</center>
+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ć.
-Wprowadzając oznaczenie <math>\bar{P}=1-P</math>, macierz kanału możemy zapisać jako:
-<center><math>\left(
+W kwantowej teorii zastępuje się klasyczne bity ich odpowiednikami, tzw. '''kubitami'''. Kubit jest najmniejszą
-\begin{matrix}
+porcją kwantowej informacji. Tak jak klasyczny bit może przyjmować wartości <math>0</math> i <math>1</math>. W odróżnieniu od niego może jednak przyjmować też dowolną '''superpozycję''' tych wartości, czyli być w stanie „pomiędzy” <math>0</math> a <math>1</math>. Formalnie jego stan można opisać wektorem z dwuwymiarowej przestrzeni
-P & \bar{P} \\
+<center><math>|\psi\rangle = \alpha|0\rangle + \beta|1\rangle</math></center>
-\bar{P} & P
-\end{matrix}
-\right)
-</math></center>
-{{fakt||entropia_BSC|Jeśli (A,B) jest parą wejście-wyjście dla BSC, to
-<center><math> H(B) \ge H(A) </math></center>}}
-Ponadto równości zachodzi wyłącznie jeśli <math>P \in \{0,1\}</math> (czyli kanał jest wierny lub wierny-odwracający), lub jeśli H(A)=1 (czyli entropia A jest maksymalna).
-{{dowod|||Niech <math>q=p(A=0)</math>. Wtedy <math>p(A=1)=\bar{q}</math>, i możemy wyznaczyć rozkład B z formuły:
-<center><math>\left( q, \bar{q} \right)
-\cdot
-\left( \begin{matrix}
-P & \bar{P} \\
-\bar{P} & P
-\end{matrix}
-\right)
-=
-( \underbrace{q P +\bar{q} \bar{P}}_{p(B = 0)},
- \underbrace{q \bar{P} + \bar{q} P}_{p(B = 1)} )
-</math></center>
-Wprowadźmy oznaczenie <math>r=p(B=0)</math>. Wtedy
+gdzie <math>|0\rangle</math> i <math>|1\rangle</math> oznaczają wektory bazowe, a liczby zespolone <math>\alpha</math> i <math>\beta</math> nazywane są ''amplitudami''.
-<center><math>\aligned
-H(A)& =-q \log q - \bar{q} \log \bar{q}\\
-H(B)& =-r \log r - \bar{r} \log \bar{r}
-\endaligned
-</math></center>
-Przypominamy naszą [[Teoria informacji/TI Wykład 2#konwencja_log|konwencję]] <math>0 \log_r 0 = 0 \log_r \frac{1}{0} = 0</math>, i oznaczamy przez h funkcję
-<center><math>h(x)=x \ln x + (1-x) \ln (1-x) </math></center>
-Dla <math> 0 \le x \le 1 </math>. Łatwo możemy policzyć (dla <math> 0<x<1 </math>):
+'''Pomiar''' takiego kubitu daje w wyniku <math>0</math> z prawdopodobieństwem <math>|\alpha|^2</math> i <math>1</math> z prawdopodobieństwem <math>|\beta|^2</math> (zawsze <math>|\alpha|^2+|\beta|^2=1</math>).
-<center><math>\aligned
-h'(x)& =1+\ln x -1 -\ln (1-x)\\
-h''(x)&=\frac{1}{x}+\frac{1}{1-x} > 0
-\endaligned
-</math></center>
-Zatem na podstawie [[Teoria informacji/TI Wykład 2#do_wypukłej|lematu o funkcjach wypukłych]], funkcja <math>h(x)</math> jest ściśle wypukła na przedziale <math>[0,1]</math>, a więc wypukła jest też funkcja
+Po dokonaniu pomiaru stan kubitu ustala się na zmierzonym wektorze (a więc po pomiarze <math>|\psi\rangle = |0\rangle</math> lub <math>|\psi\rangle = |0\rangle</math>). Ta własność jest kluczowa dla bezpieczeństwa kryptografii kwantowej.
-<center><math>\log_2 e \cdot h(x) = x \log_2 x + (1-x) \log_2 (1-x)</math></center>
-Korzystając teraz z faktu że zdefiniowane wyżej r jest kombinacją liniową q i <math>\bar{q}</math> (kontretnie
+Na kubitach można dokonywać operacji ''unitarnych'' (to znaczy takich które nie zmieniają <math>|\alpha|^2+|\beta|^2=1</math>). Przykładem takiej operacji jest ''bramka Hadamarda''
-<math>r=Pq+(1-P)\bar{q}</math>), a <math>h(q)=h(\bar{q})</math>, otrzymujemy
+<center><math> H = \frac{1}{\sqrt{2}}\left( \begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix}\right)</math></center>
-<center><math> q \log q + \bar{q} \log \bar{q} \ge r \log r + \bar{r} \log \bar{r}</math></center>
+Warto zauważyć że ta bramka jest inwolucją
+<center><math> H^2 = \frac{1}{\sqrt{2}} \left( \begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix}\right)\cdot\frac{1}{\sqrt{2}}\left( \begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix}\right)= \frac{1}{2}\left( \begin{matrix} 1+1 & 1-1 \\ 1-1 & 1+1 \end{matrix}\right) = \left( \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right)</math></center>
-<center><math> H(A) \le H(B)</math></center>
+Analogicznie opisuje się układy wielu kubitów: dwa bity mogą przyjmować 4 możliwe wartośći, 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. Jedyne dopuszczalne ingerowanie w takie układy to pomiary oraz operacje unitarne.
-i równość ma miejsce tylko jeśli <math>P \in \{0,1\}</math>, lub jeśli <math>q=q'</math> (czyli gdy <math>H(A)=1</math>).}}
+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]|brak_klonowania|
+Nie istnieje operacja kwantowa kopiująca wiernie dowolne kubity, tzn. taka <math>U</math> że dla dowolnego <math>|\psi\rangle</math>:
+<center><math>U |\psi\rangle |0\rangle = |\psi\rangle |\psi\rangle</math></center>}}
-Wyliczymy teraz <math> C_{\Gamma }</math>. Wygodnie będzie nam używać notacji
-<center><math> H(s) = - s \log_2 s - (1-s) \log_2 (1-s) </math></center>
-(co interpretujemy jako entropię zmiennej binarnej o prawdopodobieństwach s i 1-s).
+Układy wielu kubitów teoretycznie pozwalają na znacznie efektywniejsze obliczenia niż przy użyciu klasycznych komputerów. 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, i istnieją komercyjne urządzenia używające ich do bezpiecznego przesyłania danych. W takich urządzeniach kubity realizowane są jako pojedyncze fotony. Najprostszy protokół ustalania klucza wygląda następująco:
-Z definicji entropii warunkowej dostajemy:
+ '''Protokół BB84'''
+. Gracz A przygotowuje losowy ciąg kubitów z następującym rozkładem:
+ <math>|\psi\rangle=\bigg\{ \begin{matrix} |0\rangle & \mbox{z prawd.} & \frac{1}{2}\\ |1\rangle & \mbox{z prawd.} & \frac{1}{2} \end{matrix}</math>
+. Gracz A do każdego kubitu aplikuje z prawdopodobieństwem <math>\frac{1}{2}</math> bramkę Hadamarda.
+. Gracz A wysyła tak przygotowane kubity do gracza B
+. Gracz B do każdego otrzymanego kubitu aplikuje z prawdopodobieństwem <math>\frac{1}{2}</math> bramkę Hadamarda.
+. Gracz B dokonuje pomiaru wszystkich kubitów.
+. Gracze A i B ogłaszają publicznie do których kubitów aplikowali bramkę Hadamarda
+. 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).
-<center><math>\aligned
+Ustalony w ten sposób klucz gracze mogą wykorzystać do zwykłego zaszyfrowania wiadomości (np. szyfrem Vernama).
-H (B |A)& = p(A = 0) \cdot \left( p (B = 0 | A = 0) \cdot \log \frac{1}{p (B = 0 | A = 0)} + p (B = 1 | A = 0) \cdot \log \frac{1}{p (B = 1 | A = 0)} \right)\\
-& + p(A = 1)  \cdot \left( p (B = 0 | A = 1) \cdot \log \frac{1}{p (B = 0 | A = 1)} + p (B = 1 | A = 1) \cdot \log \frac{1}{p (B = 1 | A = 1)} \right)\\
-& = p(A = 0) \cdot \left( P \cdot \log \frac{1}{P} + \bar{P} \cdot \log \frac{1}{\bar{P}} \right) + p(A = 1) \cdot \left( \bar{P} \cdot \log \frac{1}{\bar{P}} + P \cdot \log \frac{1}{P} \right)\\
-& = P \cdot \log \frac{1}{P} + \bar{P} \cdot \log \frac{1}{\bar{P}}\\
-& = H(P)
-\endaligned
-</math></center>
-A zatem <math>H(B|A)</math> nie zależy od A.
+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ł qubit. W przypadku gdy tylko jeden z graczy zaaplikował bramkę Hadamarda, wynik pomiaru powinien być dokładnie losowy (dać <math>0</math> i <math>1</math> z prawdopodobieństwem <math>\frac{1}{2}</math>).
+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 pokażemy tylko jak to wygląda z punktu widzenia teorii informacji. Jeśli przesyłane pierwotnie wiadomości oznaczymy jako <math>X_A</math>, informacje które docierają do B jako <math>X_B</math> a informacje odczytane przez C jako <math>X_C</math>, to otrzymamy następującą interesującą własność:
+<center><math>H(X_A) \ge I(X_A;X_B) + I(X_A;X_C)</math></center>
-Korzystając z powyższego wyliczenia rozkładu B, mamy
+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ł.
-<center><math> H(B)=H(qP+\bar{q}\bar{P})</math></center>
-Możemy teraz znaleźć rozkład A który maksymalizuję tę wartość (dla <math>q=\frac{1}{2}</math>), i otrzymujemy:
+Inne kwantowe protokoły kryptograficzne wykorzystują teleportację kwantową, ale ich zasada jest bardzo podobna. Bezpieczeństwo zawsze opiera się na zasadzie nieoznaczoności, i odrzucaniu komunikatów które zostały zmodyfikowane przez podsłuchującego.
-<center><math>C_{\Gamma}= \max_{A} H(B) - H(B|A) = 1 - H(P)</math></center>