Hill cipher
This system is based on the linear algebra and is very important in the history of cryptography. It was Invented by Lester S. Hill in 1929, and was the first cryptographic system polyalphabetic working with more than three symbols simultaneously
This system is polyalphabetic because it may be that a same character in a message to be sent is encrypted in two different characters in the encrypted message
I would like to start with a very simple system that can be explained mathematically speaking using modular arithmetic. Throughout this article I will use for simplicity the alphabet in standard English 26-letter:
\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ 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 \\ \end{pmatrix}
Choose an integer d that determines blocks of d elements, which will be treated as a vector of d dimensions. Randomly, we choose a matrix of d × d elements which will be the key to be used. The elements of the matrix d × d will be integers between 0 and 25, in addition the matrix M must be invertible in \mathbb{Z}^n_{26}
For the encryption, the text is divided into blocks of d elements which are multiplied by the matrix d × d. As well M\cdot P_i \equiv C \pmod{26} where we have assigned the number 0, B 1, ... , Z to 25, and \pmod{26} indicates that we should take the remainder of dividing by 26 (in C language we use the % operator ) M is the matrix d × d, C is the ciphertext and P the original
Example of Hill cipher
CODIGO we break the structure into blocks of 3 characters each (in this case d = 3), eliminating punctuation marks, if any, and we get the numerical equivalents of these letters
P_1=COD=\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}, P_2=IGO=\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}
We chose M=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix} as the keys array
Before applying the encryption, we must ensure that M is invertible \mod{26}. There is a relatively simple way to find this out through the calculation of the determinant. If the determinant of the matrix is 0, or has common factors with the modulus (in the case of 26 the factors are 2 and 13), then the array cannot be used. To be 2 one of the factors of 26 many arrays may not be used (will not serve them all in that its determinant is 0, a multiple of 2 or a multiple of 13)
\det(M) = \begin{vmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{vmatrix} = 5 \cdot(23 \cdot 13 - 3 \cdot 11) - 17 \cdot (9 \cdot 13 - 3 \cdot 2) + 20 \cdot (9 \cdot 11 - 23 \cdot 2) =
= 1215 - 1734 + 1060 = 503
Now we check \pmod{26}:
503 = 9\pmod{26}
The matrix A is invertible in \mod{26}because 26 and 9 are coprimos
We calculate the first block:
M\cdot P_1=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = \begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix}
\begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix} = \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix}\pmod{26}
\begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = WLP
So the encrypted message block one is:
C_1=WLP
We calculate the second block:
M\cdot P_2=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = \begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix}
\begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix} = \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix}\pmod{26}
\begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = GSE
So the encrypted message block one is:
C_2=GSE
We add both messages encrypted to obtain the encrypted message C:
C=WLPGSE
We can decipher the C above, the method is the same, but we need to calculate M^{-1}. To do this we calculate from this formula:
M^{-1}=C^t\cdot (\det(M))^{-1}
Where C^t is the matrix of cofactors of M transposed and (\det(M))^{-1} should be done as \mod{26}, which in this case is 3 since:
9\pmod{26} \cdot 3\pmod{26}=27 \pmod{26}=1 \pmod{26}
We calculate the cofactors of M
C_{1 1}= + \begin{vmatrix} 23& 3 \\ 11& 13 \end{vmatrix} C_{1 2}= - \begin{vmatrix} 9& 3 \\ 2& 13 \end{vmatrix} C_{1 3}= + \begin{vmatrix} 9& 23 \\ 2& 11 \end{vmatrix}
C_{2 1}= - \begin{vmatrix} 17& 20 \\ 11& 13 \end{vmatrix} C_{2 2}= + \begin{vmatrix} 5& 20 \\ 2& 13 \end{vmatrix} C_{2 3}= - \begin{vmatrix} 5& 17 \\ 2& 11 \end{vmatrix}
C_{3 1}= + \begin{vmatrix} 17& 20 \\ 23& 3 \end{vmatrix} C_{3 2}= - \begin{vmatrix} 5& 20 \\ 9& 3 \end{vmatrix} C_{3 3}= + \begin{vmatrix} 5& 17 \\ 9& 23 \end{vmatrix}
C=\begin{pmatrix} 266& -111& 53 \\ -1& 25& -21& \\ -409& 165& -38 \end{pmatrix} C^t= \begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix}
Now we apply the formula in reverse:
M^{-1}=C^t\cdot (\det(M))^{-1}=\begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix} \cdot 3=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix}
M^{-1}\pmod{26}=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix} \pmod{26} =\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1 \\ 3& 15& 16 \end{pmatrix}
We calculate the first block:
M\cdot P_1=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = \begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix}
\begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix} = \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}\pmod{26}
\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = COD
So the encrypted message block one is:
P_1=COD
We calculate the second block:
M\cdot P_2=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = \begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix}
\begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix} = \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}\pmod{26}
\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = IGO
So the encrypted message block one is:
P_2=IGO
We add both messages encrypted to obtain the encrypted message C: