Jak prolomit Caesarovu šifru pomocí vzdáleností písmen
Kapitoly: Caesarova šifra, Jak prolomit Caesarovu šifru hrubou silou, Jak prolomit Caesarovu šifru pomocí vzdáleností písmen
Útok pomocí minimální vzdáleností písmen
Caearova šifra má jednu zajímavou vlastnost vyplývající z její definice. Protože pouze posouvá písmena, vždy o stejnou vzdálenost, tak vzdálenosti písmen v otevřeném textu a šifrovém textu zůstávají stejné.
Například pokud by otevřený text byl „abe“ a my bychom ho zašifrovali s klíčem „g“, získali bychom šifrový text „ghk“. Přitom vzdálenost mezi písmeny „a“, „b“, označíme |a, b|, je rovna jedné: |a,b| = 1 a pro písmena v šifrovém textu platí |g, h| = 1. Podobně pro dvojici |b,e| = 3 a |h,k| = 3 a nakonec pro dvojici |a,e| = 4 a |g,k| = 4.
Jediný problém nastává, pokud jdeme přes poslední písmeno, přes „z“. Pak to totiž nesedí. Pokud bychom zašifrovali „xz“ s klíčem „c“, tak bychom získali šifrový text „zb“. Přitom |x,z| = 2, ale |z,b| = 24.
Aby to sedělo, musíme vždy počítat kratší z cest. Tzn., že z „b“ se můžeme do „z“ dostat buď směrem „bcd…xyz“, to by nám vrátilo vzdálenost 24, anebo opačným směrem „baz“, což by nám vrátilo vzdálenost 2 — to je správná vzdálenost. Vždy tak budeme brát tu kratší z obou vzdáleností. Tuto vzdálenost nazveme minimální vzdálenost písmen.
Idea útoku
V tabulkách najdeme tři nejčastěji používaná písmena v českém textu. To jsou „e, a, o“. Nyní v šifrovém textu najdeme šest nejčastějších písmen. (Proč zrovna šest a proč zrovna tři? Je to celkem jedno, ale tahle kombinace dává docela dobré výsledky.) V těch šesti nejčastějších písmenech nyní nalezneme takovou trojici písmen, která má mezi sebou stejné minimální vzdálenosti, jako má trojice písmen „e, a, o“. Pokud takovou trojici nalezneme, pravděpopdobně jsme nalezli trojici písmen, na kterou se zašifrovala trojice písmen „e, a, o“. Z této informace už můžeme snadno odvodit šifrový klíč.
Opět je připraven nástroj, který tento algoritmus provádí. Do textového pole vložte Caesarovou šifrou zašifrovaný text a nástroj se pokusí text prolomit a dešifrovat.