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