Hill Cipher

Hillin salaus on lineaariseen algebraan ja modulaariseen aritmetiikkaan perustuva polygrammikorvaussalaus . Amerikkalaisen matemaatikko Lester Hillin keksi vuonna 1929. Se oli ensimmäinen salaus, joka mahdollisti käytännössä (vaikkakin vaikeasti) toiminnan samanaikaisesti useammalla kuin kolmella merkillä. Hillin salaus ei ole löytänyt käytännön sovellusta kryptografiassa , koska murtuman vastustuskyky on heikko ja suurten suorien ja käänteisten matriisien generointialgoritmeja ei ole kuvattu.

Historia

Hillin salakirjoitus kuvattiin ensimmäisen kerran artikkelissa "Cryptography in an Algebraic Alphabet" [1] , joka julkaistiin The American Mathematical Monthly -lehdessä kesä-heinäkuussa 1929. Saman vuoden elokuussa Hill laajensi aihetta ja piti kryptografiasta puheen American Mathematical Societylle Boulderissa, Coloradossa [2] . Hänen luentonsa johti myöhemmin toiseen artikkeliin "Concerning Certain Linear Transformation Apparatus of Cryptography" [3] , joka julkaistiin The American Mathematical Monthly -lehdessä maaliskuussa 1931. David Kahn kuvaili Code Breakers -kirjassaan Hill-salausta ja sen paikkaa kryptografian historiassa [4] seuraavasti:

Hill oli yksi niistä, jotka kehittivät yleisen ja tehokkaan menetelmän. Lisäksi Hill-salaus siirsi ensimmäistä kertaa polygrammeja käyttävän kryptografian käytännön tieteenalojen luokkaan.

Alkuperäinen teksti (englanniksi)[ näytäpiilottaa] Mutta Hill yksin keksi vallan ja yleisyyden menetelmän. Lisäksi hänen menetelmänsä, joka valmisti polygraafisen kryptografian, on ensimmäistä kertaa käytännöllinen.

Kuvaus Hill-salauksesta

Hillin salaus on polygrammisalaus , joka voi käyttää suuria lohkoja käyttämällä lineaarista algebraa. Jokaiselle aakkoston kirjaimelle on annettu numero modulo 26. Latinalaisessa aakkostossa käytetään usein yksinkertaisinta mallia: A = 0, B = 1, ..., Z = 25, mutta tämä ei ole salauksen olennainen ominaisuus . N kirjaimen lohkoa käsitellään n - ulotteisena vektorina ja kerrotaan modulo 26 n  ×  n - matriisilla . Jos modulo-kantana käytetään numeroa, joka on suurempi kuin 26, voidaan käyttää erilaista numeerista mallia numeroiden kirjainten yhteensovittamiseksi sekä välilyöntien ja välimerkkien lisäämiseksi [5] . Matriisin elementit ovat avainasemassa. Matriisin on oltava käännettävä, jotta salauksen purku on mahdollista [6] [7] . ${\mathbb {Z}}_{{26}}^{n}$

Kun n = 3, järjestelmä voidaan kuvata seuraavasti:

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

tai matriisimuodossa:

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

tai

C=KP{\pmod {26)),

jossa ja ovat sarakevektorit, joiden korkeus on 3 ja jotka edustavat vastaavasti selkeää tekstiä ja salatekstiä, ja on 3 × 3 -matriisi, joka edustaa salausavainta. Toiminnot suoritetaan modulo 26. $P$ $C$ $K$

Viestin salauksen purkamiseksi on hankittava käänteinen avainmatriisi . Käänteimatriisien laskemiseen on olemassa vakiomenetelmiä (katso tapoja löytää käänteismatriisi ), mutta kaikilla matriiseilla ei ole käänteistä (katso käänteimatriisi ). Matriisilla on käänteisarvo silloin ja vain, jos sen determinantti on muu kuin nolla eikä sillä ole yhteisiä jakajia moduulikannan kanssa [8] . Jos matriisin determinantti on nolla tai sillä on yhteinen jakaja modulo-kannan kanssa, niin kyseistä matriisia ei voi käyttää Hill-salauksessa, vaan on valittava toinen matriisi (muuten salateksti on salauskelvoton). Yllä olevat ehdot täyttäviä matriiseja on kuitenkin runsaasti [6] . $K^{-1}$

Yleensä salausalgoritmi voidaan ilmaista seuraavasti [6] [9] :

Salaus: . $C=E(K,P)=KP{\pmod {26))$

Salauksen purku: . $P=D(K,C)=K^{-1}C{\pmod {26}}=K^{-1}KP{\pmod {26}}=P$

Esimerkki

Seuraavassa esimerkissä [7] käytetään latinalaisia kirjaimia A:sta Z:hen, vastaavat numeroarvot on annettu taulukossa.

A	B	C	D	E	F	G	H	minä	J	K	L	M	N	O	P	K	R	S	T	U	V	W	X	Y	Z
0	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen	yksitoista	12	13	neljätoista	viisitoista	16	17	kahdeksantoista	19	kaksikymmentä	21	22	23	24	25

Salaus

Harkitse viestiä "ACT" ja seuraavaa avainta (GYBNQKURP kirjaimellisessa muodossa):

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

Tämä matriisi on käännettävä, koska sen determinantti ei ole nolla eikä sillä ole yhteisiä jakajia moduulikannan kanssa. Vaara, että avainmatriisin determinantilla on yhteisiä jakajia modulo-kannan kanssa, voidaan eliminoida valitsemalla moduulikannan alkuluku . Esimerkiksi Hill-salauksen kätevämmässä versiossa 3 ylimääräistä merkkiä ( välilyönti , piste ja kysymysmerkki) lisätään aakkosiin, jotta moduulikanta kasvaa arvoon 29 [5] .

Koska kirjain "A" vastaa numeroa 0, "C" - 2, "T" - 19, viesti on vektori

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

Sitten salattu vektori on

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

Vektori vastaa salatekstiä "POH". Oletetaan nyt, että viestimme oli "Kissa":

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

Nyt salattu vektori on

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

Tämä vektori vastaa salatekstiä "FIN". Voidaan nähdä, että salatekstin jokainen kirjain on muuttunut. Hillin salaus saavutti leviämisen Shannonin mukaan , ja n - ulotteinen Hill-salaus voi saavuttaa diffuusion n merkkiä kerrallaan.

Salauksen purku

Käänteinen avainmatriisi:

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

Otetaan salateksti edellisestä "POH"-esimerkistä:

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

Tämä vektori vastaa viestiä "ACT".

Turvallisuus

Tavallinen Hill-salaus on alttiina valitulle selväkieliselle hyökkäykselle, koska se käyttää lineaarisia operaatioita. Salausanalyytikko, joka sieppaa viestisymboli /salatekstisymboli -parin, pystyy muodostamaan lineaarisen yhtälöjärjestelmän , jota ei yleensä ole vaikea ratkaista. Jos käy ilmi, että järjestelmää ei voi ratkaista, sinun tarvitsee vain lisätä muutama pari viestimerkkiä / salatekstimerkkiä. Tällaiset laskelmat perinteisten lineaarialgebra-algoritmien avulla vaativat hyvin vähän aikaa. Tässä suhteessa kryptografisen vahvuuden lisäämiseksi siihen tulisi lisätä joitain epälineaarisia operaatioita. Lineaaristen operaatioiden, kuten Hill-salauksessa, ja epälineaaristen vaiheiden yhdistelmä johti permutaatio-permutaatioverkon luomiseen (kuten Feistel-verkko ). Siksi nykyaikaisia lohkosalauksia voidaan tietystä näkökulmasta pitää eräänlaisena polygrammisalauksena [7] [8] . $n^{2}$

Avaimen pituus

Avaimen pituus on kaikkien mahdollisten avainten lukumäärän binäärilogaritmi . Matriiseja on n  ×  n . Siten on avaimen pituuden yläraja Hill-salauksessa, jossa käytetään n  ×  n -matriisia . Tämä on vain yläraja, koska jokainen matriisi ei ole käännettävä, ja vain tällaiset matriisit voivat olla avain. Käännettävien matriisien lukumäärä voidaan laskea käyttämällä Kiinan jäännöslausetta . Matriisi on käännettävä modulo 26 jos ja vain jos se on käännettävä modulo 2 ja modulo 13 [8] . $26^{{n^{2}}}$ $\log _{2}(26^{n^{2}})\noin 4{,}7n^{2}$

Käännettävien modulo 2 ja 13 n  ×  n matriisien lukumäärä on sama kuin lineaarisen ryhmän GL( n ,  Z 2 ) ja GL( n ,  Z 13 ) järjestys:

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

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

Käännettävien modulo 26 matriisien lukumäärä on yhtä suuri kuin näiden lukujen tulo:

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

Lisäksi olisi viisasta välttää liikaa nollia avainmatriisissa, koska ne vähentävät diffuusiota. Tuloksena käy ilmi, että Hillin vakiosalauksen tehollinen avaintila on noin . 5 × 5 Hill -salauksessa tämä olisi noin 114 bittiä. On selvää, että raaka voima ei ole tehokkain hyökkäys Hill-salausta vastaan [7] . $4{,}64n^{2}-1{,}7$

Mekaaninen toteutus

Kun työskentelet kahdella merkillä kerrallaan, Hill-salauksella ei ole erityisiä etuja Playfair-salaukseen verrattuna ja se on jopa huonompi salauksen vahvuuden ja paperilla laskemisen helppouden suhteen. Kun avaimen koko kasvaa, salaus muuttuu nopeasti paperilla olevien ihmisten laskelmien ulottumattomiksi. Mitan 6 Hill-salaus toteutettiin mekaanisesti. Hill ja kumppani saivat patentin laitteelle ( US-patentti 1 845 947 ), joka suoritti 6 × 6 -matriisin kertolaskumoduulin 26 käyttämällä hammaspyörä- ja ketjujärjestelmää. Vaihteiden (ja siten myös avaimen) sijaintia ei voitu muuttaa tietylle laitteelle, joten kolminkertaista salausta suositeltiin turvallisuussyistä. Tämä yhdistelmä oli erittäin vahva vuonna 1929, ja se osoittaa, että Hill varmasti ymmärsi hämmennyksen ja diffuusion käsitteet. Laite oli kuitenkin melko hidas, joten toisessa maailmansodassa Hillin koneita käytettiin vain radiosignaalien kolmimerkkisen koodin salaamiseen [10] .

Muistiinpanot

↑ Lester S. Hill. Kryptografia algebrallisissa aakkosissa : Artikkeli . - 1929. - S. 7 .
↑ Chris Christensen. Lester Hill Revisited // Taylor & Francis Group, LLC : Artikkeli. - 2014. - S. 297 . — ISSN 0161-1194 .
↑ Lester S. Hill. Tietyt kryptografian lineaariset muunnoslaitteet (englanniksi) // The American Mathematical Monthly. - 1931. - maaliskuu. - S. 135-154 .
↑ David Kahn. Codebreakers: Salaisen viestinnän kattava historia muinaisista ajoista Internetiin . - Simon ja Schuster. - New York: Scribner, 1996. - s . 405 . — 723 s. — ISBN 0-684-83130-9 .
↑ 1 2 Murray Eisenberg. Hill Ciphers: Lineaarinen algebraprojekti Mathematican kanssa .
↑ 1 2 3 William Stallings. Salaus ja verkkosuojaus: periaatteet ja käytännöt. - 5. - Pearson Education, 2011. - S. 46-49. - ISBN 978-0-13-609704-4 .
↑ 1 2 3 4 A. VN Krishna, Dr. A. Vinaya Babu. Muokattu Hillin salausalgoritmi tietojen salaamiseen tiedonsiirrossa (englanniksi) // Computer Science and Telecommunications : Georgian Electronic Scientific Journal. - 2007. - Nro 3 (14) . - S. 78-83 . — ISSN 1512-1232 .
↑ 1 2 3 A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheryomushkin. Salauksen perusteet. - 2. painos - Helios ARV, 2002. - S. 115-119. – 480 s. — ISBN 5-85438-137-0 .
↑ Dorothy Elizabeth Robling Denning. Salaus ja tietoturva . - Lontoo: Addison-Wesley Publishing Company, 1982. - S. 88-89 . – 400 s. — ISBN 0-201-10150-5 .
↑ Friedrich L. Bauer. Salatut salaisuudet: kryptologian menetelmät ja maksimit. - Springer, 2002. - S. 85. - 474 s. - ISBN 978-3-662-04738-5 .

Kirjallisuus

William Stallings. Salaus ja verkkosuojaus: periaatteet ja käytännöt. - Pearson, 2011. - s. 46-49. — 711 s. - ISBN 978-0-13-609704-4 .
David Kahn. Codebreakers: Salaisen viestinnän kattava historia muinaisista ajoista Internetiin. - Simon ja Schuster, 1996. - S. 405. - 723 s. - ISBN 978-0-13-609704-4 .
Pääosissa Jeffrey Overbey, William Traves, Jerzy Wojdylo. Hill-salauksen avainvälillä. - 2005. - T. 29 . — s. 59–72. - doi : 10.1080/0161-110591893771 .
Wade Trappe, Lawrence C. Washington. Johdatus kryptografiaan: koodausteorialla . - Pearson Prentice Hall, 2006. - P. 34-38 . — 577 s. — ISBN 0-13-198199-5 .
Craig P. Bauer. Salainen historia: Kryptologian tarina. - CRC Press, 2013. - S. 227-228. — 575 s. — ISBN 978-1-4665-6187-8 .