Substituční šifra

Substituční šifra je v kryptografii druh šifry, při které dochází k záměně (substituci) nějaké množiny symbolů za jinou množinu symbolů. Dle konkrétní šifry to pak mohou být buď písmena, skupiny písmen (bigramy) nebo jiné zástupné symboly jako jsou nomenklátory. Šifra se tím liší od transpozičních šifer, ve kterých dochází k pouhému přeskupení symbolů – v šifrované zprávě se nachází všechny původní symboly, jen jsou napsány v jiném pořadí, takže nejde bez klíče přečíst.

Existuje několik různých typů substitučních šifer. Šifra, která pracuje s jednotlivými znaky, se nazývá jednoduchá substituční šifra. Šifra, která pracuje s většími skupinami písmen se nazývá polygrafická. Monoalfabetická šifra používá fixní substituci pro celou zprávu, zatímco polyalfabetická šifra používá několik substitucí v různých pozicích ve zprávě.

Jednoduchá substituce

ROT13 je Caesarova šifra, typ substituční šifry. V ROT13 je abeceda posunuta o 13 znaků.

Substituce jednotlivých znaků zvlášť — jednoduchá substituce — může být znázorněna vypsáním znaků abecedy v nějakém pořadí, které reprezentuje šifru. Tomu se říká substituční abeceda. Šifrovací abeceda může být posunuta nebo převrácena (čímž vytvoří šifry Caesar, resp. Atbaš). Abeceda může být také promíchána složitěji, čímž vzniká takzvaná smíšená abeceda. Obecně jsou smíšené abecedy vytvářeny tak, že nejprve se vybere klíčové slovo, poté se odstraní opakující se písmena, a nakonec se vypíšou všechny zbývající písmena v abecedě.

Použití tohoto systému s klíčovým slovem "zebras" vytvoří následující abecedy:

Původní abeceda:	ABCDEFGHIJKLMNOPQRSTUVWXYZ
Šifrovací abeceda:	ZEBRASCDFGHIJKLMNOPQTUVWXY

Zpráva

FLEE AT ONCE. WE ARE DISCOVERED!

se zašifruje jako

SIAA ZQ LKBA. VA ZOA RFPBLUAOAR!

Obvykle se zašifrovaný text zapisuje do bloků textu, které mají danou délku, přičemž se zanedbá interpunkce a mezery. To se dělá z toho důvodu, aby se předešlo chybám v přenosu zprávy a zároveň aby nebylo možné z textu odhadnout napsaná slova, jelikož neznáme jejich hranice (mezery). Tyto bloky se nazývají "skupiny", a občas se specifikuje i "počet skupin", který se udává jako další ověření. Skupiny pěti písmen byly nejpoužívanější v dobách, kdy se zprávy přenášely pomocí telegrafu:

SIAAZ QLKBA VAZOA RFPBL UAOAR

Pokud délka zprávy není dělitelná pěti, mohou být na konec přidány nulové znaky. Může se jednat o jakékoliv znaky, které po dešifrování na první pohled vypadají jako nesmysl, takže je příjemce může identifikovat a ignorovat.

Šifrovací abeceda je někdy odlišná od běžné abecedy. Například šifrovací abeceda šifry prasečích chlívků (pigpen cipher) se skládá ze sady symbolů, které vychází z mřížky. Například:

Tyto vlastnosti nemají příliš velký význam na bezpečnost šifry. Je možné vzít libovolnou sadu zvláštně vypadajících symbolů a přiřadit ji písmena A-Z a poté s ní zacházet normálně.

Bezpečnost jednoduchých šifer

Nevýhodou této metody, kdy zvolíme klíčové slovo a posuneme zbytek abecedy, je to, že poslední písmena abecedy (které se příliš nevyskytují) typicky zůstávají i na konci šifrovací abecedy. Silnější způsob, jakým lze vytvořit smíšenou abecedu je použití sloupcové transpozice na běžnou abecedu s použitím klíčového slova. Tato metoda se však obvykle nepoužívá.

I přes to, že počet možných kombinací klíčů je poměrně velký (26! ≈ 2^88.4, nebo 88 bitů), tato šifra není příliš bezpečná a je jednoduché ji prolomit. Pokud je zpráva dostatečně dlouhá (viz níže), kryptoanalýza může vyvodit pravděpodobný význam nejběžnějších znaků. Tím je možné vytvořit částečná slova, do kterých je možné předběžně doplnit znaky, které chybí a tím postupně rozšiřovat částečné řešení. V některých případech lze také zjistit zašifrovaná slova z toho, jak vypadá sekvence znaků, ze kterých se skládají (např. opakování některých znaků).

Klasická kryptografie

V klasické kryptografii se používaly tyto druhy substitučních šifer:

• Monoalfabetická šifra, neboli jednoduchá záměna jednoho písmene za jiné písmeno. Šifra se vyznačuje svou jednoduchostí použití, ale není vůbec bezpečná, protože i laik ji je schopen rozluštit pomocí frekvenční analýzy. Speciálním případem této šifry je Caesarova šifra, ve které pouze posuneme písmena v otevřeném textu o několik pozic dál (například místo „a“ napíšem „c“, místo „b“ napíšeme „d“ apod.). Tato šifra používá pouze jednu šifrovou abecedu.
• Homofonní šifra je vylepšená monoalfabetická šifra, protože umožňuje šifrovat jedno písmeno z otevřené abecedy několika různými způsoby, takže v šifrovém textu může být původní písmeno „a“ zastoupeno několika různými symboly, čímž luštiteli efektivně znemožníme použití jednoduché frekvenční analýzy. Přestože můžeme jedno písmeno zašifrovat na různé symboly, jedná se stále o šifru s jednou šifrovou abecedou. Šifra se hojně používala především díky své jednoduchosti oproti polyalfabetickým šifrám a díky – na svou dobu – dostatečné bezpečnosti.
• Polyalfabetická šifra vylepšuje monoalfabetickou šifru přidáním dalších abeced, podle kterých můžeme šifrovat. Podle nějakého klíče poté vybíráme, podle které konkrétní abecedy budeme zrovna šifrovat. Například v Albertiho šifře se používají dvě šifrovací abecedy, které se pak ob jedno střídají. Touto jednoduchou úpravou zvýšíme bezpečnost šifry, protože stejné znaky z otevřeného textu můžeme zašifrovat různě a stejné znaky z šifrového textu mohou znamenat různá písmena v otevřeném textu. Nicméně nejznámějším zástupcem polyalfabetických šifer je Vigenèrova šifra.
• Polygrafická šifra nepracuje s jednotlivými znaky, ale se skupinami znaků, například s dvojicemi písmen, bigramy. Výhoda spočívá v tom, že můžeme stejná písmena zašifrovat v různých bigramech jinak, takže tím znemožníme jednoduchou kryptoanalýzu. Například můžeme zašifrovat „te“ na „JH“ a „ta“ na „PQ“. Písmeno „t“ je v tomto případě zašifrováno různými způsoby. Stále ovšem zůstává zachována frekvence bigramů samotných.
• Vernamova šifra, což je jediná šifra, která je opravdu nerozluštitelná. Někdy se jí také říkáme jednorázová tabulková šifra. Princip spočívá v tom, že klíč je stejně dlouhý jako zpráva samotná a tím pádem každé písmeno v otevřeném textu šifrujeme pomocí jiného písmene z klíče. Luštitel pak není schopen najít žádné vztahy mezi písmeny, protože tam žádné nejsou. Samozřejmě klíčem musí být zcela náhodný řetězec, pokud tato podmínka není splněna, šifra nebude nerozluštitelná. Přestože je tato šifra stoprocentně bezpečná, téměř se nepoužívá kvůli složité distribuci klíčů – chceme-li někomu poslat 10 GB dat nezabezpečeným kanálem, musíme nejprve poslat 10 GB klíčů zabezpečeným kanálem. Šifru můžeme použít i v bitové kryptografii například použitím funkce XOR.

Moderní šifry

Přestože jsou všechny výše zmíněné šifry (kromě Vernamovy šifry) prolomené (některé šifry lze dnes prolomit s pomocí počítače bez zásahu lidského luštitele), samotný princip substituce se používá i v moderních šifrách. Substituční bloky tak můžeme najít v bitových a blokových šifrách DES nebo AES, kde těmto částem říkáme S-boxy. Stejně tak můžeme substituci nalézt i v hashovacích funkcích. Za druhé světové války se pak používala známá šifra Enigma, což byl zároveň stejnojmenný stroj s klávesnicí, který umožňoval automatické šifrování textu. Enigma obsahovala i substituční bloky.

Substituční šifry v kultuře

Pro svou jednoduchost a názornost bývají často klasické substituční šifry používány v různých filmech a příbězích.

• Edgar Allan Poe ukázal řešení substituční šifry v povídce "Zlatý brouk".
• Sherlock Holmes prolomil substituční šifru v povídce "The Adventure of the Dancing Men".
• Jazyk Al Bhed ve Final Fantasy X je vlastně substituční šifra.
• Uryuomoco, fiktivní jazyk z komiksu El Goonish Shive je substitučně zašifrovaná angličtina.
• Minbariská abeceda ze seriálu Babylon 5 je substitučně zašifrovaná angličtina.
• Jazyk ve videohře Starfox Adventures: Dinosaur Planet, kterým mluví domorodí Sauriani a Krystalové je také zašifrovaná angličtina.

Reference

V tomto článku byl použit překlad textu z článku Substitution cipher na anglické Wikipedii.

Literatura

• Singh, S. Kniha kódů a šifer, Dokořán, 2003