Hill Cipher

Hillova šifra je polygramová substituční šifra založená na lineární algebře a modulární aritmetice . Vynalezen americkým matematikem Lesterem Hillem v roce 1929. Byla to první šifra, která umožnila v praxi (i když s obtížemi) pracovat současně s více než třemi znaky. Hillova šifra nenašla praktické uplatnění v kryptografii kvůli slabé odolnosti vůči praskání a chybějícímu popisu algoritmů pro generování velkých přímých a inverzních matic .

Historie

Hillova šifra byla poprvé popsána v článku „Cryptography in an Algebraic Alphabet“ [1] , publikovaném v The American Mathematical Monthly v červnu až červenci 1929. V srpnu téhož roku Hill toto téma rozšířil a přednesl projev o kryptografii k Americké matematické společnosti v Boulderu, Colorado [2] . Jeho přednáška později vedla k druhému článku „Concerning Certain Linear Transformation Apparatus of Cryptography“ [3] , který byl publikován v The American Mathematical Monthly v březnu 1931. David Kahn ve svém Code Breakers popsal Hillovu šifru a její místo v historii kryptografie [4] takto:

Hill byl jedním z těch, kteří vyvinuli obecnou a účinnou metodu. Hillova šifra navíc poprvé přenesla kryptografii pomocí polygramů do kategorie praktických disciplín.

Původní text (anglicky)[ zobrazitskrýt] Ale Hill sám vymyslel metodu moci a obecnosti. Jeho postup z polygrafické kryptografie je navíc poprvé praktický.

Popis Hillovy šifry

Hillova šifra je polygramová šifra , která může používat velké bloky pomocí lineární algebry. Každému písmenu abecedy je přiřazeno číslo modulo 26. Pro latinskou abecedu se často používá nejjednodušší schéma: A = 0, B = 1, ..., Z = 25, ale to není podstatná vlastnost šifry . Blok n písmen je považován za n - rozměrný vektor a vynásobený modulo 26 maticí n  ×  n . Je-li jako základ modulo použito číslo větší než 26, pak lze použít jiné číselné schéma, aby odpovídalo písmenům čísel a přidalo se mezery a interpunkce [5] . Klíčové jsou prvky matice. Matice musí být invertibilní , aby byla možná operace dešifrování [6] [7] . ${\mathbb {Z}}_{{26}}^{n}$

Pro n = 3 lze systém popsat následovně:

{\begin{cases}c_{1}=k_{11}p_{1}+k_{12}p_{2}+k_{13}p_{3}{\pmod {26)),\\ c_{2}=k_{21}p_{1}+k_{22}p_{2}+k_{23}p_{3}{\pmod {26)),\\c_{3}=k_{31} p_{1}+k_{32}p_{2}+k_{33}p_{3}{\pmod {26}},\\\end{cases}}

nebo v maticové podobě:

{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix))={\begin{bmatrix}k_{11}&k_{12}&k_{13} \\k_{21}&k_{22}&k_{23}\\k_{31}&k_{32}&k_{33}\end{bmatrix}}{\begin{bmatrix}p_{1}\\p_{2} \\p_{3}\end{bmatrix}}{\pmod {26}},

nebo

C=KP{\pmod {26)),

kde a jsou sloupcové vektory o výšce 3 představující holý text a šifrovaný text a je matice 3×3 představující šifrovací klíč. Operace se provádějí modulo 26. $P$ $C$ $K$

Aby bylo možné zprávu dešifrovat, je nutné získat matici inverzního klíče . Existují standardní metody pro výpočet inverzní matice (viz způsoby, jak najít inverzní matici ), ale ne všechny matice mají inverzní matici (viz inverzní matice ). Matice bude mít inverzní hodnotu právě tehdy, když její determinant je nenulový a nemá žádné společné dělitele s modulovou bází [8] . Pokud je determinant matice nula nebo má společného dělitele se základnou modulo, pak tuto matici nelze použít v Hillově šifře a je třeba zvolit jinou matici (jinak bude šifrový text nerozluštitelný). Matic, které splňují výše uvedené podmínky, však existuje velké množství [6] . $K^{-1}$

Obecně lze šifrovací algoritmus vyjádřit následovně [6] [9] :

Šifrování: . $C=E(K,P)=KP{\pmod {26))$

Dešifrování: . $P=D(K,C)=K^{-1}C{\pmod {26}}=K^{-1}KP{\pmod {26}}=P$

Příklad

V následujícím příkladu [7] jsou použita latinská písmena od A do Z, odpovídající číselné hodnoty jsou uvedeny v tabulce.

A	B	C	D	E	F	G	H	já	J	K	L	M	N	Ó	P	Q	R	S	T	U	PROTI	W	X	Y	Z
0	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet	21	22	23	24	25

Šifrování

Zvažte zprávu „ACT“ a následující klíč (GYBNQKURP v doslovné podobě):

K={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix)).

Tato matice je invertibilní, protože její determinant není roven nule a nemá žádné společné dělitele se základnou modulu. Nebezpečí, že determinant matice klíče bude mít společné dělitele se základnou modulo, lze eliminovat volbou prvočísla jako základu modulo. Například v pohodlnější variantě Hillovy šifry jsou do abecedy přidány 3 znaky navíc ( mezera , tečka a otazník), aby se základ modulu zvýšil na 29 [5] .

Protože písmeno "A" odpovídá číslu 0, "C" - 2, "T" - 19, zpráva je vektorová

P_{1}={\begin{bmatrix}0\\2\\19\end{bmatrix}}.

Potom bude zašifrovaný vektor

C_{1}=KP_{1}{\pmod {26}}={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix}}{\begin{bmatrix}0\\2\ \19\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}15\\14\\7\end{bmatrix}}.

Vektor odpovídá šifrovému textu "POH". Nyní předpokládejme, že naše zpráva byla „CAT“:

P_{2}={\begin{bmatrix}2\\0\\19\end{bmatrix}}.

Nyní bude zašifrovaný vektor

C_{2}=KP_{2}{\pmod {26}}={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix}}{\begin{bmatrix}2\\0\ \19\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}5\\8\\13\end{bmatrix}}.

Tento vektor odpovídá šifrovému textu "FIN". Je vidět, že každé písmeno šifrového textu se změnilo. Hillova šifra dosáhla šíření podle Shannona a n - rozměrná Hillova šifra může dosáhnout šíření n znaků najednou.

Dešifrování

Inverzní matice klíče:

K^{-1}{\pmod {26}}={\begin{bmatrix}8&5&10\\21&8&21\\21&12&8\end{bmatrix}}.

Vezměme si šifrový text z předchozího příkladu „POH“:

P_{1}=K^{-1}C_{1}{\pmod {26}}={\begin{bmatrix}8&5&10\\21&8&21\\21&12&8\end{bmatrix}}{\begin{bmatrix }}{\begin{bmatrix} }15\\14\\7\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}0\\2\\19\end{bmatrix}}.

Tento vektor odpovídá zprávě "ACT".

Zabezpečení

Standardní Hillova šifra je zranitelná vůči vybraným útokům v prostém textu, protože používá lineární operace. Kryptanalytik, který zachytí dvojici symbol zprávy/šifrový text, bude schopen sestavit systém lineárních rovnic , jehož řešení obvykle není obtížné. Pokud se ukáže, že systém je neřešitelný, pak stačí přidat ještě pár párů znaku zprávy / znaku šifrového textu. Takové výpočty pomocí konvenčních algoritmů lineární algebry vyžadují velmi málo času. V tomto ohledu by pro zvýšení kryptografické síly měly být přidány některé nelineární operace. Kombinace lineárních operací, jako v Hillově šifře, a nelineárních kroků vedla k vytvoření permutační-permutační sítě (jako je Feistelova síť ). Moderní blokové šifry lze proto z určitého pohledu považovat za typ polygramových šifer [7] [8] . $n^{2}$

Délka klíče

Délka klíče je binární logaritmus počtu všech možných klíčů. Existuje n  ×  n matic . Je tedy horní hranice délky klíče pro Hillovu šifru používající matice n  ×  n . Toto je pouze horní hranice, protože ne každá matice je invertibilní a pouze takové matice mohou být klíčem. Počet invertibilních matic lze vypočítat pomocí čínské věty o zbytku . Matice je invertibilní modulo 26 právě tehdy, když je invertibilní modulo 2 a modulo 13 [8] . $26^{{n^{2}}}$ $\log _{2}(26^{n^{2}})\cca 4{,}7n^{2}$

Počet n  ×  n matic invertible modulo 2 a 13 se rovná řádu lineární grupy GL( n ,  Z 2 ) a GL ( n ,  Z 13 ): v tomto pořadí:

|K_{1}|=2^{n^{2}}(1-1/2)(1-1/2^{2})\tečky (1-1/2^{n}) ,

|K_{2}|=13^{n^{2}}(1-1/13)(1-1/13^{2})\tečky (1-1/13^{n}) .

Počet matic invertible modulo 26 se rovná součinu těchto čísel:

|K|=26^{n^{2}}(1-1/2)(1-1/2^{2})\tečky (1-1/2^{n})(1- 1/13)(1-1/13^{2})\tečky (1-1/13^{n}).

Bylo by také moudré vyhnout se příliš mnoha nulám v klíčové matici, protože snižují difúzi. V důsledku toho se ukazuje, že efektivní klíčový prostor standardní Hillovy šifry je asi . Pro šifru 5×5 Hill by to bylo přibližně 114 bitů. Je zřejmé, že hrubá síla není nejúčinnějším útokem na Hillovu šifru [7] . $4{,}64n^{2}-1{,}7$

Mechanické provedení

Při práci se dvěma postavami současně neposkytuje Hillova šifra žádné specifické výhody oproti šifře Playfair a je dokonce horší, pokud jde o šifrovací sílu a snadnost výpočtu na papíře. S rostoucí velikostí klíče se šifra rychle stává nedostupnou pro lidské výpočty na papíře. Hillova šifra dimenze 6 byla implementována mechanicky. Hill a partner získali patent na zařízení ( US Patent 1 845 947 ), které provádělo násobení matice 6 × 6 modulo 26 pomocí systému ozubených kol a řetězů. Umístění ozubených kol (a tedy klíče) nebylo možné u konkrétního zařízení změnit, proto bylo z bezpečnostních důvodů doporučeno trojité šifrování. Tato kombinace byla pro rok 1929 velmi silná a ukazuje, že Hill rozhodně chápal pojmy zmatek a difúze. Zařízení však bylo poměrně pomalé, takže ve druhé světové válce byly Hillovy stroje používány pouze k šifrování tříznakového kódu rádiových signálů [10] .

Poznámky

↑ Lester S. Hill. Kryptografie v algebraické abecedě : Článek . - 1929. - S. 7 .
↑ Chris Christensen. Lester Hill Revisited // Taylor & Francis Group, LLC: Článek. - 2014. - S. 297 . — ISSN 0161-1194 .
↑ Lester S. Hill. Concerning Some Linear Transformation Apparatus of Cryptography (anglicky) // The American Mathematical Monthly. - 1931. - březen. - S. 135-154 .
↑ David Kahn. The Codebreakers: Komplexní historie tajné komunikace od starověku po internet . — Simon a Schuster. - New York: Scribner, 1996. - S. 405 . — 723 s. — ISBN 0-684-83130-9 .
↑ 1 2 Murray Eisenberg. Hill Ciphers: A Linear Algebra Project with Mathematica .
↑ 1 2 3 William Stallings. Kryptografie a síťová bezpečnost: principy a postupy. - 5. - Pearson Education, 2011. - S. 46-49. - ISBN 978-0-13-609704-4 .
↑ 1 2 3 4 A. VN Krišna, Dr. A. Vinaya Babu. Upravený algoritmus Hill Cipher pro šifrování dat při přenosu dat (anglicky) // Počítačová věda a telekomunikace: Georgian Electronic Scientific Journal. - 2007. - č. 3 (14) . - S. 78-83 . — ISSN 1512-1232 .
↑ 1 2 3 A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheryomushkin. Základy kryptografie. - 2. vyd. - Helios ARV, 2002. - S. 115-119. — 480 s. — ISBN 5-85438-137-0 .
↑ Dorothy Elizabeth Robling Denning. Kryptografie a bezpečnost dat . - Londýn: Addison-Wesley Publishing Company, 1982. - S. 88 -89. — 400 s. — ISBN 0-201-10150-5 .
↑ Friedrich L. Bauer. Dešifrovaná tajemství: Metody a maxima kryptologie. - Springer, 2002. - S. 85. - 474 s. - ISBN 978-3-662-04738-5 .

Literatura

William Stallings. Kryptografie a síťová bezpečnost: principy a postupy. - Pearson, 2011. - S. 46-49. — 711 s. - ISBN 978-0-13-609704-4 .
David Kahn. The Codebreakers: Komplexní historie tajné komunikace od starověku po internet. - Simon a Schuster, 1996. - S. 405. - 723 s. - ISBN 978-0-13-609704-4 .
Jeffrey Overbey, William Traves, Jerzy Wojdylo. Na Keyspace of the Hill Cipher. - 2005. - T. 29 . — S. 59–72. - doi : 10.1080/0161-110591893771 .
Wade Trappe, Lawrence C. Washington. Úvod do kryptografie: S teorií kódování . - Pearson Prentice Hall, 2006. - S. 34-38 . — 577 s. — ISBN 0-13-198199-5 .
Craig P. Bauer. Tajná historie: Příběh kryptologie. - CRC Press, 2013. - S. 227-228. — 575 str. — ISBN 978-1-4665-6187-8 .