Představte si takovouto hru:
Eve poví Bobovi, aby šel do pokoje.
Bob zjistí, že v pokoji nic není,
kromě několika zámků, prázdné skříňky a balíku karet.
Eve řekne Bobovi, aby vybral kartu
a co nejlépe ji ukryl.
Pravidla jsou jednoduchá.
Bob nemůže z místnosti nic odnést.
Nesmí sebou vzít ani karty nebo klíče.
a do skříňky může dát jen jednu kartu.
Eve odpřísáhla, že zámky nikdy ani neviděla.
Bob vyhraje, když Eve nedokáže určit jeho kartu.
Jak by tedy měl postupovat?
Bob si vybral károvou šestku
a vložil ji do skříňky.
Nejdříve přemýšlel nad různými zámky.
Možná by měl zamknout kartu v krabičce zámkem s klíčem.
Jenže Eve dokáže zámky vypáčit.
Zvažuje i použití kombinačního zámku.
Kód je na zadní straně,
takže uzamčení a seškrábání kódu zní jako nejlepší možnost.
Ale pak si uvědomí problém.
Karty, které zůstaly na stole poskytují informaci o jeho volbě,
protože jedna karta v balíku chybí.
Zámky jsou návnada.
Neměl by kartu oddělit od balíku.
Vrátí tam tedy svoji kartu.
Ale nepamatuje si její pozici v balíku.
Tak zamíchá kartami, aby byly rozmístěné náhodně.
Míchání je nejlepším zámkem,
neboť nezanechává žádné informace o jeho volbě.
Teď může být jeho karta jakoukoliv kartou v balíku.
Může takto karty bezpochyby zanechat.
Bob hru vyhraje,
protože Eve může jen hádat.
Bob totiž nezanechal žádnou informaci o jeho volbě.
Ale hlavně,
i kdyby měla Eve neomezenou výpočetní sílu,
stále by mohla jen hádat.
To se nazývá dokonalé zabezpečení.
1. září 1945 zveřejnil 29 letý Claude Shannon
tajnou práci o této myšlence.
Shannon poprvé matematicky dokázal,
proč a jak je Vernamova šifra úplně bezpečná.
Shannon o šifrování přemýšlel takto:
Představte si, že Alice píše Bobovi zprávu o 20 písmenech.
To je jakoby vybrala 1 specifickou stránku z prostoru zpráv.
Prostor zpráv si můžeme představit jako
kompletní soubor všech zpráv o 20 písmenech.
Vše, co má délku 20 písmen
je stránkou v této hromadě.
Následně Alice použije společný klíč,
tedy seznam 20 náhodných posunů mezi 1 a 26.
Prostor klíčů je sbírka všech možných výstupů.
Takže vytvoření klíče je stejné
jako náhodný výběr z hromady.
Když Alice použije posuny na šifrování,
vznikne šifrovaný text.
Prostor šifrovaných zpráv reprezentuje
všechny možné výsledky šifrování.
Když použije klíč,
dostane se k jedinečné stránce v hromadě.
Všimněte si, že velikost prostoru zpráv
je stejná jako velikost prostoru klíčů i prostoru výsledných zašifrovaných zpráv.
To definuje takzvané dokonalé zabezpečení.
Pokud má někdo přístup k zašifrovanému textu,
tak jedinou věc, kterou ví je, že každá zpráva je stejně pravděpodobná.
Takže žádná výpočetní síla nám nepomůže zpřesnit naše hádání.
Velký problém Vernamovy šifry je způsob předchozího předání dlouhého klíče.
Abychom tento problém vyřešili,
musíme zvolnit u naší definice zabezpečení
vytvořením definice pseudo-náhodnosti.