Application to Hill Cipher¶
This cipher was constructed in 1929 by a mathematician Lester Hill. To describe it concisely, it will be useful to introduce two basic notions from cryptography:
Definition.
We also assign to each letter of an alphabet a numerical value:
This alphabet can be, of course, extended by other symbols.
One of the parameters in Hill’s encryption algorithm is a choice of the length \(\, m\,\) of a plaintext which will be encrypted in each step. The algorithm treats a plaintext consisting of \(\, m\,\) letters as a vector and multiplies it on the right by a certain \(\, m\times m\,\) matrix \(\, K\,\) with entries in \(\, Z\,\) whose determinant is not divisible neither by \(2\) nor by \(13\) (later it will be clear why). This matrix is called the secret key of the algorithm.
It will be easiest to describe the procedures of Hill’s algorithm on an example.
Example¶
\(\,\) Let \(\, m=3\,\) and \(\, K =\left[\begin{array}{rrr} 18 & 25 & 13 \\ 11 & 7 & 19 \\ 21 & 18 & 23 \end{array}\right]\,.\) We want to encrypt the message \(\ {\tt ATTACK\ TOMORROW}\) .
First we remove the spaces and write the message in terms of numbers. Next, because \(m=3,\) we divide it into vectors of size \(3:\)
If the number of letters in the plaintext is not divisible by \(m,\) we complete the last vector with arbitrary numbers, e.g. with \(0\) as above.
If the plaintext is long, doing the above substitution by hand may be time consumming and lead to mistakes. It may be better to use Sage for this purpose:
sage: S=AlphabeticStrings() # provides an alphabet from A to Z
sage: A=list(S.alphabet()) # the above alphabet in form of a list
sage: Plt="ATTACKTOMORROW" # plaintext has to be written in capital letters and without spaces
sage: print A, "\n", list(Plt), "\n", len(Plt)
['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']
['A', 'T', 'T', 'A', 'C', 'K', 'T', 'O', 'M', 'O', 'R', 'R', 'O', 'W'] # Plt in form of a list
14 # length of Plt
# Now we create a list of numerical values corresponding to the letters in Plt
sage: P=list() # P is an empty list of an unspecified length
sage: for i in range(len(Plt)):
sage: for j in range(S.ngens()): # S.ngens() returns the number of characters in S
sage: if Plt[i]==A[j]: P.insert(i,j) # if the i-th element of Plt is equal to the j-th element of A, insert at the i-th place of P the number j
sage: else: j=j+1
sage: print P
[0, 19, 19, 0, 2, 10, 19, 14, 12, 14, 17, 17, 14, 22]
# It remains to include the missing numbers and divide P into sequences of length m=3
sage: m=3
sage: r=len(P) % m # remainder after division of len(P) by m
sage: R=list(0 for i in range(m-r)) # a list of m-r zeros
sage: if r>0: P.extend(R) # if r>0, we extend P by the list R
sage: Pn=list()
sage: for i in range(ceil(len(P)/3)): # ceil(x) returns smallest integer greater or equal x
sage: k=3*i
sage: Pn.insert(i,P[k:k+3])
sage: print P, "\n", Pn, "\n", Pn[0], "\n", Pn[1][1]
[0, 19, 19, 0, 2, 10, 19, 14, 12, 14, 17, 17, 14, 22, 0]
[[0, 19, 19], [0, 2, 10], [19, 14, 12], [14, 17, 17], [14, 22, 0]]
[0, 19, 19]
2
Now we multiply the above vectors by the matrix \(\, K\,\) on the right:
Or in Sage:
sage: K=Matrix([[18,25,13],[11,7,19],[21,18,23]])
sage: Cn=list(vector(Pn[i])*K for i in range(len(Pn))) # in order to multiply Pn[i] by a matrix K, we must change the form of Pn[i] from a list to a vector
sage: print Cn
[(608, 475, 798), (232, 194, 268), (748, 789, 789), (796, 775, 896), (494, 504, 600)]
To interpret the above vectors again as a text we have to replace each entry with its remainder after division by \(26,\) and read off the unique letter it corresponds to:
Or better in Sage:
sage: C=list(Cn[i] % 26 for i in range(len(Pn)))
sage: print C, "\n", C[3], "\n", C[3][0]
[(10, 7, 18), (24, 12, 8), (20, 9, 9), (16, 21, 12), (0, 10, 20)]
(16, 21, 12)
16
sage: Cit=list()
sage: for i in range(len(Pn)):
sage: for k in range(3):
sage: Cit.insert(3*i+k,A[C[i][k]])
sage: print Cit
['K', 'H', 'S', 'Y', 'M', 'I', 'U', 'J', 'J', 'Q', 'V', 'M', 'A', 'K', 'C']
In this way we obtain the ciphertext \(\ {\tt KHSYMIUJJQVMAKC}\) (where the last letter \({\tt C}\) can be omitted as it corresponds to the artificially added number).
Note that if our alphabet consisted of \(\ N\neq 26\ \) letters, we would have to adjust the above computations accordingly: we would have to replace each entry with its remainder after division by \(N.\) This approach also explains why we enumerated the letters starting with \(0:\) the remainder is always one of the numbers \(\, 0, 1, 2, \ldots, 25.\)
In order to decrypt this text and obtain the plaintext, a recipient of the message has to write it numerically (and so know the alphabet that was used), know the inverse of the matrix \(\, K\,\) (and so also its size) and regroup the ciphertext appropriately - in our case to vectors of length \(3.\)
In our example
The reader will immediately notice that the product \(\ KK^{-1}\ \) is not equal to the usual identity matrix, but rather
However, all the off-diagonal entries are divisible by \(26,\) and the ones on the diagonal are multiplicities of \(26\) plus \(1.\) Hence, if we replace each entry with its remainder after division by \(26,\) we obtain the identity matrix \(\ \left[\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\ \). We explain this situation in the next section. First let us see that the matrix \(\ K^{-1}\ \) proposed above allows us to decrypt the ciphertext. We follow exactly the same steps as in the encryption process.
For example, \(\ {\tt K \ H \ S }\ \) corresponds to a vector \(\ \left[\begin{array}{rrr} 10 & 7 & 18 \end{array}\right] ,\,\) and
Now because \(\,\left[\begin{array}{rrr} 468 & 279 & 591 \end{array}\right] = \left[\begin{array}{rrr} 26\cdot 18 & 26\cdot 10 +19 & 26\cdot 22 +19 \end{array}\right]\,,\) the vector \(\,\left[\begin{array}{rrr} 468 & 279 & 591 \end{array}\right]\,\) corresponds to \(\,\left[\begin{array}{rrr} 0 & 19 & 19 \end{array}\right] ,\,\) and thus to \(\ {\tt A \ T \ T }\ \) as expected.
Modular arithmetic¶
Because we chose to use an alphabet that consists of \(26\) letters (and we enumerated them by \(0, 1, 2, \ldots, 25\)), the result of our computations has to be a number from this range. This is the reason why we take remainders after division by \(26\). In fact, to make the computations easier and faster we can take the remainder after division by \(26\) every time we add or multiply two numbers. We call such operations in short an \(\,\) arithmetic modulo \(\, 26\,\) and we say that we take a \(\,\) remainder modulo \(\ 26\ \); the number \(26\) is in this case called the \(\,\) modulus. \(\,\) Further, as long as numbers \(a\in Z\) and \(26\) do not have common divisors, it is possible to \(\,\) divide \(\,\) by \(a\) modulo \(26\): by definition, \(\ \frac1a\ \) (or \(a^{-1}\)) is taken to be such a number from \(1, 2, \ldots, 25\ \) that \(a\) times this number gives \(1\) modulo \(26\). \(\,\) For example,
These operations can be made easily in Sage:
In fact,
Proposition.
For any natural number \(N>1\), the set \(\ \left\{ 0,1,2,\ldots ,N-1\right\}\ \) together with addition and multiplication modulo \(N\) is a commutative ring with identity, we denote it by \(\ \mathbb{Z}_N = (Z_N,\ +_N\,,\ \cdot_N\,)\ \) and call a ring of integers modulo \(N\). It is a field if and only if \(N\) is a prime number.
The ring of integers modulo \(N\) is implemented in Sage under the name Integers(N). If we define a matrix over this ring, all the operations will be naturally made over \(\ Z_N\,\). \(\,\) For example,
sage: N=26
sage: R=Integers(N)
sage: K=Matrix(R, [[18,25,13],[11,7,19],[21,18,23]])
sage: print K.parent(), "\n", det(K), "\n", K.inverse()
Full MatrixSpace of 3 by 3 dense matrices over Ring of integers modulo 26
15
[ 7 5 10]
[ 8 25 11]
[19 3 23]
Note
We saw in Theorem 7 from the previous section that a matrix defined over a field \(\,\) is invertible if and only if its determinant is not equal to zero. In general, a matrix defined over a ring \(\ R\) is invertible if and only if its determinant is invertible over \(R\). This fact may be proven along the same lines as the aforementioned theorem (try it!). The invertible elements in \(\ R=\mathbb{Z}_N\ \) are exactly those numbers whose greatest common divisor with \(N\) is equal to \(1\).
Security¶
Security of Hill’s cipher bases on the fact that a given letter of the alphabet may be encrypted in a few ways. Already in the above example we saw that \(\ {\tt T}\ \) was encrypted as \(\ {\tt H},\ {\tt S},\ {\tt U}\,,\) while \(\ {\tt J}\ \) in the ciphertext represented both \(\ {\tt O}\ \) and \(\ {\tt M}\) . In this way the algorithm masks frequency distribution of letters in a text, and thus prevents usage of frequency analysis; in fact, the bigger the secret key, the better masking properties.
However, if one knows sufficiently many pairs (plaintext, ciphertext), it is possible to find the secret key which was used. Assume that somehow you know that the alphabet consists of \(26\) letters, the secret key matrix \(K\) is of size \(m,\) and the ciphertexts \(\ C_1,\ldots , C_m\ \) were obtained from the plaintexts \(\ P_1,\ldots , P_m\ \) via Hill’s encryption algorithm, that is:
(Note that if one knows \(\ C_i\ \) and \(\ K^{-1},\ \) then the procedure described in the example above always returns \(\ P_i\ \):
We can write the relations (1) in a form of matrix equation
where \(\ C,P\in M_m(Z_{26})\ \) and their rows are formed from \(\ C_i\) ‘s and \(\ P_i\) ‘s respectively. If the matrix \(\ P\ \) is invertible (over the ring \(\ Z_{26}\ \)), then we find that \(\ K=P^{-1}C\, (\text{mod}\, 26).\ \) If \(\ P\ \) is not invertible, one has to find more pairs (plaintext, ciphertext) and replace the ones that are linearly dependent with others.
Example.
Assume that we encrypted the text \(\ {\tt NOTHINGNEW}\ \) via Hill’s cipher with a secret key of size \(2\) and obtained ciphertext \(\ {\tt DFTMGRYDEI}.\) The pairs \(\ ({\tt NO}, {\tt DF}),\, ({\tt TH}, {\tt TM})\ \) correspond to pairs of vectors \(\ ([13\; 14],\; [3\; 5])\;, ([19\; 7],\; [19\; 12])\,.\) Hence, we obtain a matrix equation
We compute:
sage: N=26
sage: R=Integers(N)
sage: C=Matrix(R, [[3,5],[19,12]])
sage: P=Matrix(R, [[13,14],[19,7]])
sage: print "det(P) =", det(P),"\n", "K = P^{-1}C =","\n", P.inverse()*C
det(P) = 7
K = P^{-1}C =
[17 7]
[16 5]
The result may be verified by checking remaining pairs (plaintext, ciphertext). Do it yourself in the cell below using the commands presented in this section.
Exercise.
You intercepted the message that was encrypted via Hill’s cipher with the key matrix of size \(3.\) Most probably the plaintext starts with \(\ {\tt TOGENERAL}\ \) . Find the key matrix and decrypt the rest of the ciphertext:
\(\ {\tt AVQLPGSNJJLYMLQYCTQCUHIQZNTRDJPTPSAJOKDKXTSGZGFPIUANHFDNIHROMZEKKFUMNZDIACYVZHMSSKJRQEW }\) .
