Kryptografie – historické základy (substituce, transpozice, bigram, Vigenerova šifra, absolutně bezpečná šifra, steganografie, kryptoanalýza)

Kryptografie – historické základy (substituce, transpozice, bigram, Vigenerova šifra, absolutně bezpečná šifra, steganografie, kryptoanalýza)

Substituční šifry

Ve starém Říme byly položeny základy druhému hojně používanému principu, tzv. substitučním metodám. Šlo o metodu, která se dnes (patrně právem) říká Caesarova šifra – každé písmeno textu bylo nahrazeno písmenem stojícím v abecedě o 3 místa za ním. Podobná metoda se používala pro šifrování hebrejštiny.

Substituční šifra obecně nahrazuje každý znak zprávy otevřeného textu jiným znakem

podle nějakého pravidla. Aby příjemce získal otevřený text, musí na zašifrovaný text použít inverzní substituci. V klasické kryptografii existují čtyři typy substitučních šifer: 

Monoalfabetická substituční šifra (jednoduchá substituční šifra), ve které se každý znak otevřeného textu nahradí příslušným znakem šifrovaného textu.

Homofonní substituční šifra se podobá jednoduché substituční šifře, avšak jeden znak otevřeného textu může byt nahrazen jedním z několika možných znaků šifrovaného textu. Znak „A“ by mohl být nahrazen např. 5, 10, 13 nebo 25, „B“ např. 6 nebo 15. Po et znaků zašifrovaného textu pro jeden znak otevřeného textu se může lišit.

Polygramová substituční šifra je ta, ve které šifrování probíhá mezi skupinami znaků. Skupina „AA“ může být nahrazená skupinou „JH“, „AB“ skupinou „DK“ atd.

Polyalfabetická substituční šifra sa skládá z několika jednoduchých šifer, které se postupně pro jednotlivé znaky otevřeného textu střídají.

Z řecka (přesněji ze Sparty) pochází i nejstarší známé kryptografické zařízení – skytála. Jde o hůl přesně stanovené šířky, na niž se namotal proužek kůže, na který byla napsána zpráva. Ta mohla být přečtena opět jen na holi stejné šířky. V moderní terminologii se hovoří o tzv. transpoziční metodě.

Transpoziční šifry

Transpozice spočívá ve změně pořadí znaků podle určitého pravidla. Například tak, že otevřený text je zapsán do tabulky po řádcích a šifrový text vznikne čtením sloupců téže tabulky. Transpoziční mřížka. Ve čtverci n×n políček je vystřižených n×n/4 políček tak, aby při

postupném otáčení o 90° stupňů vzniklé otvory vždy ukazovaly na volné místo k vepsání textu.

Tento typ šifry použil Jules Verne ve své knize Matyáš Sandorf (Nový hrabě Monte Christo)

Bigram je jakákoliv dvojice sousedních písmen v nějakém textu. Tak například DO je bigram v českém textu, AT je bigram v anglickém textu.

Vigenerova šifra

Síla Vigenerovy šifry spočívá v tom, že k zašifrování zprávy nepoužívá jednu, ale 26 odlišných šifrových abeced. První šifrovací krok spočívá v tom, že se vytvoří tzv. Vigenerův čtverec, což je otevřená abeceda následovaná 26 šifrovými abecedami, z nichž každá je vůči předchozí posunuta o jedno písmeno. První řádek tedy odpovídá šifrové abecedě s Caesarovým posunem 1. Řádek 2 odpovídá šifrové abecedě s Caesarovým posunem 2 a tak dále. Nejvrchnější řádek čtverce reprezentuje otevřený text. Každé jeho písmeno lze zašifrovat kteroukoliv z 26 šifrových abeced. Pokud například použijeme abecedu 2, pak písmeno A šifrujeme jako C, použijeme-li abecedu 12, šifrujeme ho jako M.

Podstata Vigenerovy šifry však spočívá v tom, že se pro zakódování každého písmene použije jiný řádek čtverce, tedy jiná šifrová abeceda. Jinými slovy, odesílatel může zašifrovat první písmeno zprávy pomocí řádku 5, druhé podle řádku 14, třetí řádkem 21 a tak dále. Aby příjemce získal zpět čitelný text, musí vědět, kterým řádkem Vigenerova čtverce šifroval odesílatel každé písmeno zprávy, musí tedy existovat předem dohodnutý systém, podle něhož se řádky střídají. Toho lze dosáhnout pomocí klíčového slova - klíče.

Jako první krok napíšeme heslo nad text zprávy – opakovaně, tolikrát, kolikrát je třeba, abychom ji pokryli celou. Z otevřeného textu odstraníme mezery. Pak šifrujeme následujícím způsobem: k zašifrování prvního písmene, jímž je d, se nejprve podíváme, jaké písmeno klíče se u něj nachází. Je to W, čímž je dán řádek Vigenerova čtverce, v daném případě řádek 22, jenž začíná právě písmenem W. V průsečíku sloupce označeného d a řádku označeného W najdeme písmeno Z, což je první písmeno písmeno hledaného šifrového textu atd.

Klí ové slovo: W H I T E W H I T E W H I T E W H I T E W H I

Otevřený text: d i v e r t t r o o p s t o e a s t r i d g e

Šifrový text: Z P D X V P A Z H S L Z B H I W Z B K M Z N M

Vrcholem Vigenerovy práce byl jeho Traicté des chiffres (Traktát o šifrách), publikovaný roku 1586. Ironií osudu jej vydal téhož roku, kdy Thomas Phelippes prolomil šifru Marie Stuartovny.

Vzhledem k tomu, o jak silný šifrovací prostředek šlo, zdálo by se přirozené, že se rychle rozšíří do šifrovací praxe po celé Evropě. Stal se však opak: Vigenerova šifra se neujala. Tento zjevně dokonalý systém byl opomíjen po celá dvě následující století.

Absolutně bezpečná šifra

(Vermanova šifra)

V roce 1917 si Gilbert Verman dal patentovat vylepšení dřívějších způsobů š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 šifrovaný 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 krajně obtížné, i když útočník ví, o jakou šifru jde. Aby byla Vermanova šifra spolehlivá, je nutno dodržet tři požadavky:

Klíč je stejně dlouhý jako přenášená zpráva. (Ve starších šifrách to bylo jinak.)

Klíč je dokonale náhodný. (Generátory pseudonáhodných čísel nepřipadají v úvahu, nejlepší je užití fyzikálních metod.)

Klíč nelze použít opakovaně. (Žádné dvě zprávy nesmí být šifrovány stejným klíčem.)

Popsané zacházení s klíčem je ale 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. Stojíme tak před problémem slepice a vejce: 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ě.

Steganografie

Steganografie (z řečtiny: steganós-schovaný, gráphein-psát) je věda zabývající se

utajením komunikace prostřednictvím ukrytí zprávy. Jedná se tedy o metody ukrývání

zprávy jako takové. asto může být kombinována s kryptografií. Do této skupiny patří

různé metody maskování jinak viditelné informace. V moderní době lze tajné texty ukrývat

například do souborů s hudbou i obrázků namísto náhodného šumu.

Na počátku používání metod pro utajení zpráv se objevují jednak primitivní kryptografické algoritmy, jednak zajímavé steganografické postupy. Často citován je např. Herodotos, který ve svých Dějinách zaznamenal patrně nejstarší využití steganografie. Odesílatel zprávy Histiaeus napsal text na oholenou hlavu svého otroka, který s ní, samozřejmě již opět vlasatý dorazil do Milétu, kde přispěl k povstání proti Peršanům. Dalšími steganografickými metodami, které se postupem času objevovaly, jsou tajný inkoust či nějakým způsobem vyznačená písmena v běžném textu (propíchnutím, sklonem, pořadím ve slově aj.). Dnes se zřejmě steganografie používá jen doplňkově, mezi často zmiňované možnosti patří např. ukrytí v grafických souborech, v nevyužívaních bitech apod. Mezi „zajímavé“ možnosti (zřejmě bez valné praktické použitelnosti), objevivší se v souvislosti s rozmachem elektronické komunikace, patří i ukrytí zprávy ve spamech.

Kryptoanalýza

Kryptoanalýza se snaží bez znalosti klíče dojít k utajovaným datům (metody zahrnují: čistě vědecké přístupy, hrubou strojovou sílu, hrubou lidskou sílu – tzv. pendreková kryptoanalýza). Kryptografie a kryptoanalýza spolu tvoří jeden obor nazývaný kryptografie.