Denis Sasák
Vigenerova šifra
upraviťVigenerova šifra využíva formu polyalfabetickej substitúcie. Je metóda šifrovania abecedného textu pomocou série prepletených Caesarových šifier, na základe písmen kľúčového slova.
V roku 1553 ju prvýkrát opísal Giovan Battista Bellaso. Ľahké je ju pochopiť a implementovať, no odolávala všetkým pokusom o jej prelomenie až do roku 1863, teda o tri storočia neskôr. Mnoho ľudí sa pokúsilo implementovať šifrovacie schémy, ktoré sú v podstate Vigenerove šifry. V roku 1863 Friedrich Kasiski ako prvý zverejnil všeobecnú metódu dešifrovania Vigenerových šifier. V 19. storočí bola schéma nesprávne pripísaná Blaise de Vigenere (1523 – 1596), a tak získala svoje súčasné meno.
História
upraviťÚplne prvý popis polyalfabetickej šifry vytvoril Leon Battista Alberti (1467) a použil kovový šifrovací disk na prepínanie medzi šifrovými abecedami. Neskôr Johannes Trithemius vo svojom diele Polygraphiae vynašiel tabula recta, kritickú zložku Vigenerovej šifry. Šifra Trithemius však poskytovala progresívny, dosť rigidný a predvídateľný systém prepínania medzi šifrovými abecedami. V roku 1586 Blaise de Vigenere publikoval typ polyalfabetickej šifry nazývanej autokey šifra – pretože jej kľúč je založený na pôvodnom otvorenom texte. Vigenerova šifra je opísaná v knihe La cifra del Sig. Staval na tabula recta Trithemia + „protiznak“ (kľúč) na prepínanie šifrových abecied každé písmeno. Alberti a Trithemius používali pevný vzor suplovania, Bellasova schéma znamenala, že vzor suplovania bolo možné ľahko zmeniť jednoducho výberom nového kľúča. Kľúče boli obom stranám vopred známe, alebo boli prenášané „mimo pásma“ spolu so správou.
Charles Lutwidge Dodgson vo svojom diele „The Alphabet Cipher“ nazval Vigenèrovu šifru neprelomiteľnou. Charles Babbage prelomil variant šifry už v roku 1854, ale svoju prácu nepublikoval. Kasiski úplne prelomil šifru a publikoval túto techniku v 19. storočí.
Popis
upraviťVigenerova šifra má niekoľko Caesarových šifier za sebou s rôznymi hodnotami posunu.
Na šifrovanie je možné použiť tabuľku abecedy, ktorá sa nazýva tabula recta, Vigenerov štvorec alebo Vigenerova tabuľka. Má abecedu napísanú 26-krát v rôznych riadkoch, pričom každá abeceda je v porovnaní s predchádzajúcou abecedou cyklicky posunutá doľava. V rôznych bodoch procesu šifrovania používa šifra inú abecedu z jedného z riadkov. Abeceda použitá v každom bode závisí od opakujúceho sa kľúčového slova.
Predpokladajme napríklad, že čistý text, ktorý sa má zašifrovať, je:
utok na usvit.
Osoba odosielajúca správu si vyberie kľúčové slovo a opakuje ho, kým sa nezhoduje s dĺžkou otvoreného textu, napríklad kľúčové slovo „DVERE“:
DVEREDVEREDV
Každý riadok začína kľúčovým písmenom. Zvyšok riadku obsahuje písmená A až Z (v posunutom poradí). Kód bude používať iba toľko kľúčov, koľko je jedinečných písmen v reťazci kľúčov, tu iba 5 kľúčov: {D, V, E, R, E}. Pre po sebe nasledujúce písmená správy sa zoberú po sebe nasledujúce písmená kľúčového reťazca a každé písmeno správy sa zašifruje pomocou zodpovedajúceho kľúčového radu. Vyberie sa ďalšie písmeno kľúča a tento riadok sa prejde, aby sa našiel nadpis stĺpca, ktorý zodpovedá znaku správy. Písmeno na priesečníku je zašifrované písmeno.
Napríklad prvé písmeno otvoreného textu, u, je spárované s D, prvým písmenom kľúča. Preto sa používa riadok A a stĺpec D Vigenerovho štvorca, konkrétne D. Podobne pre druhé písmeno otvoreného textu sa používa druhé písmeno kľúča. Písmeno v riadku T a stĺpci V je X. Zvyšok otvoreného textu je zašifrovaný podobným spôsobom:
Čistý text: utoknausvit
Kľúč: DVEREDVEREDV
Šifrovaný text: LXFOPVEFRNHR
Kryptoanalýza
upraviťMyšlienkou Vigenerovej šifry, je zamaskovať frekvenciu písmen v otvorenom texte, aby zasahovala do priamej aplikácie frekvenčnej analýzy. Napríklad, ak je P najčastejšie písmeno v šifrovom texte, možno sa domnievať, že P zodpovedá e, pretože e je najčastejšie používané písmeno v slovenčine.
Hlavnou slabinou Vigenerovej šifry je opakujúci sa znak jej kľúča.