Monoalfabetická šifra

Monoalfabetická šifra je nejjednodušší druh substituční šifry, kdy se písmena v otevřeném textu pouze zamění za jiná písmena, dle daného klíče, čímž vznikne šifrový text.

Popis šifry

Na začátku je třeba vytvořit tabulku substitucí, což je tabulka, která znázorňuje, které písmeno v otevřeném textu se mění na jaké v šifrovém textu. Tabulku lze vytvořit libovolným způsobem, ale platí, že zobrazení musí být bijektivní, tedy každé písmeno z otevřeného textu musí mít jedinečný obraz v šifrovém textu. Pokud by se například písmeno „a“ zobrazilo na písmeno „q“ a písmeno „b“ by se také zobrazilo na písmeno „q“, vznikla by kolize a při dešifrování by nebylo zřejmé, zda písmeno „q“ dešifrovat na „a“ nebo na „b“. A naopak: písmeno v otevřeném textu musí mít pouze jeden obraz, nelze písmeno „a“ jednou zašifrovat na „b“ a jindy na „c“. Pak už to nebyla jednoduchá monoalfabetická šifra, ale homofonní šifra nebo některá z polyalfabetických šifer, které při šifrování používají více abeced, například Vigenèrova šifra.

Dále platí, že se písmena nemusí šifrovat zase jen na písmena, ale na cokoliv jiného, například obrázky, čísla nebo jakékoliv jiné symboly. Pokud je ale třeba získat monoalfabetickou šifru, musí tato tabulka splňovat podmínku bijekce. Použitím jiných znaků zpravidla se nezvýší bezpečnost šifry, protože pokud vypadá výsledný šifrový text „hqp“ nebo „(hvězdička)(sluníčko)(jednorožec)“ už je z hlediska kryptoanalýzy jedno.

Po vytvoření tabulky substitucí, přichází na řadu úprava vstupního otevřeného textu tak, aby vyhovoval domluveným či stanoveným podmínkám. Ty mohou znít jakkoliv, často padá požadavek na odstranění diakritiky, interpunkce, mezer a podobně. Technicky není problém vytvořit substituční tabulku, která bude obsahovat jakékoliv znaky. Stejným počtem rozličných písmen lze zašifrovat „(jablko)“ na „(hruška)“.

Nakonec se šifruje otevřená zpráva znak po znaku – přečte se znak, nalezne se znak v tabulce, kde se nachází i odpovídající obraz písmene, a zamění se původní znak za nový (ten z tabulky substitucí). Záměnou posledního znaku šifrování končí.

Dešifrování probíhá stejným způsobem, pouze se používá tabulka substitucí obráceně. Pokud v ní například bylo pravidlo „a“→„q“, musí se ve skutečnosti zaměňovat „q“→„a“. Takto uživatel získá původní upravený otevřený text. Pokud je třeba dostat původní otevřený text bez úprav – pokud byly nějaké provedeny – je nutno ještě doplnit mezery, diakritiku apod.

Příklad šifrování

Zašifrujme text „Tichá voda břehy mele“. Na začátku vytvoříme tabulku substitucí. Můžeme ji vytvořit jakkoliv, tak dejme tomu, že vypadá takto:

abcdefghijklmnopqrstuvwxyz
KSVHPLIJQGXCZADYBEWRTMFONU

V prvním řádku máme písmena otevřeného abecedy a na řádku druhém písmena šifrové abecedy. Nyní upravíme vstupní text. Vidíme, že v tabulce se vyskytují jen písmena anglické abecedy, takže odstraníme z textu vše nadbytečné. Mezery můžeme ponechat (a šifrovat je zase jako mezery), ale pouze by to snížilo bezpečnost šifry. Upravený text vypadá takto: „tichavodabrehymele“. Teď začneme šifrovat. Z tabulky vidíme, že pod písmenem „t“ se nachází písmeno „R“, takže ho tak zašifrujme. Dále „i“ zašifrujeme na „Q“, „c“ na „V“ apod. Výsledkem bude zašifrovaný text: „RQVJKMDHKSEPJNZPCP“.

Šifrový klíč

V šifře můžeme použití velké množství klíčů. Pokud bychom brali pouze anglickou abecedu, existuje celkem 26! možných klíčů (počet všech permutací písmen v abecedě). To je zhruba 1026 klíčů.

Šifra standardně nepoužívá dobře zapamatovatelné klíče. V předchozím případě jsme použili klíč „KSVHPLIJQGXCZADYBEWRTMFONU“, což je něco, co si lze těžko jednoduše zapamatovat. Proto byl vymyšlen systém, který zjednodušil distribucí klíčů. Uživatel si zvolil svůj libovolný klíč, což mohlo být jakékoliv slovo či jakákoliv věta. Při šifrování se pak klíč použil při vytvoření šifrové abecedy. Pokud by klíčem bylo slovo „lokomotiva“, postupovalo by se takto: odstranila by se všechna písmena, která tam jsou vícekrát tak, aby ve slově zůstal pouze první výskyt písmene. V našem případě bychom odstranili dvě „o“: lokmtiva. Toto slova bychom napsali na začátek šifrové abecedy a doplnili bychom abecedu chybějícími písmeny z abecedy. Tedy na začátku máme LOKMTIVA. Písmeno „A“ už v šifrové abecedě je, takže jdeme dále. Písmeno „B“ tam není, dopíšeme. Písmeno „C“ tam není, dopíšeme. (…) Písmeno „I“ tam už je, přeskočíme. A tak dále, dokud nemáme celou abecedu.

I monoalfabetická šifra má své tzv. slabé klíče. Slabým klíčem je například: „abcdefghijklmnopqrstuvwxyz“, tedy standardní nezměněná abeceda. Pokud bychom se pokusili šifrovat s tímto klíčem, bude šifrový text stejný jako otevřený text. Existuje i mnoho dalších slabých klíčů, kdy se část písmen zobrazí na sebe sama. Klíče, které mají mnoho takových zobrazení, jsou pak slabé klíče a snižují bezpečnost šifry. Slova, která jsou složená z těchto písmen, se totiž zašifrují na sebe sama a případný luštitel je může odhalit pouhým nahlédnutím do šifrového textu.

Bezpečnost šifry

Tato šifra byla velmi oblíbená díky své maximální jednoduchosti. Distribuce klíčů nebyla díky výše popsané metodě problémová a samotné šifrování a dešifrování bylo oproti jiným metodám (například Vigenèrova šifra) také jednoduché. Ale měla své slabiny.

Standardní monoalfabetická šifra je vylepšenou verzí Caesarovy šifry. Caesarova šifra je vlastně pouze speciální případ monoalfabetické šifry, ve které používáme pouze 26 šifrových abeced namísto 26! šifrových abeced. Monoalfabetická šifra je tedy lepší v tom, že má k dispozici velké množství použitelných klíčů. I v dnešní době je téměř nemožné prolomit tuto šifru pouhým zkoušením všech možných klíčů. Pokud by počítač dokázal vyzkoušet miliardu klíčů za sekundu, trvalo by mu přibližně deset miliard let, než by vyzkoušel všechny možné klíče. Pokud bychom měli k dispozici miliardu takových počítačů, trvalo by testování všech klíčů zhruba 12 let.

Monoalfabetická šifra je ale snadno zlomitelná pomocí frekvenční analýzy, což je postup, při kterém se v šifrovém textu hledají vztahy mezi písmeny, které by luštiteli řekly něco o otevřeném textu. Nejjednodušší je spočítat výskyt písmen. Protože víme, že jedno písmeno v otevřeném textu má pouze jeden vzor v šifrovém textu, bude platit, že počet písmen v otevřeném textu bude souhlasit s počtem písmen jeho obrazu v zašifrovaném textu. Víme, že nejčastější písmeno v českém jazyku je „e“. Najdeme-li tak v šifrovém textu nejčastější písmeno, je velká šance, že se jedná právě o písmeno „e“. Vyhledávat můžeme samozřejmě i další vztahy:

  • Bigramy a trigramy. (Bigram jsou dvě písmena jdoucí za sebou. Například „bi“ je bigramem ve slově bigram. Trigram je ekvivalentně posloupnost tří písmen.) Stejně jako má jazyk nejčastější písmena, má i nejčastější bigramy a trigramy.
  • Písmena na začátku a na konci slov, pokud známe mezery a jsme tak schopni určit hranici slov.
  • Můžeme zjistit, jestli se před nebo za daným písmenem vyskytuje spíše hodně různých písmen nebo málo různých písmen. Za samohláskami se typicky vyskytuje hodně různých písmen, za souhláskami se typicky vyskytuje méně různých písmen.

Všechny tyto metody můžeme použít k přibližnému určení, jaká písmena odpovídají kterým písmenům v otevřené abecedě. Nakonec jednoduchým zkoušením a dosazováním můžeme šifru prolomit.

Důležitou věcí je, že opakovaným šifrováním podle jiných abeced nedochází k zesílení šifry. Výsledný šifrový text pouze bude vypadat tak, jako by byl zašifrován jinou abecedou. Pokud bychom zašifrovali „a“→„b“ a následně „b“→„c“, je to stejné, jako bychom zašifrovali rovnou „a“→„c“. Luštitel tak sice neodhalí, že jsme použili více šifrových abeced, ale dešifruje text stejně snadno, jako bychom použili jednu abecedu.

Šifra se nedoporučuje používat prakticky nikde, protože ji je dnes při troše snahy schopen rozluštit i laik.

Vylepšení šifry

Protože tato šifra byla velmi oblíbená, dočkala se několika vylepšení[1]:

  • Nomenklátory, což byly zástupné symboly za některá slova. Alice a Bob se mohli dohodnout, že namísto běžného zašifrování slov „hřbitov“, „náměstí“ a „hospoda“ použijí symbol „(kniha)“, „(deštník)“ a „(opice)“. Zašifrování zprávy „Sejdeme se na hřbitově“ pak mohlo vypadat takto: „FUSTUVUFUBG(kniha)“. I pokud útočník pomocí frekvenční analýzy rozluštil všechny substituce, nomenklátor stejným postupem rozluštit nemohl. Mohl si ale nějak pomoci. Bob například napsal, že se sejdou „na …“, čímž hospoda vypadává ze hry, protože věta „sejdeme se na hospodě“ nedává smysl.
  • Záměrné zkomolení zprávy na základě zvukomalebnosti. To jsou prakticky jakékoliv změny, které sice změní text, ale ten jde stále pochopit. Častými změnami pak jsou různé „gramatycké chibi“ a podobně. Tyto chyby ztíží běžnou frekvenční analýzu, protože hodnoty výskytu písmen neodpovídají obvyklému zastoupení. Stejně tak formulace jako „na hospodě“ v předchozím příkladě mohou být použity záměrně v rámci této kategorie vylepšení.
  • Nuly neboli klamače. Do textu se záměrně vloží několik symbolů, které nemají žádný význam. Bob s Alicí vědí, které symboly to jsou, a tak je při dešifrování zahodí. Případnému luštiteli ale klamače značně zkomplikují kryptoanalýzu, protože při správném použití opět znehodnotí tabulky výskytů písmen a ostatní vztahy mezi písmeny. Při vysokém počtu klamačů se text stává opravdu těžce luštitelný, ale zase může nepřiměřeně narůst velikost zprávy.
  • Písmena z otevřeného textu se zašifrují na více různých písmen. Písmeno „e“ můžeme zašifrovat jednou jako „B“ a jindy jako „C“. Výhodou je, že pokud to budeme dělat vyváženě, budou v zašifrovaném textu namísto jednoho písmene s 10% výskytem dvě písmena, obě s výskytem kolem 5 %. Luštitel tak má ztíženou pozici, protože nemůže tak snadno odhadnout písmeno „e“. Tato šifra se pak nazývá homofonní šifra. Rozložení znaků ještě upravuje tak, aby bylo všech písmen zhruba stejně. Pokud má písmeno „e“ 10% výskyt, bude mít v šifrovém textu 10 různých výskytů apod. Tato šifra už nemůže používat jen standardní abecedu, protože by v šifrovém textu nestačila písmena. Mohou se použít například bigramy, čísla nebo jiné symboly.

Související články

Literatura

  • SINGH, Simon. Kniha kódů a šifer. [s.l.]: Dokořán, 2009. 384 s. ISBN 978-80-7363-268-7. 

Reference

  1. ↑ Vylepšení substitucních šifer (PDF, strana 8)