Vigenèrova šifra

Vigenèrova šifra je symetrická polyalfabetická substituční šifra, která text šifruje pomocí série různých Caesarových šifer v závislosti na písmenech klíče.

Šifra vychází z šifry florentského polyhistora Leona Battisty Albertiho který svou polyalfabetickou šifru zveřejnil kolem roku 1467, ale konečnou podobu ji dal až Giovan Battista Bellaso ve svém díle La cifra del. Sig. Giovan Battista Bellaso z roku 1553. V 19. století byla nesprávně připsána francouzskému diplomatovi Blaisi de Vigenèrovi, který šifru podobného typu zveřejnil až v roce 1586.^[1]

Popis původní Albertiho šifry

Původní Albertiho šifra se lišila od klasických substitučních šifer tím, že používala dvě šifrovací abecedy, čímž bylo dosaženo většího zmatení nepřítele, který by se šifru snažil rozluštit. Tyto abecedy mohly vypadat takto:

Otevřená abeceda:  a b c d e f g h i j k l m n o p q r s t u v w x y z
Šifrová abeceda 1: Q W E R T Z U I O P A S D F G H J K L Y X C V B N M
Šifrová abeceda 2: Y A Q X S W C D E V F R B G T N H Z M J U K I L O P

Pokud bychom chtěli zašifrovat slovo „silnice“, postupovali bychom takto: první písmeno, „s“, bychom zašifrovali podle první abecedy: s→L. Druhé písmeno bychom zašifrovali podle druhé abecedy: i→E. Třetí písmeno opět podle první abecedy: l→S. Pak n→G, i→O, c→Q a e→T. Výsledné šifrové slovo by bylo: „LESGOQT“. Už v tomto krátkém slovu můžeme vidět hlavní výhodu Albertiho šifry: jedno písmeno v otevřeném textu se může zašifrovat dvěma způsoby a v zašifrovaném textu tak může být pod dvěma znaky. Písmeno „i“ bylo zašifrováno do písmen „E“ a „O“. Toto poněkud ztěžuje kryptoanalýzu, protože útočník nemůže použít jednoduchou frekvenční analýzu.

Popis Vigenèrovy šifry

Vigenèrova šifra je rozšíření původní Albertiho šifry, která používala pouze dvě šifrové abecedy. Vigenèrova šifra umožňuje použít až 26 šifrových abeced, čímž drasticky snižuje pravděpodobnost prolomení šifry. Tato šifra se ve své době označovala jako Le chiffre indèchiffrable, tedy nerozluštitelná šifra. Základem šifrování se stal Vigenèrův čtverec, což byla šifrovací pomůcka, na které bylo znázorněno oněch 26 šifrových abeced, které jsme mohli použít. Ve čtverci byla na prvním řádku vepsaná otevřená abeceda, což byla normální abeceda a, b, c, d, … Na dalších řádcích pak byla vepsána šifrová abeceda, která vznikla posunem předchozí abecedy o jedna (jakoby Caesarova šifra s klíčem „b“). V levém sloupečku pak byl klíč posunutí vzhledem k první, otevřené abecedě. Přehledně to zobrazuje obrázek napravo. Každé písmeno z otevřené abecedy můžeme zašifrovat kteroukoliv z 26 šifrových abeced, což znamená, že jakýkoliv znak z otevřeného textu jsme schopni zašifrovat na libovolný znak. To opět snižuje riziko prolomení šifry.

Postup při šifrování už je pak jednoduchý. Zvolíme si klíč, což může být slovo libovolné délky. Při použití slova délky jedna se ale bude jednat o klasickou Caesarovu šifru, při použití klíče délky dva dostaneme obdobu Albertiho šifry. Obecně můžeme říci, že čím delší klíč, tím bezpečnější šifra bude. Samozřejmě nesmíme jako klíč volit jiné slabé klíče, jako například „aaaaa“. Samotné šifrování probíhá následovně: vezmeme první písmeno z otevřeného textu a zašifrujeme ho pomocí té šifrové abecedy z Vigenèrova čtverce, která odpovídá prvnímu znaku z klíče. Poté vezmeme druhé písmeno z otevřeného textu a zašifrujeme ho pomocí šifrové abecedy, která odpovídá druhému znaku z klíče. Až vyčerpáme všechny znaky v klíči, začneme opět od začátku klíče. Ukázka:

Chceme zašifrovat text „wikipedie“ a jako klíč si zvolíme slovo „bagr“. Šifrové abecedy budeme volit takto:

wikipedie
bagrbagrb

Dle Vigenèrova čtverce: písmeno „w“ má v šifrové abecedě „b“ obraz „X“. Písmeno „i“ má v šifrové abecedě „a“ obraz „I“. Písmeno „k“ má v šifrové abecedě „g“ obraz „Q“. A tak dále. Na konec dostaneme: „XIQZQEJZF“. Vidíme, že písmeno „i“ v otevřeném textu bylo zašifrováno dvěma různými způsoby na „I“ a „Z“ a naopak: v šifrovém textu se vyskytují dvě písmena „Q“, která v originále znamenají „k“ a „p“.

Dešifrování probíhá opačným postupem.

Výhody Vigenèrovy šifry

Vigenèrova šifra disponuje velkým množstvím klíčů, je tudíž odolná vůči útokům hrubou silou. Například pokud bychom pracovali s klíči o délce 13, existovalo by celkem 26¹³ možných klíčů, což je zhruba 10¹⁸ klíčů. Pokud by stroj prověřil miliardu klíčů za sekundu, prověřit všechny klíče délky 13 by mu trvalo přes 78 let.
Šifra je odolná proti běžné frekvenční analýze. Pokud máme v klíči n různých písmen, pak libovolné písmeno v otevřeném textu může být zašifrované až do n různých písmen. Informace o četnosti jednotlivých písmen je nám tak k ničemu.
Klíč může být snadno zapamatovatelný. Protože klíčem může být jakékoliv slovo nebo klidně celá věta či věty, účastníci šifrování si nemusí složitě poznamenávat a zapisovat klíče, ale mohou si je jednoduše zapamatovat.

Slabiny Vigenèrovy šifry

Na svou dobu byla příliš složitá. V době, kdy byla šifra vymyšlena, se používaly substituční šifry, které byly daleko jednodušší na používání. Proto se spíše používaly některé vylepšené substituční šifry (například homofonní šifra), než aby se přešlo k bezpečnější Vigenèrově šifře. Vigenèrova šifra se tak začala používat až o dvě století později, v 18. století.
Opakování klíče: pokud jsme zvolili klíč kratší než zpráva, což bylo vcelku běžné, protože nebylo reálné používat klíče, které by byly stejně dlouhé jako zpráva samotná, docházelo k tomu, že různé části zprávy byly zašifrovány stejným klíčem. Pokud jsme v otevřeném textu měli slovo „ale“ a šifrový klíč měl délku 5, existuje celkem 5 možných způsobů, jakým mohlo být slovo „ale“ zašifrováno. Jakýkoliv další výskyt slova „ale“ se už zašifroval stejně jako jeden z jeho předchozích výskytů. Pokud tak útočník našel v šifrovém textu shluky stejných písmen, pravděpodobně se jedná o stejná slova v otevřeném textu. Pokud nalezneme dvě taková slova, můžeme pomocí nich zkusit odhadnout délku klíče. Pokud je například vzdálenost mezi slovy 20, může mít klíč délku některého z dělitelů čísla 20. Možné délky tak jsou: 1, 2, 4, 5, 10, 20.
I do Vigenèrovy šifry zčásti zasahují některé vlastnosti jazyka. Jedna z výhod této šifry spočívala v tom, že si její uživatelé mohli zvolit snadno zapamatovatelná hesla, což znamenalo nějaká reálná slova nebo věty. Na tato slova už ovšem můžeme aplikovat frekvenční analýzu. Například můžeme předpokládat, že nejčastější písmeno v klíči je písmeno „e“, což je nejčastější písmeno v češtině. A naopak – není moc pravděpodobné, že nějaké písmeno v textu bude šifrováno pomocí písmen „w“ nebo „q“, která se v češtině téměř nevyskytují.

Těchto slabin využil pruský důstojník Friedrich Wilhelm Kasiski a šifru prolomil, což publikoval roku 1863. Ještě před ním šifru rozluštil v 50. letech 19. století britský matematik a filosof Charles Babbage, svůj postup však nezveřejnil.^[2]

Odkazy

Reference

↑ http://crypto.interactive-maths.com/vigenegravere-cipher.html Vigenère Cipher na Crypto Corner
↑ SALOMON, David. Data Privacy and Security: Encryption and Information Hiding. [s.l.]: Springer, 2003. ISBN 978-0387003115. Kapitola Breaking The Vigenère Cipher, s. 66. (anglicky)

Literatura

KAHN, David. The Codebreakers - The Story of Secret Writing. [s.l.]: Scribner. Revidované vydání, 1996. 1200 s. ISBN 978-0684831305.

SINGH, Simon. Kniha kódů a šifer. [s.l.]: Dokořán, 2009. 384 s. ISBN 978-80-7363-268-7.

Související články

[1] ttp://crypto.interactive-maths.com/vigenegravere-cipher.html Vigenère Cipher na Crypto Corner

[2] SALOMON, David. Data Privacy and Security: Encryption and Information Hiding. [s.l.]: Springer, 2003. ISBN 978-0387003115. Kapitola Breaking The Vigenère Cipher, s. 66. (anglicky)

[1]

[2]