Vernamova šifra

Vernamova šifra je symetrický šifrovací systém vynalezený v roce 1917 Gilbertem Vernamem [ 1] .

Šifra je typ jednorázového blokového kryptosystému. Používá funkci boolean exclusive-or . Vernamova šifra je příkladem systému s absolutní kryptografickou silou [2] . Zároveň je považován za jeden z nejjednodušších kryptosystémů [3] .

Historie

Poprvé popsal Frank Miller v roce 1882. [4] [5] [6]

Šifra je pojmenována po telegrafistovi Gilbertu Vernamovi , který v roce 1917 vynalezl a v roce 1919 patentoval systém pro automatické šifrování telegrafních zpráv.

Vernam v patentu nepoužil koncept XOR, ale implementoval přesně tuto operaci v žebříkové logice. Každý znak ve zprávě byl bitově XORed (exkluzivní nebo) pomocí klíče papírové pásky [7] . Joseph Mauborgne (tehdejší kapitán americké armády a pozdější náčelník signálního sboru) upravil tento systém tak, aby sekvence znaků na pásce klíče byla zcela náhodná, protože v tomto případě by byla kryptoanalýza nejobtížnější.

Vernam vytvořil zařízení, které tyto operace provádí automaticky, bez účasti kryptografa. Bylo tak zahájeno tzv. „lineární šifrování“, kdy procesy šifrování a přenosu zprávy probíhají současně. Do té doby bylo šifrování předběžné, takže šifrování linky výrazně zvýšilo rychlost komunikace.

Nebýt kryptografa, Vernam si však správně všiml důležité vlastnosti své šifry – každá páska by měla být použita pouze jednou a poté zničena. To je v praxi těžko aplikovatelné – proto byl aparát přeměněn na několik smyčkových pásek s coprime periodami [8] .

Popis

Šifrovací systém byl navržen pro šifrování telegrafních zpráv, což byly binární texty, ve kterých je otevřený text reprezentován v Baudotově kódu (ve formě pětimístné „kombinace pulsů“). V tomto kódu vypadalo například písmeno „A“ (1 1 0 0 0). Na papírové pásce číslo "1" odpovídalo otvoru a číslo "0" - jeho nepřítomnosti. Tajný klíč měl být chaotický soubor písmen stejné abecedy [8] .

Pro získání šifrového textu je prostý text zkombinován s operací XOR s tajným klíčem . Takže například při použití klíče (1 1 1 0 1) na písmeno „A“ (1 1 0 0 0) dostaneme zašifrovanou zprávu (0 0 1 0 1): S vědomím, že za přijatou zprávu mít klíč (1 1 1 0 1), je snadné získat původní zprávu stejnou operací: Pro absolutní šifrovací sílu musí mít klíč tři kritické vlastnosti [2] : $(11000)\oplus (11101)=(00101)$ $(00101)\oplus (11101)=(11000)$

Mít náhodné diskrétní rovnoměrné rozdělení: , kde k je klíč a N je počet binárních znaků v klíči; $P_{k}(k)=1/2^{N}$
mít stejnou velikost jako zadaný prostý text;
Aplikujte pouze jednou.

Známá je také tzv. Vernamova šifra modulo m , ve které znaky otevřeného textu, šifrového textu a klíče nabývají hodnot z kruhu zbytků Z m . Šifra je zobecněním původní Vernamovy šifry, kde m = 2 [2] .

Například Vernamova šifra modulo m = 26 (A=0,B=1,…, Z=25):

Klíč: EVTIQWXQVVOPMCXREPYZ Prostý text: ALLSWELLTHATENDSWELL (Všechno je v pořádku, to končí dobře) Šifrovaný text: EGEAMAIBOCOIQPAJATJK

Při šifrování se transformace provádí podle Vigenèrovy tabulky (sčítání znakových indexů modulo délky abecedy dává této tabulce).

Klíčové písmeno je sloupec, písmeno otevřeného textu je řádek a šifrový text je písmeno na průsečíku.

Bez znalosti klíče nelze takovou zprávu analyzovat. I kdyby bylo možné vyzkoušet všechny klíče, výsledkem by byly všechny možné zprávy dané délky plus kolosální množství nesmyslných dešifrování , které vypadají jako změť písmen. Ale ani mezi smysluplnými dešifrováními by nebylo možné vybrat ten požadovaný. Když je náhodná sekvence (klíč) kombinována s nenáhodnou (prostý text), výsledek ( šifrovaný text ) je zcela náhodný, a proto postrádá statistické rysy, které by bylo možné použít k analýze šifry. [9] .

Kryptografická síla

V roce 1945 napsal Claude Shannon „Matematickou teorii kryptografie“ (odtajněno až po druhé světové válce v roce 1949 jako „ Teorie komunikace v tajných systémech “), ve které dokázal absolutní kryptografickou sílu Vernamovy šifry. To znamená, že zachycení šifrovaného textu bez klíče neposkytuje žádné informace o zprávě. Z hlediska kryptografie nelze uvažovat o systému, který by byl bezpečnější než Vernamova šifra [2] . Požadavky na implementaci takového schématu jsou zcela netriviální, protože je nutné zajistit uložení jedinečné gama rovné délce zprávy s jejím následným zaručeným zničením. V tomto ohledu není komerční využití Vernamovy šifry tak běžné jako schémata veřejného klíče a používá se zejména pro přenos zpráv zvláštního významu vládními úřady [8] .

Předkládáme důkaz absolutní kryptografické síly. Nechť je zpráva reprezentována binární sekvencí délky . Rozdělení pravděpodobnosti zprávy může být jakékoli. Klíč je také reprezentován binární sekvencí stejné délky, ale s rovnoměrným rozložením pro všechny klíče. $N:m=m_{1},m_{2},\ldots ,m_{n}$ $P_{m} (m)$ $k=k_{1},k_{2},\ldots ,k_{n}$ $P_{k}(k)=1/2^{N}$

V souladu se schématem šifrování vytvoříme šifrovaný text součtem modulo 2 sekvencí otevřeného textu a klíče po komponentě:

C=M\oplus K=(m_{1}\oplus k_{1},m_{2}\oplus k_{2},\ldots ,m_{N}\oplus k_{N})

Legální uživatel zná klíč a provede dešifrování:

M=C\oplus K=(c_{1}\oplus k_{1},c_{2}\oplus k_{2},\ldots ,c_{N}\oplus k_{N})

Najděte rozdělení pravděpodobnosti N-bloků šifrových textů pomocí vzorce:

P(c=a)=P(m\plus k=a)=\součet _{m}{P(m)}P(m\plus k=a|m)=\součet _{m} {P(m)1/2^{N}}=1/2^{N}

Výsledek potvrzuje známou skutečnost, že součet dvou náhodných veličin, z nichž jedna má diskrétní rovnoměrné rozdělení na konečné grupě , je rovnoměrně rozdělená náhodná veličina. V našem případě je tedy distribuce šifrových textů rovnoměrná.

Píšeme společnou distribuci holého textu a šifrovaného textu:

P(m=a,c=b)=P(m=a)P(c=b|m=a)

Pojďme najít podmíněné rozdělení

P(c=b|m=a)=P(m\plus k=b|m=a)=P(k=b\plus a|m=a)=P(k=b\plus a)=1 /2^{N},

protože klíč a otevřený text jsou nezávislé náhodné proměnné. Celkový:

P(c=b|m=a)=1/2^{N}

Dosazením pravé strany tohoto vzorce do vzorce společného rozdělení vznikne

P(m=a,c=b)=P(m=a)1/2^{N}

Což dokazuje nezávislost šifrových a otevřených textů v tomto systému. To znamená absolutní kryptografickou sílu [10] .

Rozsah

V současné době se Vernam šifrování používá jen zřídka. Do značné míry je to způsobeno značnou velikostí klíče, jehož délka musí odpovídat délce zprávy. To znamená, že použití takových šifer vyžaduje obrovské náklady na výrobu, skladování a zničení klíčových materiálů. Přesto zcela silné šifry jako Vernam stále nacházely praktické využití pro ochranu kritických komunikačních linek s relativně malým množstvím informací. Například Britové a Američané používali šifry typu Vernam během druhé světové války. Šifra modulo 2 Vernam byla použita na vládní horké lince mezi Washingtonem a Moskvou, kde klíčovými materiály byly papírové pásky, na kterých byly perforovány znaky sekvence kláves [2] .

V praxi je možné jedenkrát fyzicky přenést nosič informací dlouhým skutečně náhodným klíčem a poté přeposílat zprávy podle potřeby. Myšlenka šifrovacích bloků je založena na tomto : šifrovací úředník dostane diplomatickou poštou nebo osobně zápisník, jehož každá stránka obsahuje klíče. Přijímající strana má stejný poznámkový blok. Použité stránky jsou zničeny [11] .

Nevýhody

Aby Vernamova šifra fungovala, je potřeba skutečně náhodná sekvence ( klíč ) . Podle definice není sekvence získaná pomocí jakéhokoli algoritmu skutečně náhodná, ale pseudonáhodná. To znamená, že potřebujete získat náhodnou sekvenci nikoli algoritmicky, ale například pomocí radioaktivního rozpadu vytvořeného elektronickým generátorem bílého šumu nebo jinými docela náhodnými událostmi. Aby se distribuce co nejvíce přiblížila stejnoměrnosti , náhodná posloupnost se obvykle předává pomocí hashovací funkce, jako je MD5 [12] .

Nevýhodou použití Vernamovy šifry je chybějící potvrzení pravosti a integrity zprávy. Příjemce nemůže ověřit nepřítomnost poškození nebo pravost odesílatele. Pokud třetí strana nějakým způsobem rozpozná zprávu, snadno obnoví klíč a bude moci nahradit zprávu jinou o stejné délce. Řešením problému je použití hashovací funkce. Hašovací funkce se vypočítá z prostého textu a její hodnota se zašifruje spolu se zprávou. Jakákoli změna ve zprávě změní hodnotu hash. I když se tedy útočníkovi dostane do rukou šifrovací blok, aniž by znal algoritmus pro výpočet hashovací funkce, nebude jej moci použít k přenosu informací [11] .

Vždy je nutné mít po ruce dostatečný počet klíčů, které mohou být v budoucnu potřeba pro šifrování velkého množství otevřeného textu. Skutečný objem textu je často obtížné předem odhadnout, zejména v diplomatické a vojenské sféře, kde se situace může rychle a nepředvídatelně změnit. To může vést k nedostatku klíčů, což může způsobit, že kryptograf klíč (klíče) buď znovu použije, nebo šifrovanou komunikaci úplně přeruší.

Problémem je bezpečný přenos sekvence a její utajení. Pokud existuje kanál pro přenos zpráv, který je spolehlivě chráněn před zachycením, nejsou šifry vůbec potřeba: tímto kanálem lze přenášet tajné zprávy. Pokud je však klíč systému Vernam přenášen pomocí jiné šifry (například DES ), bude výsledná šifra chráněna přesně tak, jako je chráněna DES. Zároveň, protože délka klíče je stejná jako délka zprávy, není o nic jednodušší jej přenést než zprávu. Šifrovací blok na fyzickém médiu lze ukrást nebo zkopírovat [11] .

Vernamova šifra je citlivá na jakékoli porušení šifrovací procedury. Byly případy, kdy byla stejná stránka poznámkového bloku z různých důvodů použita dvakrát. Například mezi celým objemem sovětské šifrované korespondence zachycené americkou rozvědkou ve 40. letech minulého století byly nalezeny zprávy, které byly uzavřeny dvakrát použitou gama. Toto období netrvalo příliš dlouho, protože již po prvních úspěších amerických kryptoanalytiků na konci 40. let se tajné služby SSSR dozvěděly o vážných problémech se spolehlivostí jejich šifrované korespondence. Takové zprávy byly dešifrovány během následujících 40 let v rámci tajného projektu Venona , jehož dokumenty byly později odtajněny a umístěny na web NSA [13] .

Poznámky

↑ Symetrické algoritmy .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Mao, 2005 .
↑ Miller, Frank. Telegrafický kód pro zajištění soukromí a utajení při přenosu telegramů. — C. M. Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: Vynálezce One-Time Pad . kryptologie . 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . Číselník zobrazuje data šifrovacího formuláře Zpět na telegrafy (25. července 2011). Staženo 26. července 2011.
↑ Patent USA 1310719A
↑ 1 2 3 Babash, et al., 2003 .
↑ Kryptografie (nepřístupný odkaz) . Datum přístupu: 8. února 2014. Archivováno z originálu 2. listopadu 2013. (neurčitý)
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , str. 41-43.
↑ 1 2 3 Jednorázová podložka .
↑ Často kladené otázky .
↑ Kiwi, 2005 .

Literatura

Fomichev V. M. Diskrétní matematika a kryptologie : Kurz přednášek / ed. N. D. Podufalov - M. : Dialog-MEPhI , 2013. - S. 239-246. — 397 s. — ISBN 978-5-86404-185-7
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informační bezpečnost : učebnice - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Mao V. Moderní kryptografie : Teorie a praxe / přel. D. A. Klyushina - M. : Williams , 2005. - S. 255. - 768 s. — ISBN 978-5-8459-0847-6
Robert L. Benson. The Venona Story (anglicky) // Centrum pro kryptologickou historii Národní bezpečnostní agentura. Archivováno z originálu 27. května 2010.
Babash A. V. , Goliev Yu. I. , Larin D. A. , Shankin G. P. Kryptografické myšlenky 19. století // Informační bezpečnost. Důvěrník - Petrohrad. : 2004. - vydání. 3.

Odkazy

Symetrické algoritmy (ruština) .
Dirk Rijmenants. Jednorázová podložka (anglicky) .
Marcus J. Ranum. Často kladené otázky One-Time-Pad ( Vernamova šifra) .
Byrd Kiwi. Cenové chyby . - 2005. Archivováno 24. prosince 2013.