Hillova šifra

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:

1. Matice je typu mxm (čtvercová) a platí, že počet znaků zprávy je dělitelný m.
2. Determinant matice a počet znaků abecedy jsou nesoudělná čísla.
3. 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⁻¹ a získáme tak původní zprávu zapsanou číselně ve sloupcích matice Z ≡ K⁻¹. 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