Jak spočítat délku klíče Vigenèrovy šifry
Kapitoly: Vigenèrova šifra, Jak prolomit Vigenèrovu šifru se znalostí délky klíče, Odhadnutí délky klíče Vigenèrovy šifry, Jak spočítat délku klíče Vigenèrovy šifry, Friedmanův test — index koincidence
Kasiského test
Existuje postup, z jehož pomocí lze opravdu alespoň přibližně odhadnout délku použitého klíče, případně snížit počet možných klíčů na nějakou rozumně malou množinu. Tuto slabinu objevili nezávisle na sobě dva lidé: Charles Babbage a Friedrich Kasiski. Prvním byl sice Babbage, ale prvním publikujícím byl Kasiski, takže se metoda jmenuje po něm — Kasiského metoda nebo Kasiského test.
Hlavní předností Vigenèrovy šifry je, že pokud se v otevřeném textu vyskytují dvě stejná slova, tak se zašifrují s různými klíči. Většinou. Někdy také ne a toho právě tento algoritmus využívá.
Představme si, že chceme zašifrovat text „Dnes půjdu do kina nebo do divadla. Pojedu tam buď autem nebo šalinou.“ Použijeme klíč „sifra“. Výsledným šifrovým textem bude text „vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom“. Mezery jsou v šifrovém textu ponechány záměrně.
Můžeme si všimnout jedné zajímavé věci — v otevřeném textu je dvakrát slovo „nebo“. V ideálním případě by se v šifrovém textu oba výskyty zašifrovali na jiný šifrový text. Jenomže shodou náhod se stalo to, že se oba výskyty slova „nebo“ zašifrovaly na slovo „fmgf“. Jak se to stalo? Podívejme se, jak se aplikoval klíč:
| Dnes půjdu do kina nebo do divadla. Pojedu tam buď autem nebo šalinou. |
| sifr asifr as ifra sifr as ifrasif rasifr asi fra sifra sifr asifras |
Vidíme, že během opakování klíče došlo k zkrátka tomu, že se první „nebo“ šifrovalo částí klíče „sifr“ a druhé „nebo“ úplně stejnou částí klíče. Náhoda je blbec, stane se.
Postup na zjištění délky klíče
Této chyby ale můžeme využít k odhadnutí délky klíče. Předpokládejme nyní, že máme na vstupu pouze šifrový text „vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom“. Zjistíme, že dvě slova „fmgf“ jsou stejná. Odhadneme, že se původně jednalo o stejná slova, která se nešťastně zašifrovala na stejné šifrové slovo.
Nyní si spočítáme vzdálenost mezi těmito slovy. Spočítáme počet písmen od začátku prvního slova „fmgf“ k začátku druhého slova „fmgf“, tj tuto vzdálenost: „vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom“ (mezery nepočítáme). Celkem tam máme 30 písmen. Pokud jsme měli pravdu a obě slova „fmgf“ jsou ve skutečnosti stejná slova, pak bude platit, že klíč má délku rovnou některému z dělitelů čísla 30. Proč? Jeden z dělitelů je například číslo 6. Kdyby měl klíč délku 6, dejme tomu klíč „abcdef“, vypadalo by šifrování otevřeného textu takto:
| Dnes půjdu do kina nebo do divadla. Pojedu tam buď autem nebo šalinou. |
| abcd efabc de fabc defa bc defabcd efabcd efa bcd efabc defa bcdefab |
Vidíme, že opět by se slova šifrovala stejnou částí klíče. Platí, že pokud jsou slova vzdálená o násobek délky klíče, pak se slova budou šifrovat stejnou částí klíče.
V tuto chvíli tak víme, že klíč má pravděpodobně jednu z délek 2, 3, 5, 6, 10, 15, 30. Toto je ještě pořád docela hodně možností — můžeme postup aplikovat dále a můžeme zkusit najít jinou dvojici stejně zašifrovaných slov. Pokud bychom zjistili, že jejich vzdálenost je 15, už by se nám možnosti snížily na 3 a 5 a dále už to bude hračka.
Online nástroj na prolomení Vigenèrovy šifry
Nástroj předvádí předchozí algoritmus. Zkusí najít v šifrovém textu stejné bloky textu. Pokud nějaké takové bloky nalezne, vypočítá z nich pravděpodobné délky klíče a pro všechny délky zkusí daný klíč zjistit. Poté vybere nejlepší klíč. Pokud žádný shodný blok nenajde, tak algoritmus skončí.
Nástroj by samozřejmě šel vylepšit tak, že v případě neúspěchu by zkusil projet zkrátka všechny klíče do nějakého limitu. Algoritmus zkouší jen klíče, jejichž délka je menší nebo rovna stu.
Tento algoritmus si často poradí s dlouhým klíčem v relativně krátkém čase, pokud je text dostatečně dlouhý. Můžete zkusit vložit do nástroje tento text a prolomte ho. Nástroj vám najde klíč o délce 58.