SECURITY OF C.N.
BY: Assist.lec. AHMED K. DARAJ
2
C.N. Security lec 4 ENG. AHMED K. DARAJ
Hill cipher
The Hill cipher uses matrix multiplication, mod 26. In particular, the
encryption key is an nxn matrix with an inverse mod 26, where n is the block size.
System can be described as follows:
C = KP mod 26
For example, we will illustrate the cipher with n=2. Consider the following
key:
3 1
6 5
To encrypt a plaintext, group the plaintext in pairs: "math", for example.
Convert each letter to its numerical equivalent, mod 26, and write it in a nx1 matrix
as follows:
12
0 stands for "ma"
Now, multiply the encryption key by the plaintext and reduce mod 26 to get the
ciphertext:
3 1 12 36 10
mod 26 = mod 26 = , which corresponds to the ciphertext KU.
6 5 0 72 20
Here is the encryption of "th":
C.N. Security lec 4 ENG. AHMED K. DARAJ
3 1 19 64 12
mod 26 = mod 26 = , which corresponds to the ciphertext MT.
6 5 7 149 19
Ciphertext: KUMT
Example: consider the plaintext "paymoremoney" and use the encryption key:
The first three letters of the plaintext are represented by the vector
The ciphertext for the entire plaintext is: LNS HDL EWM TRW.
Decryption:
Decryption requires using the inverse of the matrix K. The inverse K -1 of a
matrix K is defined by the equation KK-1 = K-1K = I, where I is the matrix that is all
zeros except for ones along the main diagonal from upper left to lower right. The
inverse of a matrix does not always exist, but when it does, it satisfies the preceding
equation.
P = K-1 C mod 26
To find K-1 it needs to use a bit of math. It turns out that K-1 above can be
calculated from our key. The important things to know are inverses (mod m),
determinants of matrices and matrix adjugates.
C.N. Security lec 4 ENG. AHMED K. DARAJ
Let K be the key matrix. Let d be the determinant of K. We wish to find K -1
(the inverse of K), such that K × K-1 = I (mod 26), where I is the identity matrix. The
following formula tells us how to find K-1 given K:
where d × d-1 = 1(mod 26), and adj(K) is the adjugate matrix of K.
The determinant (d) is calculated normally for K as follows:
The determinant of a 2 × 2 matrix is defined by:
The determinant of a 3 × 3 matrix is defined by:
Determinant 1 3 5 7 9 11 15 17 19 21 23 25
Reciprocal Modulo 26 1 9 21 15 3 19 7 23 11 5 17 25
The adjugate is the transpose of its cofactor matrix, it is calculated as follows:
The adjugate of the 2×2 matrix
C.N. Security lec 4 ENG. AHMED K. DARAJ
The adjugate of the 3×3 matrix
Once K-1 is found, decryption can be performed.
C.N. Security lec 4 ENG. AHMED K. DARAJ
Example: decrypt the following ciphertext " KUMT" if you know it is encrypted
using Hill cipher by key
3 1
6 5
Solution:
d= 3*5 –(1*6) = 9
d-1 = 3
5 − 1
adj(k) =
− 6 3
15 23
k-1 =d-1 * adj(k) =
8 9
Now, we can corroborate that this is the case by decrypting the example above.
15 23 10 610 12
mod 26 = mod 26 =
8 9 20 260 0
15 23 12 617 19
mod 26 = mod 26 =
8 9 19 267 7
Plaintext: math
We can also verify this by multiplying both matrices in question together:
𝟏 𝟎
(K*K-1) mod 26 =[ ]
𝟎 𝟏
3 1 15 23 53 78 1 0
mod 26 = mod 26 =
6 5 8 9 130 183 0 1
Example of decryption 3x3 key: decrypt the following ciphertext "LNS HDL
EWM TRW " if you know it is encrypted using Hill cipher key
C.N. Security lec 4 ENG. AHMED K. DARAJ
Solution:
p=k-1*C mod 26
d= 17*(18*19-21*2) - 17*(21*19-21*2) + 5*(21*2-18*2)= -939 mod 26 =23
(23)-1=17 17 21 2
17 18 2
The adjugate of the 3×3 matrix and then transpose is 5 21 19
300 −313 267 𝟒 𝟗 𝟏𝟓
([−357 313 −252] ∗ 17 ) mod 26 =[𝟏𝟓 𝟏𝟕 𝟔 ] this is K-1
6 0 −51 𝟐𝟒 𝟎 𝟏𝟕
𝑝1 4 9 15 11
[𝑝2] = [15 17 6 ] *[13] 𝑚𝑜𝑑 26
𝑝3 24 0 17 18
p1= (4*11+9*13+15*18) mod 26 =15 ➔ p
p2= (15*11+17*13+6*18) mod 26 =0 ➔ a
p1= (24*11+0*13+17*18) mod 26 =24 ➔ y
And repeat the same function to the next three letters until end the ciphertext
Then plaintext is pay mor emo ney.
Example: Suppose that the plaintext "friday" is encrypted using a 2 x 2 Hill cipher
to
yield the ciphertext PQCFKU. Find the key?
Solution:
C.N. Security lec 4 ENG. AHMED K. DARAJ
Using the first two plaintext-ciphertext pairs, we have
The inverse of matrix can be computed:
So:
This result is verified by testing the remaining plaintext-ciphertext pair.
