CSC 440, Winter 2021, Hill cipher notes
A Hill cipher example
We are given the encryption matrix and plaintext:
[5 11] , 𝑠𝑢𝑚𝑚𝑒𝑟 (18, 20,12,12,4,17) 47
We encrypt each pair of plaintext letters. We’ll start with su:
[5 11][18]≡[5⋅18+11⋅20]≡[310]≡[24] (𝑚𝑜𝑑26) 4 7 20 4⋅18+7⋅20 212 4
This translates back to the letters YE. Continuing with mm and then er, we get the ciphertext YEKCZF.
We are performing left matrix-vector multiplication here:
[𝑎 𝑏][𝑥]=[𝑎𝑥+𝑏𝑦] 𝑐𝑑𝑦 𝑐𝑥+𝑑𝑦
The idea is to calculate the dot products of each row of the matrix with the single column of the vector.
This can be generalized to nxn matrices and vectors of length n. To decrypt, we will need to calculate the inverse of the encryption
matrix mod 26.
Left vs right matrix multiplication
I used left multiplication above. This is how I have most often seen the Hill cipher presented (e.g., in Wikipedia and in the 2nd edition of
CSC 440, Winter 2021, Hill cipher notes
the textbook). The 3rd edition uses right multiplication. Everything still works but one ends up with different ciphertexts.
I will stick with left multiplication in what follows and in the homework.
CSC 440, Winter 2021, Hill cipher notes
Calculate the modular inverse of a 2×2 matrix The usual integer/rational number inverse
Given a 2×2 matrix:
𝑀=[𝑎 𝑏] 𝑐𝑑
where 𝑎, 𝑏, 𝑐, 𝑑 are integers, the determinant is defined as: det 𝑀 = 𝑎𝑑 − 𝑏𝑐
The identity matrix, which is similar to the identity value for normal multiplication (1), is:
[1 0] 01
So, just as multiplying a value and its multiplicative inverse yields 1, multiplying a matrix and its inverse yields the identity matrix:
𝑀𝑀−1=[1 0] 01
Linear algebra shows us that the inverse of a 2×2 matrix is the 2×2 matrix:
𝑀−1 = (det 𝑀)−1 [ 𝑑 −𝑏] −𝑐 𝑎
CSC 440, Winter 2021, Hill cipher notes
But not every matrix has an inverse. When the determinant is 0 the matrix doesn’t have an inverse because 0 does not a multiplicative inverse.
Modular inverse
Now let’s look at matrices 𝑚𝑜𝑑 𝑛. Recall that 𝑚𝑜𝑑 𝑛, a value 𝑎 does not have an inverse iff gcd(𝑎, 𝑛) > 1. So a matrix has an inverse iff gcd(det 𝑀, 𝑛) = 1.
Here are some examples 𝑚𝑜𝑑 26. 𝑀0=[7 5]
11 6
det𝑀0 =7⋅6−5⋅11≡−13≡13(𝑚𝑜𝑑26)
Because gcd(13,26) = 13, the determinant of 𝑀0 does not have a multiplicative inverse. Don’t use this matrix for the Hill system!
However, this one does have an invertible determinant:
𝑀 =[5 11]
1
47
det𝑀 =5⋅7−11⋅4≡−9≡17(𝑚𝑜𝑑26) 1
(det𝑀 )−1 = 17−1 ≡ 23 (𝑚𝑜𝑑 26) 1
So the inverse of 𝑀−1 is: 1
CSC 440, Winter 2021, Hill cipher notes
Let’s check correctness:
𝑀−1=23⋅[7 −11]
≡23⋅[7 15] 22 5
≡ [161 345] 506 115
≡[5 7] (𝑚𝑜𝑑26) 12 11
1
−4 5
𝑀𝑀−1≡[5 11][5 7]
4 7 12 11
≡[5⋅5+11⋅12 5⋅7+11⋅11] 4⋅5+7⋅12 4⋅7+7⋅11
≡ [157 156] 104 105
≡ [1 0] (𝑚𝑜𝑑 26) 01
11
CSC 440, Winter 2021, Hill cipher notes
Cryptanalysis of Hill: Known plaintext attack
Recall that a known plaintext attack means that Eve knows the plaintext corresponding to a portion of the ciphertext. For example, continuing with 2×2 matrices for the Hill cipher, assume she knows that the plaintext 𝑥𝑜𝑥1𝑥2𝑥3 is encrypted by 𝑦0𝑦1𝑦2𝑦3.
She wants to find the encryption matrix [𝑎 𝑏]. 𝑐𝑑
This means that she knows:
[𝑎 𝑏] [𝑥0] ≡ [𝑦0] 𝑚𝑜𝑑 26 𝑐𝑑𝑥1 𝑦1
[𝑎 𝑏] [𝑥2] ≡ [𝑦2] 𝑚𝑜𝑑 26 𝑐𝑑𝑥3 𝑦3
Using the definition of matrix/vector multiplication, we get these four equivalences:
𝑎𝑥0 + 𝑏𝑥1 ≡ 𝑦0 (𝑚𝑜𝑑 26) 𝑎𝑥2 + 𝑏𝑥3 ≡ 𝑦2 (𝑚𝑜𝑑 26)
𝑐𝑥0 + 𝑑𝑥1 ≡ 𝑦1 (𝑚𝑜𝑑 26) 𝑐𝑥2 + 𝑑𝑥3 ≡ 𝑦3 (𝑚𝑜𝑑 26)
We can see that we have two pairs of linear equivalences, each with two unknowns. Using the method learned (perhaps long ago) for solving linear equations works here to find 𝑎, 𝑏, 𝑐, 𝑑.
CSC 440, Winter 2021, Hill cipher notes
To get started, multiply the first equivalence by −𝑥2 and the
second by 𝑥0:
−𝑎𝑥0𝑥2 − 𝑏𝑥1𝑥2 ≡ −𝑦0𝑥2 (𝑚𝑜𝑑 26)
𝑎𝑥0𝑥2 + 𝑏𝑥0𝑥3 ≡ 𝑦2𝑥0 (𝑚𝑜𝑑 26)
Adding the left and right sides together yields a single equivalence:
𝑏(𝑥0𝑥3 − 𝑥1𝑥2) ≡ (𝑦2𝑥0 − 𝑦0𝑥2) (𝑚𝑜𝑑 26)
Multiply both sides by the multiplicative inverse of (𝑥0𝑥3 − 𝑥1𝑥2) and that gets a value for 𝑏. Plug that back in to one of the pairs above to get 𝑎.
Generalizing to nxn matrices, Eve needs n blocks of plaintext each containing n characters. But she may need more, as explained next.
The only stumbling block in the method is if it turns out
that (𝑥0𝑥3 − 𝑥1𝑥2) does not have multiplicative inverse. In that case, Eve would have to have more plaintext/ciphertext matches but if she has enough such “cribs” then, with high probability, she’ll be able to find the values in the encryption matrix.
CSC 440, Winter 2021, Hill cipher notes
Linearity is the weakness!
This linearity of the Hill system is its chief weakness. This is yet another vulnerability to be on the watch for as we examine other (and more recent) cryptosystems.