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