Vernamova šifra

Vernamova šifra nebo také jednorázová tabulková šifra (anglicky one-time pad) je jednoduchý šifrovací postup patentovaný v roce 1917 Gilbertem Vernamem. Spočívá v posunu každého znaku zprávy o náhodně zvolený počet míst v abecedě. To se prakticky rovná náhradě zcela náhodným písmenem a na tomto faktu je založen důkaz, že Vernamova šifra je v principu nerozluštitelná.

Postup šifrování

Vezmeme jednotlivá písmena tajné zprávy a každé z nich posuneme o několik pozic v abecedě. Například první písmeno je posunuto o 5 pozic, druhé o 1, třetí o 14, čtvrté o 24, další o 9, 0, 3, 9, 19. Když při posouvání překročíme konec abecedy, pokračujeme od jejího začátku. Ze slova ALDEBARAN tak dostaneme šifrový text FMRCKAUJG. Posloupnost 5, 1, 14, 24, 9, 0, 3, 9, 19 je klíčem k rozluštění zprávy. Kdo ji zná, dokáže snadno posunout písmena opačným směrem a získat původní text. Bez znalosti klíče je luštění odposlechnuté zprávy nemožné.

Podmínky spolehlivosti

Porušení kterékoli z následujících podmínek má za následek oslabení šifry, takže by již nebyla nerozluštitelná.

Klíč je tak dlouhý jako přenášená zpráva. Jiné šifrovací systémy používají kratší klíče, což znamená, že počet možných klíčů je menší než počet možných zpráv. Kratší klíč v principu umožňuje útok hrubou silou.
Klíč je dokonale náhodný. Nepřipadají v úvahu počítačové generátory pseudonáhodných čísel, neboť jejich činnost lze předvídat. Nejvhodnější je užití fyzikálních metod - hardwarový generátor náhodných čísel.
Klíč nelze použít opakovaně. Tato podmínka je vlastně důsledkem předchozí, protože opakovaný klíč není náhodný. Dostane-li útočník do ruky dvě zprávy zašifrované týmž klíčem, má často velmi snadnou cestu k rozluštění.

Možnosti útoku

Statistická kryptoanalýza je znemožněna náhodným charakterem šifrového textu. Nelze z něj zjistit žádné informace o četnosti znaků v původní zprávě ani vztahy mezi skupinami znaků apod., protože z každého písmene vznikne jiné zcela náhodně volené písmeno.

Ani útok hrubou silou, vůči kterému není odolná prakticky žádná jiná šifra, neuspěje. I kdyby měl útočník k dispozici neomezený výpočetní výkon, kvantové počítače a podobně a mohl systematicky vyzkoušet všechny možné klíče délky $n$ , pak výsledkem snažení bude pouze posloupnost všech možných zpráv délky $n$ . Nebude schopen mezi nimi nalézt tu správnou, nezíská o ní žádnou informaci. Ani pořadí, v jakém zprávy získal, neřekne útočníkovi nic, neboť za předpokladu náhodné volby klíče je také zcela náhodné.

Důkaz spolehlivosti

Gilbert Vernam tvrdil, že si je jist, že jeho šifra je nerozluštitelná. S exaktním důkazem ale přišel až C. E. Shannon v roce 1949. Důkaz je založen na tom, že náhodný posun v abecedě se rovná nahrazení zcela náhodným písmenem, a šifrovaný text proto nelze odlišit od zcela náhodné posloupnosti. Považujeme-li tajnou zprávu za náhodnou veličinu $A$ a klíč za náhodnou veličinu $B$ , která má rovnoměrné rozložení a je nezávislá na $A$ , pak zašifrovaná zpráva je také náhodou veličinou s rovnoměrným rozložením, která je nezávislá na $A$ . Jinými slovy šifrový text neobsahuje žádnou informaci o původní zprávě, a proto útočník v principu nemá šanci cokoli zjistit.

Binární varianta

Dodejme, že Vernamova šifra funguje beze změn nad jakoukoliv množinou znaků, například jen 0 a 1. (To je důležité pro digitální počítače pracující ve dvojkové soustavě.) Posun písmen nad dvouznakovou abecedou je možný pouze o 1 místo nebo 0 míst, klíčem je tedy také posloupnost 0 a 1. Každý bit klíče odpovídá jednomu bitu zprávy a říká, zda se tento bit má při šifrování změnit nebo nechat. Tato jednoduchá operace se dvěma bity se jmenuje XOR (výlučné nebo, angl. exclusive or, značka ⊕). K dešifrování stačí vzít šifrovaný text a provést XOR znovu se stejným klíčem, což se projeví jako posun písmen opačným směrem. Změněné bity se změní zpět, nezměněné zůstanou.

Opakování klíče

Binární varianta je obzvláště citlivá na opakované použití klíče. Důvodem je následující vlastnost operace XOR: $(A\oplus X)\oplus (B\oplus X)=A\oplus B$ . Když má tedy útočník v ruce dvě zprávy šifrované týmž klíčem a provede s nimi XOR, dostane XOR dvou původních zpráv a zbaví se veškeré náhodnosti, která spočívala v klíči a která dává šifře její sílu. Statistická kryptoanalýza mu pak už docela lehce umožní zprávy přečíst.

Praktické použití

Popsané zacházení s klíčem je v praxi velice obtížné. Dlouhý náhodný klíč si člověk nedokáže zapamatovat, musí být zaznamenán. Jeho generování není jednoduché. Musí být zajištěno, že klíč zná pouze odesilatel a příjemce zprávy a nikdo jiný. Komunikující strany se tedy musí předem dohodnout na dlouhém klíči nějakým bezpečným způsobem a hned po odeslání první zprávy klíč zničit. Abychom mohli bezpečně odeslat třeba 2 MB tajných dat, musíme předem bezpečně odeslat 2 MB dat (klíč). Vernamova šifra se tak i přes svou sílu používala jen výjimečně, například pro krytí horké linky mezi Moskvou a Washingtonem za studené války. Také někteří špioni tuto šifru využívali. Dnešní historici mají několik zpráv zašifrovaných tímto způsobem a nemají k dispozici klíč. Tajný text v tom případě zůstane skryt navěky.

Nové výhledy na řešení problému distribuce klíče dala Vernamově šifře kvantová kryptografie, která matematickou nepodmíněnou bezpečnost Vernamovy šifry doplňuje nepodmíněně bezpečnou fyzikální metodou přenosu informace.

Odkazy

Literatura

Simon Singh: Kniha kódů a šifer, Dokořán, 2003

Související články

Externí odkazy

Vojtěch Hála: Kvantová kryptografie – Aldebaran bulletin 14/2005