Hill Cipher

A Hill-rejtjel egy poligram - helyettesítő rejtjel , amely lineáris algebrán és moduláris aritmetikán alapul . Lester Hill amerikai matematikus találta fel 1929-ben. Ez volt az első titkosítás, amely lehetővé tette a gyakorlatban (ha nehezen is) háromnál több karakterrel egyidejűleg működni. A Hill titkosítás nem talált gyakorlati alkalmazásra a kriptográfiában a repedésekkel szembeni gyenge ellenállás és a nagy direkt és inverz mátrixok generálására szolgáló algoritmusok leírásának hiánya miatt .

Történelem

Hill titkosítását először a "Cryptography in an Algebraic Alphabet" [1] című cikk írta le , amely a The American Mathematical Monthly -ben jelent meg 1929 júniusában-júliusában. Az év augusztusában Hill kibővítette a témát, és beszédet tartott a kriptográfiáról az American Mathematical Society-ben a Colorado állambeli Boulderben [2] . Előadása később egy második tanulmányhoz vezetett, "Concerning Certain Linear Transformation Apparatus of Cryptography" [3] , amely a The American Mathematical Monthly folyóiratban jelent meg 1931 márciusában. David Kahn a Code Breakers című művében a következőképpen írta le a Hill-rejtjelet és annak helyét a kriptográfia történetében [4] :

Hill egyike volt azoknak, akik általános és hatékony módszert dolgoztak ki. Ezenkívül a Hill-rejtjel először helyezte át a poligramokat használó kriptográfiát a gyakorlati tudományágak kategóriájába.

Eredeti szöveg (angol)[ showelrejt] De Hill egyedül dolgozta ki a hatalom és az általánosság módszerét. Ezen túlmenően a poligrafikus kriptográfiát készített eljárása első ízben praktikus.

A hegy titkosításának leírása

A Hill-rejtjel egy poligram-rejtjel , amely nagy blokkokat tud használni lineáris algebra segítségével. Az ábécé minden betűjéhez modulo 26-os szám tartozik. A latin ábécé esetében gyakran a legegyszerűbb sémát használják: A = 0, B = 1, ..., Z = 25, de ez nem lényeges tulajdonsága a rejtjelnek. . Egy n betűből álló blokkot n -dimenziós vektorként kezelünk, és a modulo 26-ot megszorozzuk egy n  ×  n mátrixszal . Ha 26-nál nagyobb számot használunk modulo alapként, akkor egy másik numerikus séma használható a számok betűinek egyeztetésére, szóközök és írásjelek hozzáadására [5] . A mátrix elemei a kulcs. A mátrixnak invertálhatónak kell lennie ahhoz, hogy a visszafejtési művelet lehetséges legyen [6] [7] . ${\mathbb {Z}}_{{26}}^{n}$

n = 3 esetén a rendszer a következőképpen írható le:

{\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}}

vagy mátrix formában:

{\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}},

vagy

C=KP{\pmod {26)),

ahol és a 3 magasságú oszlopvektorok, amelyek rendre a nyílt szöveget és a titkosított szöveget reprezentálják, és egy 3 × 3-as mátrix, amely a titkosítási kulcsot reprezentálja. A műveletek végrehajtása modulo 26. $P$ $C$ $K$

Az üzenet visszafejtéséhez be kell szerezni az inverz kulcsmátrixot . Vannak szabványos módszerek az inverz mátrixok kiszámítására (lásd az inverz mátrix megtalálásának módjait ), de nem minden mátrixnak van inverze (lásd inverz mátrix ). Egy mátrixnak akkor és csak akkor lesz inverze, ha a determinánsa nem nulla, és nincs közös osztója a modulusalappal [8] . Ha egy mátrix determinánsa nulla, vagy közös osztója van a modulo alappal, akkor az a mátrix nem használható Hill-rejtjelben, és másik mátrixot kell választani (különben a rejtjelezett szöveg megfejthetetlen lesz). A fenti feltételeket kielégítő mátrixok azonban bőségesen léteznek [6] . $K^{-1}$

Általában a titkosítási algoritmus a következőképpen fejezhető ki [6] [9] :

Titkosítás: . $C=E(K,P)=KP{\pmod {26))$

Dekódolás: . $P=D(K,C)=K^{-1}C{\pmod {26}}=K^{-1}KP{\pmod {26}}=P$

Példa

A következő példában [7] latin betűket használunk A-tól Z-ig, a megfelelő számértékeket a táblázat tartalmazza.

A	B	C	D	E	F	G	H	én	J	K	L	M	N	O	P	K	R	S	T	U	V	W	x	Y	Z
0	egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16	17	tizennyolc	19	húsz	21	22	23	24	25

Titkosítás

Vegye figyelembe az "ACT" üzenetet és a következő kulcsot (GYBNQKURP szó szerinti formában):

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

Ez a mátrix invertálható, mivel a determinánsa nem egyenlő nullával, és nincs közös osztója a modulusalappal. Az a veszély, hogy a kulcsmátrix determinánsának közös osztói lesznek a modulo alappal, kiküszöbölhető, ha egy prímszámot választunk modulo alapnak. Például a Hill titkosítás egy kényelmesebb változatában 3 extra karaktert ( szóköz , pont és kérdőjel) adnak az ábécéhez, hogy a modulusalapot 29-re növeljék [5] .

Mivel az "A" betű a 0-nak, "C" - 2, "T" - 19-nek felel meg, az üzenet egy vektor

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

Ekkor a titkosított vektor lesz

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}}.

A vektor a "POH" titkosított szövegnek felel meg. Tegyük fel, hogy az üzenetünk "CAT" volt:

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

Most a titkosított vektor lesz

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}}.

Ez a vektor a "FIN" titkosított szövegnek felel meg. Látható, hogy a rejtjelezett szöveg minden betűje megváltozott. A Hill-rejtjel elérte a terjedést Shannon szerint , egy n - dimenziós Hill-rejtjel pedig n karakter diffúzióját képes elérni egyszerre.

Dekódolás

Inverz kulcsmátrix:

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

Vegyük a titkosított szöveget az előző „POH” példából:

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

Ez a vektor az "ACT" üzenetnek felel meg.

Biztonság

A szabványos Hill titkosítás sebezhető a választott egyszerű szöveges támadásokkal szemben, mivel lineáris műveleteket használ. Az üzenetszimbólum/titkosszöveg szimbólumpárt elfogó kriptoanalitikus képes lesz lineáris egyenletrendszert összeállítani , amit általában nem nehéz megoldani. Ha kiderül, hogy a rendszer megoldhatatlan, akkor csak néhány pár üzenetkarakter / titkosított szöveg karakterpárt kell hozzáadnia. Az ilyen, hagyományos lineáris algebrai algoritmusokkal végzett számítások nagyon kevés időt igényelnek. Ebben a tekintetben a kriptográfiai erősség növelése érdekében hozzá kell adni néhány nemlineáris műveletet. A Hill-rejtjelhez hasonlóan lineáris műveletek és nemlineáris lépések kombinációja egy permutáció-permutációs hálózat létrehozásához vezetett (mint például a Feistel hálózat ). Ezért bizonyos szempontból a modern blokk-rejtjelek a poligram-rejtjelek egy típusának tekinthetők [7] [8] . $n^{2}$

Kulcshossz

A kulcs hossza az összes lehetséges kulcs számának bináris logaritmusa . n  ×  n mátrix van . Ezért ez a kulcshossz felső korlátja egy n  ×  n mátrixot használó Hill-rejtjel esetén . Ez csak egy felső korlát, mivel nem minden mátrix invertálható, és csak az ilyen mátrixok lehetnek kulcsok. Az invertálható mátrixok száma a kínai maradéktétel segítségével számítható ki . Egy mátrix akkor és csak akkor invertálható modulo 26 és modulo 13 [8] . $26^{{n^{2}}}$ $\log _{2}(26^{n^{2}})\approx 4{,}7n^{2}$

Az n  ×  n invertálható modulo 2 és 13 mátrixok száma megegyezik a GL( n ,  Z 2 ) és GL( n ,  Z 13 ) lineáris csoportok sorrendjével:

|K_{1}|=2^{n^{2}}(1-1/2)(1-1/2^{2})\pontok (1-1/2^{n}) ,

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

A modulo 26 invertálható mátrixok száma megegyezik a következő számok szorzatával:

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

Ezenkívül bölcs dolog lenne elkerülni a túl sok nullát a kulcsmátrixban, mivel ezek csökkentik a diffúziót. Ennek eredményeként kiderül, hogy a szabványos Hill-rejtjel effektív kulcstere kb . 5×5 Hill-rejtjel esetén ez körülbelül 114 bitet jelentene. Nyilvánvaló, hogy a nyers erő nem a leghatékonyabb támadás a Hill titkosítás ellen [7] . $4{,}64n^{2}-1{,}7$

Mechanikai megvalósítás

Ha egyszerre két karakterrel dolgozik, a Hill-rejtjel nem nyújt különösebb előnyt a Playfair-rejtjellel szemben, sőt a kriptográfiai erősség és a papíron történő számítás egyszerűsége tekintetében is alacsonyabb. A kulcs méretének növekedésével a rejtjel gyorsan elérhetetlenné válik a papíron végzett emberi számítások számára. A 6-os dimenziójú Hill titkosítást mechanikusan valósították meg. Hill és egy partnere szabadalmat kapott egy eszközre ( 1 845 947 amerikai egyesült államokbeli szabadalom ), amely 6 × 6-os mátrixszorzó modulo 26-ot hajtott végre fogaskerekek és láncok rendszerével. A fogaskerekek (és így a kulcs) elhelyezkedése egy adott eszköznél nem változtatható meg, ezért biztonsági okokból háromszoros titkosítás javasolt. Ez a kombináció nagyon erős volt 1929-ben, és azt mutatja, hogy Hill biztosan megértette a zűrzavar és diffúzió fogalmát. Az eszköz azonban meglehetősen lassú volt, így a második világháborúban Hill gépeit csak a rádiójelek három karakteres kódjának titkosítására használták [10] .

Jegyzetek

↑ Lester S. Hill. Kriptográfia algebrai ábécében : Cikk . - 1929. - S. 7 .
↑ Chris Christensen. Lester Hill Revisited // Taylor & Francis Group, LLC : Cikk. - 2014. - S. 297 . — ISSN 0161-1194 .
↑ Lester S. Hill. A kriptográfia bizonyos lineáris transzformációs berendezéseivel kapcsolatban (angol) // The American Mathematical Monthly. - 1931. - márc. - S. 135-154 .
↑ David Kahn. A kódtörők: A titkos kommunikáció átfogó története az ókortól az Internetig . — Simon és Schuster. - New York: Scribner, 1996. - 405. o . — 723 p. — ISBN 0-684-83130-9 .
↑ 1 2 Murray Eisenberg. Hill Ciphers: Lineáris algebra projekt a Mathematicával .
↑ 1 2 3 William Stallings. Kriptográfia és hálózatbiztonság: alapelvek és gyakorlatok. - 5. - Pearson Education, 2011. - S. 46-49. - ISBN 978-0-13-609704-4 .
↑ 1 2 3 4 A. VN Krishna, Dr. A. Vinaya Babu. Módosított Hill-rejtjelezési algoritmus az adatok titkosítására az adatátvitelben (angol) // Számítástechnika és távközlés : Georgian Electronic Scientific Journal. - 2007. - 3. szám (14) . - S. 78-83 . — ISSN 1512-1232 .
↑ 1 2 3 A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cserjomuskin. A kriptográfia alapjai. - 2. kiadás - Helios ARV, 2002. - S. 115-119. — 480 s. — ISBN 5-85438-137-0 .
↑ Dorothy Elizabeth Robling Denning. Kriptográfia és adatbiztonság . - London: Addison-Wesley Publishing Company, 1982. - S. 88 -89. — 400 s. — ISBN 0-201-10150-5 .
↑ Friedrich L. Bauer. Megfejtett titkok: A kriptológia módszerei és maximumai. - Springer, 2002. - S. 85. - 474 p. - ISBN 978-3-662-04738-5 .

Irodalom

William Stallings. Kriptográfia és hálózatbiztonság: alapelvek és gyakorlatok. - Pearson, 2011. - P. 46-49. — 711 p. - ISBN 978-0-13-609704-4 .
David Kahn. A kódtörők: A titkos kommunikáció átfogó története az ókortól az Internetig. - Simon és Schuster, 1996. - P. 405. - 723 p. - ISBN 978-0-13-609704-4 .
Jeffrey Overbey, William Traves, Jerzy Wojdylo. A Hill Rejtjel kulcsterén. - 2005. - T. 29 . — P. 59–72. - doi : 10.1080/0161-110591893771 .
Wade Trappe, Lawrence C. Washington. Bevezetés a kriptográfiába: Kódoláselmélettel . - Pearson Prentice Hall, 2006. - P. 34-38 . — 577 p. — ISBN 0-13-198199-5 .
Craig P. Bauer. Titkos történelem: A kriptológia története. - CRC Press, 2013. - P. 227-228. — 575 p. — ISBN 978-1-4665-6187-8 .