-
Pomyślcie o następującej grze.
-
Ewa każe Bobowi wejść do pokoju.
-
Bob widzi, że nie ma tam nic
poza kilkoma kłódkami,
-
pustym pudełkiem i talią kart.
-
Ewa każe Bobowi wybrać kartę z talii
-
i jak najlepiej ją ukryć.
-
Zasady są proste. Bob nie może
niczego stamtąd wynieść;
-
karty i kluczyki zostają w pokoju;
-
do pudełka można włożyć
co najwyżej jedną kartę.
-
Ewa mówi, że nigdy
nie widziała tych kłódek.
-
Bob wygra, jeśli Ewa nie zdoła
określić, którą wybrał kartę.
-
Jaka będzie najlepsza strategia?
-
Bob wybrał kartę, szóstkę karo,
i wrzucił ją do pudełka.
-
Najpierw pomyślał
o różnych typach zamków.
-
Może powinien zamknąć kartę
w pudełku na klucz?
-
Ale Ewa może mieć wytrych,
więc Bob myśli o zamku cyfrowym.
-
Klucz jest z tyłu. Najlepiej będzie
zamknąć i pomieszać cyfry.
-
Nagle Bob coś sobie uświadamia:
-
pozostałe karty na stole
przekażą informację o jego wyborze,
-
bo teraz jednej brakuje.
-
Zamki służą odwróceniu uwagi!
-
Nie powinien wyciągać
karty z talii.
-
Wkłada ją z powrotem.
Nie pamięta, gdzie dokładnie była.
-
Tasuje więc karty
dla większej losowości.
-
Tasowanie to najlepszy zamek,
-
bo nie pozostawia
informacji o wyborze.
-
Teraz jego karta
może być każdą w talii.
-
Bob może zostawić karty na wierzchu.
-
Bob wygrywa, ponieważ Ewa
może co najwyżej zgadywać.
-
Nie pozostawił informacji
o swoim wyborze.
-
Co ważniejsze, nawet jeśli damy Ewie
nieograniczoną moc obliczeniową,
-
będzie ona mogła tylko zgadywać.
-
To właśnie jest tzw.
„tajność doskonała”.
-
1 września 1945 r.
29-letni Claude Shannon
-
opublikował utajniony
artykuł na ten temat.
-
On pierwszy
matematycznie dowiódł,
-
że szyfr z kluczem jednorazowym
jest doskonale tajny.
-
Oto, jak Shannon myślał
o schematach szyfrowania.
-
Wyobraźcie sobie, że Alicja pisze
20-literową wiadomość do Boba.
-
To ekwiwalent wybrania
jednej kartki
-
z przestrzeni wiadomości.
-
A przestrzeń wiadomości
to kompletny zbiór
-
wszystkich możliwych
wiadomości 20-literowych.
-
Wszystko 20-literowe, co przyjdzie wam
do głowy, jest kartką w tym stosie.
-
Teraz Alicja stosuje wspólny klucz,
-
listę 20 losowo wygenerowanych
podstawień między 1 a 26.
-
Przestrzeń kluczy jest zbiorem
wszystkich możliwych wyników,
-
więc wygenerowanie klucza
to ekwiwalent
-
losowego wyboru strony z tego stosu.
-
Alicja stosuje klucz
do zakodowania wiadomości
-
i uzyskuje szyfrogram.
-
Przestrzeń szyfrogramów to wszystkie
możliwe wyniki szyfrowania.
-
Zastosowanie klucza odeśle Alicję
do jednej kartki z tego stosu.
-
Zauważcie, że przestrzeń
wiadomości
-
ma wielkość przestrzeni kluczy
-
i przestrzeni szyfrogramów.
-
To definiuje „tajność doskonałą”.
-
Bo jeśli ktoś ma dostęp wyłącznie
do strony z szyfrogramem,
-
to wie tylko, że każda wiadomość
jest równie prawdopodobna.
-
Żadna moc obliczeniowa
nie poprawi skuteczności zgadywania.
-
Problem z kluczem jednorazowym
jest taki, że musimy
-
wcześniej przekazać
sobie długie klucze.
-
By rozwiązać ten problem,
musimy zmienić definicję tajności,
-
wprowadzając pseudolosowość.
