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. +more 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ř. +more takovéto přiřazení:.

562x562px

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. +more 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. +more # 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 +morepng'>110px. Lze snadno ověřit, že matice K splňuje podmínky a lze také snadno spočítat matici 130px.

Š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 . +more 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 200px,

potom 500px,

470px.

Š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). +more 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. +more 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 220px.

520px,

450px.

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ř. +more 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. ). +more 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

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 * http://is.muni.cz/th/98552/fi_b/bc.txt

Kategorie:Klasické šifry