Substituční šifra: definice, princip a prolomení frekvenční analýzou

Objevte substituční šifru: definice, principy, příklady (Caesarova), její slabiny a postup prolomení pomocí frekvenční analýzy — praktický průvodce pro začátečníky i nadšence.

Substituční šifra je druh kryptografie, ve kterém se každé písmeno otevřeného textu nahrazuje jiným znakem podle předem daného pravidla (tzv. klíče). Pokud je pravidlo stále stejné pro všechna písmena zprávy, jde o monoalfabetickou (jednoalfabetovou) substituci; pokud se pravidlo mění v průběhu zprávy, jde o polyalfabetickou substituci.

V substituční šifře se používá pravidlo, které postupně mění jednotlivá písmena zprávy. Pravidlo říká, že se každé písmeno nahradí (neboli "substituuje") jiným písmenem z abecedy. Důležité je, že jednoduchá (jednoalfabetová) substituce zachovává délky slov a pozice mezer i interpunkce, takže struktura textu zůstává rozpoznatelná.

V této tabulce je například uvedeno pravidlo pro substituční šifru:

• Příklad jednoduché substituce – Caesarova šifra (posun o 3):
• a → d, b → e, c → f, d → g, e → h, f → i, g → j, h → k, i → l, j → m, k → n, l → o, m → p, n → q, o → r, p → s, q → t, r → u, s → v, t → w, u → x, v → y, w → z, x → a, y → b, z → c

Podle tohoto pravidla se věta "Jack a Jill šli na kopec" změní na "Etar tzn Evmm gkzc dw cuk uvmm". Příkladem substituční šifry je Caesarova šifra.

Šifrování a dešifrování

Šifrování probíhá nahrazením každého písmena podle klíče. Dešifrování je opačný proces – pro každé písmeno v šifře najdeme, které písmeno mu v otevřeném textu odpovídalo. U jednodušších monoalfabetických šifer stačí znát nebo uhodnout permutaci abecedy; u polyalfabetických šifer se pro dešifrování používají pravidla, která se mění v čase (např. Vigenèrova šifra).

Zranitelnost a frekvenční analýza

Substituční šifry nejsou pro důležité zprávy dostatečně bezpečné, pokud se používá jen jedno pevné nahrazení. Lze je prolomit pomocí myšlenky zvané frekvenční analýza. Každý jazyk má charakteristické rozložení četností písmen (v češtině např. často vystupují E, A, O, I, N, T a podobně). Monoalfabetická substituce zachovává četnosti znaků – pouze písmena jsou přejmenována – takže nejběžnější písmena v šifrovaném textu odpovídají nejběžnějším písmenům v daném jazyce.

Pro praktické rozluštění šifry se používají tyto kroky:

• Spočítat četnosti jednotlivých písmen ve šifře (nejčastější, druhé nejčastější apod.).
• Porovnat je s typickými četnostmi písmen v příslušném jazyce a navrhnout prvotní přiřazení (např. nejčastější šifrové písmeno → E).
• Analyzovat krátká slova a jednopísmenná slova (v češtině např. "a", "k", "s", "v", "o"), která často pomohou určit konkrétní písmena.
• Sledovat časté digramy a trigramy (v češtině například "pr", "po", "ne", "ch", "st" apod.) a dvojité znaky (dvě stejné za sebou), což usnadní další odhalování mapování.
• Vyhledávat opakující se vzory slov – opakování slov ve stejném tvaru odhalí opakované šifrové bloky, které lze přiřadit ke stejným otevřeným slovům.
• Používat postupné opravování a testování hypotéz: jakmile se uvolní několik písmen, lze zkusit doplnit slova a ověřit konzistenci řešení.

Rozluštění kryptogramů (zpráv skrytých substituční šifrou) je běžnou hádankou, kterou často najdete v novinách. U krátkých textů je však frekvenční analýza méně spolehlivá, protože náhodné odchylky frekvencí mohou vést k chybným domněnkám.

Pokročilé techniky a obrana

Aby se zvýšila odolnost proti frekvenční analýze, používají se různé modifikace:

• Polyalphabetická substituce (např. Vigenère) – kódování se střídá podle klíče, což rozostří frekvenční stopy.
• Homofonní substituce – jedno písmeno otevřeného textu může být mapováno na více možných symbolů ve šifře, čímž se rovnoměrněji rozloží četnosti.
• Transpozice – místo (nebo spolu se) nahrazením měníme pořadí písmen; kombinace substituce a transpozice zvyšuje bezpečnost.
• Pro skutečně bezpečnou komunikaci se používají moderní šifry a standardy (symetrické algoritmy jako AES, asymetrické jako RSA) a dobře generované klíče.

Automatické metody prolomení

Kromě ruční frekvenční analýzy existují automatické přístupy: algoritmy pro porovnání četností, heuristiky založené na statistikách jazyka, genetické algoritmy, simulované žíhání (simulated annealing) nebo metody strojového učení. Tyto techniky dokáží u dlouhých šifer rychle nalézt správná přiřazení i tam, kde ruční metoda selhává.

Závěr

Substituční šifra jasně ilustruje základní principy šifrování – nahrazení a zachování struktury textu. Jednoalfabetická substituce je však z praktického hlediska slabá, protože statistické vlastnosti jazyka dovolují použitím frekvenční analýzy šifru relativně snadno prolomit. Pro bezpečné použití je nutné volit složitější schémata, kombinovat techniky nebo použít moderní kryptografické protokoly.

Otázky a odpovědi

Otázka: Co je to substituční šifra?

Otázka: Jak substituční šifra funguje?

Otázka: Jaký je příklad tabulky používané v substituční šifře?

Otázka: Co je to Caesarova šifra?

Otázka: Jsou substituční šifry dostatečně bezpečné pro důležité zprávy?

Otázka: Jak lze substituční šifry prolomit?

Otázka: Jaká je běžná hádanka, která zahrnuje prolomení šifry?

Hledání podle dopisu