The one-time pad | Journey into cryptography | Computer Science | Khan Academy

Przez ponad czterysta lat, ten sam problem pozostawał nierozwiązany.

Jak Alicja może zaprojektowac szyfr, który ukryłby jej "odciski"

i tym samym zatrzymał wyciek informacji.

Odpowiedzią jest losowość.

Wyobraź sobie, że Alicja rzuca 26-ścienną kością

aby wygenerować długą listę losowych przesunięć,

i dzieli się tym z Bobem, zamiast szyfrującego słowa.

Teraz, aby zaszyfrować jej wiadomośc,

Alicja używa listy losowych przesunięć.

Ważne jest to, że lista przesunięć jest tak długa jak wiadomość

aby uniknąć powtórzeń.

Nastepnie, wysyła to do Boba, który odszyfrowywuje wiadomość

używając tej samej listy losowych przesunięć, jaką mu ona dała.

Teraz Ewa będzie miała problem,

ponieważ zaszyfrowana wiadomość

będzie miała dwie potężne właściwości:

Po pierwsze, przesunięcia nigdy nie będą się układały w powtarzające schematy;

i po drugie, zaszyfrowana wiadomość będzie miała jednolity rozkład częstotliwości.

Ponieważ nie ma różnicy w częstotliwości,

nie ma wycieku informacji,

i jest niemożliwym dla Ewy złamanie tego szyfru.

Jest to najsilniejsza z możliwych metod zaszyfrowania,

i pochodzi z końca 19 wieku.

Jest dziś znana jako szyfr z kluczem jednorazowym.

Aby zobraziwać siłę szyfru z kluczem jednorazowym,

musimy zrozumieć jaka kombinatoryczna ekslozja ma tu miejsce.

Dla przykładu, szyfr Cezara przesuwał każdą literę tym samym przesunięciem,

którym była liczba pomiędzy 1 a 26.

Więc gdyby Alicja chciała zaszyfrowac swoje imię,

otrzymała by jeden z 26 możliwych zaszyfrowań,

małą liczbę możliwości, łatwe do sprawdzenia ich wszystkich,

znane jako poszukiwanie na siłę (brute-force).

Porównajmy to z szyfrem z kluczem jednorazowym,

gdzie każda litera zostaje przesunięta

przez inną liczbę pomiędzy 1 a 26.

Jeśli zastanowimy się nad ilością możliwych szyfrowań,

otrzymamy 26 pomnożone przez siebie 5 razy,

czyli prawie 12 milionów.

Czasem to ciężko zobrazować.

Więc wyobraź sobie, że napisała swoje imię na pojedynczej kartce

i na jej wierzchu postawiła każde możliwe zaszyfrowanie.

Jak wysoko będzie to sięgać?

Z niemal 12 milionami możliwych pięcioliterowych sekwencji,

stos papieru byłby ogromny,

wysokości ponad kilometra.

Jeśli Alicja zaszyfruje swoje imię używając szyfru z kluczem jednorazowym,

to jak wybieranie jednej z tych kartek losowo,

z punktu widzenia Ewy, chcącej złamać ten szyfr,

każde pięć liter zaszyfrowanego słowa jakie ma

jest z równym prawdopodobieństwem dowolnym słowem ze stosu.

Zatem, jest to doskonała dyskrecja.