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ść.