Monoalfabetická šifra

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Na začátku si musíme 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 můžeme 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 nám kolize a při dešifrování bychom nevěděli, 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, nemůžeme 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 písmena nemusíme šifrovat zase jen na písmena, ale na cokoliv jiného, například obrázky, čísla nebo jakékoliv jiné symboly. Pokud ale chceme získat monoalfabetickou šifru, musí tato tabulka splňovat podmínku bijekce. Použitím jiných znaků zpravidla nezvýšíme bezpečnost šifry, protože jestli vypadá výsledný šifrový text „hqp“ nebo „(hvězdička)(sluníčko)(jednorožec)“ už je z hlediska kryptoanalýzy jedno.

Pokud už máme hotovou tabulku 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ě. Nicméně technicky není problém vytvořit substituční tabulku, která bude obsahovat jakékoliv znaky. Můžeme klidně zašifrovat „(pomeranč)“ na „(koloběžka)“.

Nakonec šifrujeme otevřenou zprávu znak po znaku – přečteme znak, nalezneme znak v tabulce, kde najdeme i odpovídající obraz písmene, a zaměníme 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 používáme tabulku substitucí obráceně. Pokud v ní například bylo pravidlo „a“→„q“, budeme ve skutečnosti zaměňovat „q“→„a“. Takto získáme původní upravený otevřený text. Abychom dostali původní otevřený text bez úprav – pokud jsme nějaké provedli – musíme ještě doplnit mezery, diakritiku apod.

Příklad šifrování[editovat | editovat zdroj]

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íč[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 řekli 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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