Termíny
-
odesílatel a příjemce zprávy
-
κρύπτω - řecky skrývám
-
zpráva, otevřený text, šifrovaný text, zašifrování (šifrování), rozšifrování (dešifrování)
Odesílatel chce poslat zprávu příjemci, ale chce ji poslat bezpečně, to znamená, že si chce být jistý, že nikdo cizí nebo nepovolaný zprávu nepřečte.
Zprávu, kterou chceme skrýt, označujeme jako otevřený text nebo nešifrovaný text, angl. plaintext. Převod otevřeného textu v text nečitelný pro cizí označujeme jako zašifrování nebo prostě šifrování (angl. encryption). Zašifrovanou zprávu označujeme jako šifrovaný text (angl. ciphertext) a převod šifrovaného textu do původní zprávy jako rozšifrování nebo dešifrování (angl. decryption).
Kryptografie je umění nebo věda, jak udržet zprávy zabezpečené. Kryptoanalýza je umění nebo věda, jak šifrovaný text rozluštit.
Otevřený text označujeme jako M (message) nebo P (plaintext), může to být proud bitů, textový soubor, bitmapa, proud digitalizovaného hlasu, video, prostě cokoliv. Otevřený text v počítačovém světě jsou jednoduše binární data. Šifrovaný text označujeme C (ciphertext) a jsou to opět binárná data. Mohou být někdy stejné velikosti jako otevřený text, někdy větší. Pokud se použije současně se šifrováním komprese, tak menší. Samotné šifrování však nekomprimuje, to je přidaná funkce.
Šifrovací funkce E pracuje s otevřeným textem M a vytváří šifrovaný text C, v matematickém zápisu to je:
\$E(M)=C\$
Obráceně funkce pro rozšifrování D pracuje s šifrovaným textem a vytváří původní text.
\$D(C)=M\$
Protože cílem zašifrování a rozšifrování je znovu sestavit původní zprávu, musí platit:
\$D(E(M))=M\$
Potvrzení pravosti (authentication), celistvost (integrity), nemožnost odmítnout (nonrepudiation)
Od kryptografie je kromě utajení informací požadováno i následující:
-
potvrzení pravdivosti (authentication) - pro příjemce zprávy je důležité, že si může být jistý o tom kdo mu poslal zprávu. Útočník se nemůže maskovat za toho, kdo mu poslal zprávu.
-
celistvost (integrity) - pro příjemce zprávy musí být možné, aby mohl zkontrolovat, zda zpráva nebyla nějak změněna během přenosu. Útočník by neměl mít šanci podstrčit falešnou zprávu za pravou.
-
nemožnost odmítnout (nonrepudiation) - odesílatel zprávy by neměl mít možnost později lživě namítnout, že zprávu neposlal.
Toto jsou životně důležité požadavky pro sociální interakci pomocí počítačů a jsou analogické se vzájemnou komunikací z očí do očí.
Algoritmy a klíče
Kryptografický algoritmus se nazývá také šifra. Je to matematická funkce použitá k zašifrování a rozšifrování. (Všeobecně jsou to dvě svázané funkce, jedna pro zašifrování a druhá pro rozšifrování).
Je-li bezpečnost algoritmu založena na tom, že nikdo neví (kromě odesílatele a příjemce), jak algoritmus funguje, pak se takový algoritmus nazývá omezený algoritmus.
Omezené algoritmy byly zajímavé v historii, ale jsou žalostně neadekvátní k dnešním požadavkům. Velká nebo měnící se skupina uživatelů je nemůže používat, protože pokaždé, když nějaký uživatel opustí skupinu, všichni ostatní musí začít používat jiný algoritmus. To samé, když někdo náhodně provalí tajemství, všichni musí změnit algoritmus.
Daleko horší je, že omezené algoritmy nelze nijak zkontrolovat, jestli jsou kvalitní a nemají nějaké zásadní díry. Každá skupina uživatelů musí mít svůj unikátní algoritmus. Tato skupina nemůže používat běžný hardware a software, ale slídil si může koupit jejich zažízení a prostudovat algoritmus. Každá skupina si musí napsat svůj vlastní algoritmus a implementovat ho. Pokud ve skupine není dobrý kryptograf, tak si nemohou být jisti, že mají bezpečný algoritmus a bezpečný systém.
Přes tyto hlavní nedostatky, omezené algoritmy jsou extrémně populární v aplikacích s nízkou bezpečností. Uživatelé nevědí nebo je nezajímají bezpečnostní problémy neoddělitelně spjaté s jejich systémem.
Moderní kryptografie řeší tento problém klíčem (key), označovaným jako K. Tento klíč může být kterákoliv hodnota z velkého počtu čísel. Rozsah možných hodnot klíče se nazývá klíčový prostor (keyspace). Obě funkce zašifrování a rozšifrování pracují s tímto klíčem, t.j. jsou závislé na klíči a jsou označovány dolním indexem K, takže matematicky to vypadá takto:
\$E_K(M)=C\$
\$D_K(C)=M\$
Tyto funkce mají vlastnost: \$D_K(E_K(M))=M\$
Některé algoritmy používají pro zašifrování jeden klíč a pro rozšifrování druhý klíč, to znamená šifrovací klíč \$K_1\$ je odlišný od odpovídajícího dešifrovacího klíče \$K_2\$.
V tomto případě bude zápis funkcí tento:
\$E_{K_1}(M)=C\$
\$D_{K_2}\(C)=M\$
\$D_{K_2}(E_{K_1}(M))=M\$
Celá bezpečnost těchto algoritmů je založena na klíči (nebo na klíčích) a nezávisí příliš na detailech algoritmu. To znamená, že algoritmus může být veřejný a může být veřejně analyzován na nedostatky.
A může být použit pro masovou produkci. Nezáleží na tom, že slídil zná algoritmus, pokud nezná váš určitý klíč, nemůže číst zprávu.
Tady je nutné podotknout, že všechny počítačové systémy s uzavřenými zdrojovými kódy (MS Windows, Apple iOS a další), přestože pravděpodobně používají veřejné kryptografické algoritmy, tak implementace těchto algoritmů nemůže být veřejně zkontrolována a tudíž může obsahovat chyby, které útočníci nezřídka používají k prolamování systému a jiným neplechám. Z hlediska bezpečnosti to degraduje všechny tyto systémy na *omezené algoritmy*.
Kryptosystém je souhrn algoritmů plus všechny možné otevřené texty, šifrované texty a klíče.
Existují v zásadě dva typy algoritmů, symetrické a s veřeným klíčem.
Symetrické algoritmy (Symetric Algorithms)
Symetrické algoritmy se někdy též nazývají konvenční algoritmy, a jsou to takové algoritmy kde dešifrovací klíč může být spočítán ze šifrovacího klíče a obráceně. U většiny symetrických algoritmů je šifrovací a dešifrovací klíč jeden identický. Tyto algoritmy se také nazývají jako algoritmy s tajným klíčem (secret-key algorithms), s jedním klíčem (single-key algorithms nebo one-key algorithm). Vyžadují, aby se odesílatel s příjemcem dohodnul předem na tajném klíči, než začnou vzájemně komunikovat. Bezpečnost symetrického algoritmu spočívá v jeho klíči, prozrazení klíče znamená, že kdokoliv může rozšifrovat nebo zašifrovat zprávu. Komunikace je bezpečná bezpečná do té doby, dokud klíč zůstává tajný.
Zašifrování a rozšifrování pomocí symetrického klíče se zapisuje takto:
\$E_K(M) = C\$
\$D_K(C) = M\$
Symetrické algoritmy mohou být dále rozděleny do dvou kategorií:
-
Některé algoritmy pracují s otevřeným textem po bitech (nebo bytech) a takové se nazývají proudové algoritmy (stream algorithms) nebo proudové šifry (stream ciphers).
-
Jiné algoritmy pracují s otevřeným textem ve skupinách bitů, v blocích. Takové se nazývají blokové algoritmy (block algorithms) nebo blokové šifry (block ciphers). V moderních počítačích je blok obvykle 64bitů.
Když nebyly k dispozici počítače, tak symetrické algoritmy obvykle pracovaly s otevřeným textem po znacích a můžeme si o nich myslet, že to jsou proudové algoritmy pracující s proudem znaků.
Algoritmy s veřejným klíčem (Public-Key Algorithms)
Algoritmy s veřejným klíčem (také nazývané asymetrické algoritmy) jsou navrženy tak, že klíč pro zašifrování je odlišný od klíče pro rozšifrování. Dále dešifrovací klíč nemůže být spočítán (v rozumném čase) ze šifrovacího klíče. Algoritmus se nazývá s veřejným klíčem proto, že šifrovací klíč je možno zveřejnit. Zcela neznámý cizinec může vzít šifrovací klíč (public-key), zašifrovat s ním zprávu, ale jenom osoba, která vlastní příslušný dešifrovací klíč, může rozšifrovat zprávu a přečíst si ji. Šifrovací klíč se nazývá veřejný klíč (public key) a dešifrovací klíč se nazývá soukromý klíč (private key).
Zašifrování pomocí veřejného klíče příjemce K se popisuje takto:
\$E_K(M)=C\$
Přestože veřejný a soukromý klíč jsou různé, dešifrování pomocí odpovídajícího sourkromého klíče přijemce se zapisuje takto:
\$D_K(C)=M\$
Někdy je zpráva zašifrována pomocí soukromého klíče odesílatele a dešifrována pomocí jeho veřejného klíče. Toto se používá jako digitální podpis. Přestože může vzniknout nedorozumnění, tak se tato operace popisuje takto:
\$E_K(M)=C\$
\$D_K(C)=M\$
Kryptoanalýza
Účelem kryptografie je udržet otevřený text nebo klíč či oboje v tajnosti od slídila (může se nazývat protivník, soupeř, útočník, nabourávač, zachycovač, oponent nebo prostě nepřítel). U slídila předpokládáme, že má k dispozici kompletní komunikaci mezi odesíletelem a příjemcem.
Kryptoanalýza (cryptoanalysis) je věda, která se snaží získat otevřený text zprávy bez přístupu ke klíči. Úspěšný kryptoanalytik může získat buď otevřený text nebo klíč. Může navíc objevit slabosti v kryptosystému, které eventuelně vedly k předchozím výsledkům. Ztráta klíče bez toho, ža by byla použita kryptoanalýza se nazývá kompromitace (compromise).
Použitá kryptoanalýza se nazývá útok (attack). Základní předpoklad kryptoanalýzy, poprvé jasně formulovaný Holanďanem Augustem Kerckhoffsem v 19. století je, že bezpečnost musí ležet výhradně v klíči. Dále Kerckhoffs předpokládá, že kryptoanalytici znají kompletně detaily kryptografického algoritmu a implementace. (Jistě, někdo může předpokládat, že CIA nemá ve zvyku hovořit s Mossadem o svých krypto algoritmech, ale Mossad pravděpodobně má způsoby, jak tyto algoritmy najít.) V reálnosti kryptoanalytici nemají vždy detailní údaje o celém kryptosystému, ale je dobré předpokládat, že je mají. Jestliže nikdo nemůže zlomit algoritmus, přestože má znalosti o tom, jak algoritmus funguje, tak zcela jistě ho nezlomí někdo, kdo tyto znalosti nemá.
Poznámka: Kerckhoffsovy principy (2. je nejdůležitější) 1.Systém by měl být, když ne teoreticky nerozbitný, nerozbitný v praxi. 2. Návrh systému by neměl vyžadovat utajení a kompromitace systému by neměla obtěžovat korespondenty. 3. Klíč by měl být zapamatovatelný bez poznámek a měl by být snadno vyměnitelný. 4. Kryptogramy by měly být přenosné telegraficky. 5. Přístroj nebo dokumenty by měly být přenosné a obsluhovatelné jednou osobou. 6. Systém by měl být jednoduchý, nevyžadující znalost dlouhého seznamu pravidel ani psychickou zátěž.
Všeobecně existují čtyři druhy hlavních kryproanalytických útoků a tři ostatní
-
Útok pouze na šifrovaný text (Ciphertext-only attack)
Kryptoanalytik má několik šifrovaných textů, všechny zašifrované stejným algoritmem. Úkol kryptoanalytika spočívá v tom, rozluštit co možná nejvíce otevřeného textu a nebo lépe odvodit klíč (nebo klíče), kterými byly zašifrovány zprávy.
Je dáno: \$C_1 = E_k(P_1), C_2=E_k(P_2), ... C_i=E_k(P_i)\$
Je třeba najít: buď \$P_1, P_2 ... P_i; k;\$ nebo algoritmus, který odvozuje \$P_{i+1}\$ z \$C_{i+1}=E_k(P_{i+1})\$
-
Útok na známý otevřený text (Known-plaintext attack)
Kryptoanalytik má přístup nejenom k šifrovaným textům několika zpráv, ale také k otevřenému textu těchto zpráv. Jeho práce je vydedukovat šifrovací klíč (nebo klíče), použité k zašifrování zpráv. Nebo nalézt algoritmus, umožňující rozšifrování zpráv zašifrovaných tímto klíčem (klíči).
Je dáno: \$P_1, C_1 = E_k(P_1), P_2, C_2=E_k(P_2), ... P_i, C_i=E_k(P_i)\$
Je třeba najít: buď klíč \$k\$, nebo algoritmus, který odvozuje \$P_{i+1}\$ z \$C_{i+1}=E_k(P_{i+1})\$
-
Útok na vybraný otevřený text (Chosen-plaintext attack)
Kryptoanalytik nejenom že má přístup k šifrovanému textu a odpovídajícímu otevřenému textu u několika zpráv, ale může si zvolit otevřený text, který bude zašifrován. To je účinnější, žež útok na známý otevřený text, , protože kryproanalytik může zvolit specifický otevřený text k zašifrování, čímž může získat více informací o klíči. Jeho práce je vydedukovat klíč (nebo klíče) použité k zašifrování zprávy nebo algoritmus k rozšifrování libovolné další zprávy, zašifrované tím samým klíčem (nebo klíči).
Je dáno: \$P_1, C_1=E_k(P_1), P_2, C_2=E_k(P_2),...P_i, C_i=E_k(P_i)\$, kde si kryptoanalytik může zvolit \$P_1,P_2,...P_i\$
Je třeba najít: Buďto klíč \$k\$, nebo algoritmus, k odvození \$P_{i+1}\$ z \$C_{i+1}=E_k(P_{i+1})\$.
-
Adaptivní útok na vybraný otevřený text (Adaptive-chosen-plaintext attack)
Toto je speciální případ předchozího útoku na vybraný otevřený text. Nejenom, že kryptoanalytik může zvolit otevřený text k zašifrování, ale může i měnit svoji volbu v závislost na předchozím zašifrování. V předchozím útoku na otevřený text může kryptoanalytik zvolit jeden velký blok otevřeného textu k zašifrování, v adaptivním útoku může volit menší bloky otevřeného textu a potom volit další v závislosti na výsledku předchozího útok atd.
-
Útok na vybraný šifrovaný text (Chosen-ciphertext attack)
Kryptoanalytik může volit různé šifrované texty k rozšifrování a má přístup k rozšifrovanému původnímu otevřenému textu. Například, kryptoanalytik má přístup k nepoškozené krabičce, která provádí automatické rozšifrování. Jeho práce spočívá v tom, najít šifrovací klíč.
Je dáno: \$C_1,P_1=D_k(C_1), C_2,P_2=D_k(C_2),... C_i,P_i=D_k(C_i)\$
Je třeba najít klíč \$k\$.
Tento typ útoku se používá hlavně proti algoritmům s veřejným klíčem, ale je někdy efektivní i proti algoritmům symetrickým.
Někdy se "útok na vybraný otevřený text" a "útok na vybraný šifrovaný text" společně označují jako útok na vybraný text (choosen-text attack).
-
Útok na vybraný klíč (Choosen-key attack)
Tento útok neznamená, že by si kryptoanalytik mohl zvolit klíč, znamená spíše to, že má nějaké znalosti o tom, v jaké závislosti jsou různé klíče. Je to zvláštní až obskurní a není to velmi použitelné.
-
Kryptoanalýza gumovou hadicí (Rubber-hose cryptanalysis)
Kryptoanalytik vyhrožuje, vydírá nebo mučí někoho, dokud mu nedá klíč. Podplácení se někdy označuje jako útok odkoupením (purchase-key attack). Toto jsou velmi mocné způsoby útoku a je to často nejlepší cesta, jak zlomit algoritmus.
Bylo by dobré se zmínit i o útoku hrubou silou (brute-force attack), kde máme-li dostatečný výpočetní výkon a program k tomu, abychom vyzkoušeli všechny použitelné klíče z klíčového prostoru, dostaneme klíč a tím pádem i otevřený text prostým vyzkoušením všech klíčů po sobě. Útok hrubou silou je de facto útokem na šifrovaný text. Zmíníme se o něm i později.
U Caesarovy šifry je vidět, že klíčový prostor je velmi malý (pro 26 písmen obsahuje klíčový prostor 25 klíčů) a proto bude útok hrubou silou velmi rychlý i bez nějaké výpočetní techniky. Je proto velmi důležité, aby klíčový prostor (množina všech možných klíčů) daného kryptosystému byl hodně, ale hodně velký.
Bezpečnost algoritmu
Různé algoritmy poskytují různou úroveň bezpečnosti, závisí to na tom, jak těžké je zlomit. Jestliže náklady na zlomení algoritmu jsou vyšší než hodnota zašifrovaných dat, potom jste pravděpodobně v bezpečí. Jestliže je čas potřebný ke zlomení algoritmu větší než čas, po který je nutné udržet informaci v utajení, potom jste opět pravděpodobně v bezpečí. Je-li množství dat zašifrované jedním klíčem menší než množství dat potřebných pro zlomení algoritmu, potom jste pravděpodobně v bezpečí.
Říkáme "pravděpodobně", protože vždy existuje šance, že se podaří nějaký průlom v kryptoanalýze. Na druhou stranu hodnota převážného množství zašifrovaných dat časem klesá. Je důležité, aby hodnota zašifrovaných dat zůstávala stále menší, než náklady na prolomení bezpečnosti, které ji chrání.
Právě ve dnech, kdy píši tento článek, vyšel na známém serveru ROOT článek o tom, že "Čínští vědci tvrdí, že umí prolomit RSA šifru novým algoritmem pro kvantový počítač" https://www.root.cz/zpravicky/cinsti-vedci-tvrdi-ze-umi-prolomit-rsa-sifru-novym-algoritmem-pro-kvatovy-pocitac/
Lars Knudsen roztřídil jednotlivá prolomení algoritmů do těchto kategorii:
-
Kompletní prolomení (Total break)
Kryptoanalytik najde klíč k, takže \$D_k(C)=P\$.
-
Global deduction
Kryptoanalytik najde alternativní algoritmus A, který je ekvivalentní k \$D_k(C)\$, bez toho, že by znal klíč k.
-
Instance (or local) deduction
Kryptoanalytik najde otevřený text ze zachyceného šifrovaného textu.
-
Informational deduction
Kryptoanalytik získá nějakou informaci o klíči nebo o otevřeném textu. Tato informace může být několik bitů klíče, nějaká informace ve formě otevřeného textu apod.
Algoritmus je nepodmíněně bezpečný (unconditionally secure), jestliže nijak nezávisí na tom, kolik šifrovaného textu má kryptoanalytik k dispozici, a přesto nemá dostatek informací k tomu, aby odvodil (rozluštil) otevřený text. Ve skutečnosti jenom jednorázová tabulková šifra (one-time pad) je nezlomitelná při nekonečných zdrojích. Všechny ostatní kryptosystémy jsou zlomitelné pomocí útoku na šifrovaný text jednoduše tak, že se vyzkouší všechny možné klíče jeden po druhém a zkoumá se, zda je otevřený text smysluplný. Tomu se říká útok hrubou silou (brute-force attack).
Kryptografie se více zabývá kryptosystémy u kterých je neproveditelné zlomení pomocí výpočetní techniky. Algoritmus se považuje za výpočetně bezpečný (nazývá se též silný), pokud nemůže být zlomen ať současnými tak i budoucími dostupnými výpočetními prostředky. Co to jsou dostupné výpočetní prostředky není definováno nijak přesně a je možné o tom diskutovat.
Můžeme měřit složitost útoku různými způsoby:
-
Datová složitost - Množství dat, které jsou potřebné k útoku.
-
Výpočetní složitost - Množství času potřebné k útoku.
-
Požadavek na úložný prostor - Množství paměti (operační nebo nonvolatilní) k provedení útoku.
Za pravidlo se považuje: složitost útoku se bere jako minimum těchto tří faktorů. Některé útoky zahrnují výměnu tří složitostí. Rychlejší útok by mohl být možný na úkor větších požadavků na úložiště.
Složitosti jsou vyjádřeny v řádech. Má-li algoritmus výpočetní složitost \$2^128\$, potom je potřeba \$2^128\$ operací na jeho prolomení. Tyto operace mohou být komplexní a časově náročné. Avšak platí, jestliže předpokládáme, že máme dostatek výpočetní rychlosti, abychom provedli jeden milion operací za sekundu a postavíme milion výpočetních systémů paralelně vedle sebe k provedení úkolu, tak stejně potřebujeme \$10^19\$ let, abychom získali klíč. To je však \$10^9\$ krát více, než je odhadované stáří vesmíru.
Zatímco složitost útoku zůstává konstatní (pokud kryptoanalytici neudělají zásadní průlom), tak u výpočetního výkonu tomu tak není. Viděli jsem fenomenální nárůst výpočetního výkonu za poslední půlstoletí a není důvod předpokládat, že tento trend nebude pokračovat. Avšak v posledních letech se trend nárůstu výpočetní rychlosti zpomalil a při výrobě křemíkových procesorů výrobci narážejí na fyzikální limity. Např. technologický proces výroby čipů 5nm litografií umí zatím jenom jedna firma na světě, taiwanská TSMC. Mnoho kryptoanalytických útoků může být bezvadně paralelizováno. Mohou být rozkouskovány na miliardu malých úkolů a žádný z procesorů nemusí komunikovat s jiným.
Takže, pokud považujeme jednoduše algoritmus za bezpečný jenom proto, že jeho zlomení pomocí současné technologie je nemožné, je poněkud chybný názor. Dobré kryptosystémy jsou navrhovány tak, aby vydržely útok výpočetního výkonu, který je očekáván za mnoho let.
Steganografie
Steganografie slouží ke skrytí tajné zprávy v jiné zprávě tak, že existence tajné zprávy uvnitř jiné zprávy není patrná.
Nerozluštitelná š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á neboli nepodmínečně bezpečná.
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í.
Poznámka: doc. Martin Plesh, PhD. z Fakulty matematiky, fyziky a informatiky Univerzity Komenského v Bratislave ukazuje, že pomocí více pseudonáhodných generátorů lze dosáhnout dokonalé náhody. Takže dokonale náhodný klíč lze získat. https://www.youtube.com/watch?v=rjXsR2n_CQY
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.
Domácí úkol č.5
-
Vernamova šifra představuje symetrický algoritmus nebo algoritmus s veřejným klíčem?
-
Napište předpis pro šifrovací a dešifrovací funkci pro Vernamovu šifru.
-
Dokažte pomocí pravdivostní tabulky, že \$(A \oplus X) \oplus (B \oplus X) = A \oplus B\$
| A | B | \$A \oplus B\$ |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Domácí úkol 2
Zde je primitivní implementace Vernamovy šifry v Pythonu:
# Vernamova šifra, primitivní implementace v Pythonu
# (c) Jirka Chráska, jirka@lixis.cz
# Testováno v Python 3 na Linuxu.
# Flag==True - zašifrování, encryption; Flag==False - rozšifrování, decryption
def Vernam(Plain, Key, Flag):
result = ""
for i in range(len(Plain)):
char = Plain[i]
if(Flag):
result += chr((ord(char)-97 + ord(Key[i])-97)%26 + 97)
else:
result += chr((ord(char) - ord(Key[i])+26)%26 + 97)
return result
if __name__== "__main__":
print("Při zadávání klíče a plaintextu nepoužívejte mezery, háčky a čárky. Klíč musí být minimálně stejně dlouhý jako plaintext. Plaintext bude převeden na malá písmena.")
Key = ''.join(input("Zadejte klíč: ").lower().split()) // (1)
Plain = ''.join(input("Zadejte plaintext: ").lower().split()) // (2)
if( len(Key) <= len(Plain)): // (3)
print("Klíč je menší než plaintext! Konec.")
exit(None)
# zašifrujeme
CipherText = ''.join(Vernam(Plain, Key, True)) // (4)
print("Šifrovaný text: ", CipherText)
# rozšifrujeme
print("Dešifrovaný plaintext: ", Vernam(CipherText, Key, False)) // (5)
# Při zadávání klíče a plaintextu nepoužívejte mezery. Plaintext bude převeden na malá písmena.
# Zadejte klíč: aspodipoieríljlwekrjwlekwlkmah
# Zadejte plaintext: TohleJeTextCoChcemeZasifrovatX
# Šifrovaný text: tgwzhrthmbkmzlsyiwviwdmpnzfmte
# Dešifrovaný plaintext: tohlejetextcochcemezasifrovatx-
Zadáváme klíč tak, že náhodně píšeme písmenka na klávesnici.
-
Zadáváme plaintext, který by měl být maximálně stejně dlouhý jako klíč.
-
Testujeme délku klíče, musí být minimálně stejně dlouhý jako plaintext.
-
Zašifrujeme
-
Rozšifrujeme a vytiskneme
Zkuste implementaci vylepšit, tak, aby fungovala i s háčky a čárkami, mezerami a interpukčními znaménkami. Prostě s UTF-8 znaky. Python není můj hlavní programovací jazyk, proto ho moc neumím. Nejraději mám Perl a C. Zkuste najít zásadní chyby v implementaci.
Zdrojový kód: vernam_2.py
Odkazy a literatura:
Bruce Schneier: Applied Cryptography 2nd edition, John Wiley & Sons Inc. 1996
Niels Ferguson, Bruce Schneier, Tadayoshi Kohno: Cryptography Engineering Design Principles and Practical Applications, Wiley Publishing, Inc.