Hill Cipher

Hill sanders leicester

Hill Cipher is a polygram substitution cipher based on linear algebra and modular arithmetic . Invented by American mathematician Lester Hill in 1929. This was the first cipher that allowed in practice (albeit with difficulty) to simultaneously operate with more than three characters. Hill's cipher did not find practical application in cryptography due to the weak resistance to cracking and the lack of a description of algorithms for generating direct and inverse large matrices .

Content

History

Hill's cipher was first described in the article “Cryptography in an Algebraic Alphabet” ^[1] , published in The American Mathematical Monthly in June-July 1929. In August of that year, Hill expanded the topic and gave a talk about cryptography to the American Mathematical Society in Boulder, Colorado. ^[2] Later, his lecture led to the second article, Concerning Certain Linear Transformation Apparatus of Cryptography ^[3] , which was published in The American Mathematical Monthly in March 1931. David Kahn in his work “ Code Crackers ” described Hill's cipher and its place in the history of cryptography ^[4] :

Hill was one of those who developed a common and powerful method. In addition, Hill's cipher first converted cryptography using polygrams to the category of practical disciplines.
Original text
But Hill alone devised a method of power and generality. In addition, his procedure made polygraphic cryptography practical for the first time.

Hill Cipher Description

The Hill Cipher is a polygram cipher that can use large blocks using linear algebra. Each letter of the alphabet is assigned a number modulo 26. For the Latin alphabet, the simplest scheme is often used: A = 0, B = 1, ..., Z = 25, but this is not an essential property of the cipher. A block of n letters is considered as an n- dimensional vector and is multiplied modulo 26 by an n × n matrix. If a number greater than 26 is used as the base of the module, then you can use another numerical scheme to match the letters of the numbers and add spaces and punctuation marks ^[5] . Matrix elements are the key. Matrix must be reversible in $\mathbb {Z} _{26}^{n}$ ${\ displaystyle \ mathbb {Z} _ {26} ^ {n}}$ so that the decryption operation ^[6] ^[7] is possible.

For n = 3, the system can be described as follows:

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

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

or in matrix form:

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

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

or

C=KP{\pmod {26}},

{\ displaystyle C = KP {\ pmod {26}},}

Where $P$ ${\ displaystyle P}$ and $C$ ${\ displaystyle C}$ - column vectors of height 3 representing open and encrypted text, respectively, $K$ ${\ displaystyle K}$ - 3 × 3 matrix representing the encryption key. Operations are performed modulo 26.

In order to decrypt the message, you need to get the inverse matrix of the key $K^{-1}$ ${\ displaystyle K ^ {- 1}}$ . There are standard methods for computing inverse matrices (see methods for finding an inverse matrix ), but not all matrices have an inverse (see inverse matrix ). A matrix will have the opposite if and only if its determinant is non-zero and does not have common divisors with the base of the module ^[8] . If the determinant of the matrix is zero or has common divisors with the base of the module, then such a matrix cannot be used in the Hill cipher, and a different matrix must be selected (otherwise the ciphertext will not be able to decrypt). However, matrices that satisfy the above conditions exist in abundance ^[6] .

In general, the encryption algorithm can be expressed as follows ^[6] ^[9] :

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

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

Example

In the following example ^[7] , Latin letters from A to Z are used, the corresponding numerical values are given in the table.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	one	2	3	four	five	6	7	eight	9	ten	eleven	12	13	14	15	sixteen	17	18	nineteen	20	21	22	23	24	25

Encryption

Consider the message “ACT” and the key below (GYBNQKURP in literal form):

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

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

This matrix is invertible, since its determinant is nonzero and has no common divisors with the base of the module. The danger that the determinant of the key matrix will have common divisors with the base of the module can be eliminated by choosing a prime as the base of the module. For example, in a more convenient version of the Hill cipher, 3 additional characters (space, dot and question mark) are added to the alphabet to increase the base of the module to 29 ^[5] .

Since the letter “A” corresponds to the number 0, “C” - 2, “T” - 19, the message is a vector

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

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

Then the encrypted vector will be

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

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

The vector corresponds to the encrypted text "POH". Now suppose our message was “CAT”:

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

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

Now the encrypted vector will be

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

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

This vector corresponds to the ciphertext "FIN". It is seen that each letter of the ciphertext has changed. Hill's cipher achieved Shannon , and Hill's n- dimensional cipher can diffuse n characters at a time.

Decryption

Inverse Key Matrix:

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

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

Take the ciphertext from the previous “POH” example:

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

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

This vector corresponds to the message "ACT".

Cryptographic Strength

Hill's standard cipher is vulnerable to attack on the selected plaintext, because it uses linear operations. Cryptanalyst who will intercept $n^{2}$ ${\ displaystyle n ^ {2}}$ pairs the message symbol / ciphertext symbol can compose a system of linear equations, which is usually not difficult to solve. If it turns out that the system is not solvable, then you just need to add a few more message symbol / ciphertext symbol pairs. Such calculations using conventional linear algebra algorithms require very little time. In this regard, to increase the cryptographic stability, some nonlinear operations must be added to it. The combination of linear operations, as in Hill's cipher, and non-linear steps led to the creation of a permutation-permutation network (for example, Feistel's network ). Therefore, from a certain point of view, modern block ciphers can be considered as a type of polygram cipher ^[7] ^[8] .

Key Length

Key length is the binary logarithm of the number of all possible keys. Exists $26^{n^{2}}$ ${\ displaystyle 26 ^ {n ^ {2}}}$ n × n matrices. Means $\log _{2}(26^{n^{2}})\approx 4{,}7n^{2}$ ${\ displaystyle \ log _ {2} (26 ^ {n ^ {2}}) \ approx 4 {,} 7n ^ {2}}$ Is the upper bound of the key length for the Hill cipher using n × n matrices. This is only the upper bound, since not every matrix is invertible, but only such matrices can be the key. The number of reversible matrices can be calculated using the Chinese remainder theorem . A matrix is invertible modulo 26 if and only if it is invertible both modulo 2 and modulo 13 ^[8] .

The number of n × n- invertible 2 and 13 matrices is equal to the order of the linear group GL ( n , Z ₂ ) and GL ( n , Z ₁₃ ), respectively:

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

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

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

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

The number of invertible 26 modulo matrices is equal to the product of these numbers:

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

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

In addition, it will be wise to avoid too many zeros in the key matrix, since they reduce diffusion. As a result, it turns out that the effective key space of the standard Hill cipher is about $4{,}64n^{2}-1{,}7$ ${\ displaystyle 4 {,} 64n ^ {2} -1 {,} 7}$ . For Hill's 5 × 5 cipher, this will be approximately 114 bits. Obviously, exhaustive search is not the most effective attack on Hill's cipher ^[7] .

Mechanical implementation

Hill Cryptographic Machine

When working with two characters at a time, the Hill cipher does not provide any specific advantages over the Plafer cipher and even inferior to it in cryptographic strength and ease of computation on paper. As the size of the key increases, the cipher quickly becomes inaccessible to calculations on paper by a person. Hill Cipher dimension 6 was implemented mechanically. Hill and his partner received a patent for a device ( US Patent 1,845,947 ), which performed the multiplication of a 6 × 6 matrix modulo 26 using a system of gears and chains. The location of the gears (and hence the key) could not be changed for a particular device, therefore, for security reasons, triple encryption was recommended. This combination was very strong for 1929, and it shows that Hill undoubtedly understood the concepts of confusion and diffusion. However, the device was rather slow, therefore, in World War II , Hill machines were used only to encrypt a three-character code of radio signals ^[10] .

Notes

↑ Lester S. Hill. Cryptography in an Algebraic Alphabet : - 1929. - S. 7 .
↑ Chris Christensen. Lester Hill Revisited // Taylor & Francis Group, LLC: Article. - 2014 .-- S. 297 . - ISSN 0161-1194 .
↑ Lester S. Hill. Concerning Certain Linear Transformation Apparatus of Cryptography (Eng.) // The American Mathematical Monthly. - 1931. - March. - S. 135-154 .
↑ David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. - Simon and Schuster. - New York: Scribner, 1996 .-- S. 405 .-- 723 p. - ISBN 0-684-83130-9 .
↑ ¹ ² Murray Eisenberg. Hill Ciphers: A Linear Algebra Project with Mathematica .
↑ ¹ ² ³ William Stallings. Cryptography and Network Security: Principles and Practice. - 5. - Pearson Education, 2011. - S. 46-49. - ISBN 978-0-13-609704-4 .
↑ ¹ ² ³ ⁴ AVN Krishna, Dr. A. Vinaya Babu. A Modified Hill Cipher Algorithm for Encryption of Data In Data Transmission // Computer Science and Telecommunications: Georgian Electronic Scientific Journal. - 2007. - No. 3 (14) . - S. 78-83 . - ISSN 1512-1232 .
↑ ¹ ² ³ A.P. Alferov, A. Yu. Zubov, A.S. Kuzmin, A.V. Cheryomushkin. The basics of cryptography. - 2nd ed. - Helios ARV, 2002 .-- S. 115-119. - 480 p. - ISBN 5-85438-137-0 .
↑ Dorothy Elizabeth Robling Denning. Cryptography and Data Security. - London: Addison-Wesley Publishing Company, 1982. - S. 88-89. - 400 p. - ISBN 0-201-10150-5 .
↑ Friedrich L. Bauer. Decrypted Secrets: Methods and Maxims of Cryptology. - Springer, 2002 .-- S. 85. - 474 p. - ISBN 978-3-662-04738-5 .

Literature

William Stallings. Cryptography and Network Security: Principles and Practice. - Pearson, 2011 .-- P. 46-49. - 711 p. - ISBN 978-0-13-609704-4 .
David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. - Simon and Schuster, 1996.- P. 405. - 723 p. - ISBN 978-0-13-609704-4 .
Jeffrey Overbey, William Traves, Jerzy Wojdylo. On the Keyspace of the Hill Cipher. - 2005 .-- T. 29 . - P. 59–72. - DOI : 10.1080 / 0161-110591893771 .
Wade Trappe, Lawrence C. Washington. Introduction to Cryptography: With Coding Theory. - Pearson Prentice Hall, 2006 .-- P. 34-38. - 577 p. - ISBN 0-13-198199-5 .
Craig P. Bauer. Secret History: The Story of Cryptology. - CRC Press, 2013 .-- P. 227-228. - 575 p. - ISBN 978-1-4665-6187-8 .

[1] Lester S. Hill. Cryptography in an Algebraic Alphabet : - 1929. - S. 7 .

[:1-2] Chris Christensen. Lester Hill Revisited // Taylor & Francis Group, LLC: Article. - 2014 .-- S. 297 . - ISSN 0161-1194 .

[3] Lester S. Hill. Concerning Certain Linear Transformation Apparatus of Cryptography (Eng.) // The American Mathematical Monthly. - 1931. - March. - S. 135-154 .

[4] David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. - Simon and Schuster. - New York: Scribner, 1996 .-- S. 405 .-- 723 p. - ISBN 0-684-83130-9 .

[:2-5] ¹ ² Murray Eisenberg. Hill Ciphers: A Linear Algebra Project with Mathematica .

[:0-6] ¹ ² ³ William Stallings. Cryptography and Network Security: Principles and Practice. - 5. - Pearson Education, 2011. - S. 46-49. - ISBN 978-0-13-609704-4 .

[:4-7] ¹ ² ³ ⁴ AVN Krishna, Dr. A. Vinaya Babu. A Modified Hill Cipher Algorithm for Encryption of Data In Data Transmission // Computer Science and Telecommunications: Georgian Electronic Scientific Journal. - 2007. - No. 3 (14) . - S. 78-83 . - ISSN 1512-1232 .

[:3-8] ¹ ² ³ A.P. Alferov, A. Yu. Zubov, A.S. Kuzmin, A.V. Cheryomushkin. The basics of cryptography. - 2nd ed. - Helios ARV, 2002 .-- S. 115-119. - 480 p. - ISBN 5-85438-137-0 .

[9] Dorothy Elizabeth Robling Denning. Cryptography and Data Security. - London: Addison-Wesley Publishing Company, 1982. - S. 88-89. - 400 p. - ISBN 0-201-10150-5 .

[10] Friedrich L. Bauer. Decrypted Secrets: Methods and Maxims of Cryptology. - Springer, 2002 .-- S. 85. - 474 p. - ISBN 978-3-662-04738-5 .