Hillova šifra
![ikona](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/48px-Broom_icon.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Preferences-system.svg/16px-Preferences-system.svg.png)
Hillova šifra je polygrafická substituční šifra vycházející z lineární algebry a využívaná v klasické kryptografii. Vynalezena byla americkým matematikem Lesterem S. Hillem v roce 1929. Jedná se o první polygrafickou šifru, která umožňovala pracovat na více než třech symbolech zároveň.
Úvod
Tento článek uvádí jednoduchý příklad šifrování textu vycházející z tzv. Hillovy šifry. Jeho hlavním cílem je poskytnout a demonstrovat praktickou aplikaci maticového počtu na úrovni vyšších ročníků středních škol a víceletých gymnázií. Text předpokládá základní orientaci v problematice maticového počtu (matice, inverzní matice, determinant matice, maticové násobení) a znalost modulární aritmetiky.
Abeceda
Abecedou budeme rozumět písmena anglické abecedy od A do Z, přičemž každé z nich bude jednoznačně reprezentováno libovolným celým číslem od 0 do 25. Zvolme tedy např. takovéto přiřazení:
Zpráva
Zprávou bude jakýkoliv text, který chceme šifrovat a poté dešifrovat. Zpráva smí být složena pouze ze znaků definované abecedy. Nechť námi zvolenou zprávou je slovo MATEMATIKA, čísly je (podle výše uvedené tabulky) tato zpráva reprezentována jako 12 0 19 4 12 0 19 8 10 0.
Šifrovací a dešifrovací klíč
Šifrovacím klíčem nazveme matici, kterou použijeme k zakódování zprávy. Je třeba, aby byly splněny následující podmínky:
- Matice je typu mxm (čtvercová) a platí, že počet znaků zprávy je dělitelný m.
- Determinant matice a počet znaků abecedy jsou nesoudělná čísla.
- Matice je invertibilní (regulární).
Dešifrovacím klíčem je potom matice inverzní k šifrovacímu klíči (proto je třeba splnit podmínku 3).
Zvolme tedy jako klíč např. matici . Lze snadno ověřit, že matice K splňuje podmínky a lze také snadno spočítat matici
.
Šifrování
Šifrování pomocí Hillovy šifry je reprezentováno maticovým násobením, a to tak, že zprávu rozdělíme na úseky délky m (proto musí platit výše uvedená podmínka 1), které vepíšeme do matice Z jako sloupce. Poté provedeme součin K . Z ≡ S mod l (kde l je počet znaků v abecedě). Sloupce matice S (tj. zašifrované matice) již jen přepíšeme do jednoho řádku a čísla nahradíme znaky podle naší abecedy. Získáme tak zašifrovanou zprávu.
V našem příkladu tedy máme zprávu zapsanou maticově jako ,
potom ,
.
Šifrovaná zpráva má tedy číselnou podobu 12 24 23 0 12 24 1 14 10 20 a písmennou podobu MYXAMYBOKU.
Stojí za povšimnutí, že zatímco slabika MA byla v obou svých výskytech kódována jako MY, neznamená to, že např. A je v tomto algoritmu vždy nahrazeno hláskou Y (na konci slova místo A máme nikoliv Y ale U). Je to proto, že Hillova šifra převádí celé m-tice znaků a ne jen jednotlivé znaky. Díky tomu je velmi nesnadné prolomit tuto šifru použitím frekvenční analýzy.
Dešifrování
Dešifrování kódovaného textu probíhá obdobně. Šifrovanou zprávu převedeme na čísla a rozdělíme na úseky o m znacích, ty vepíšeme do sloupců matice S, kterou vynásobíme zleva maticí K−1 a získáme tak původní zprávu zapsanou číselně ve sloupcích matice Z ≡ K−1. S mod l. Písmenný tvar zprávy dostaneme opět pomocí tabulky s abecedou.
V našem příkladu tedy máme zprávu MYXAMYBOKU, číselně vyjádřenou jako 12 24 23 0 12 24 1 14 10 20, pak matice .
,
.
Dešifrovaná zpráva má tedy číselnou podobu 12 0 19 4 12 0 19 8 10 0 a písmennou podobu MATEMATIKA.
Problém s první podmínkou
Podle podmínky 1 pro šifrovací matici, kterou jsme uvedli výše, bychom měli vždy tuto matici volit s ohledem na počet znaků zprávy tak, aby počet řádků matice dělil počet znaků zprávy beze zbytku. Co ale dělat v případě, kdy bychom potřebovali šifrovat zprávu délky např. 11 znaků? Číslo 11 je prvočíslo a nejmenší možná matice by tehdy musela být typu 11x11, pročež by ale bylo velmi obtížné byť jen ověřit, zda vyhovuje zbylým dvěma podmínkám.
Jednou z možností, jak tento problém jednoduše eliminovat je kupříkladu rozšíření abecedy o jeden či více speciálních znaků (mezera, interpunkce aj.). Zvolený znak bychom doplnili na konec zprávy a mohli poté šifrovat maticí typu 2x2 či 3x3. Vhodnou abecedou je tedy i jakákoliv znaková soustava se speciálními znaky.
Odkazy
Reference
V tomto článku byl použit překlad textu z článku Hill cipher na anglické Wikipedii.
Literatura
- Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June–July 1929, pp. 306–312.
Externí odkazy
- http://fyztyd.fjfi.cvut.cz/2008/cd/prispevky/sbpdf/cisla.pdf[nedostupný zdroj]
- http://is.muni.cz/th/98552/fi_b/bc.txt