Hill cipher

Number Theory Level 4

Given the matrix A = ∣ 3 1 3 2 ∣ m o d 26 A= \begin{vmatrix}{3} && {1} \\ {3} && {2}\end{vmatrix} \bmod{26} , use a Hill cipher to decipher the message V V I X H U I E Y C R I VVIXHUIEYCRI using modulo 26, where A → 0 , B → 1 , … , Z → 25 , A \rightarrow 0, B \rightarrow 1, \ldots , Z \rightarrow 25, and enter the result as a string of integers.

What does the deciphered message state?


The answer is 7015152413422244017.

Rocco Dalto by Rocco Dalto , 67, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Rocco Dalto
Jan 1, 2017

Note: det ⁡ ( A ) = 3 \: \det(A) = 3 and gcd ⁡ ( 3 , 26 ) = 1 \gcd(3,26) = 1 , so for each block X j X_{j} the system A X j = B j m o d 26 A X_{j} = B_{j} \bmod{26} has a unique solution, where ( 1 < = j < = 6 ) (1 <= j <= 6) .

Using six blocks for V V I X H U I E Y C R I VVIXHUIEYCRI we obtain:

21 21 21\: 21

8 23 8 \: 23

7 20 7 \: 20

8 4 8 \: 4

24 2 24 \: 2

17 8 17 \: 8

A ∗ X j = B j ⟹ X j = A − 1 ∗ B j A * X_{j} = B_{j} \implies X_{j} = A^{-1} * B_{j}

Using the A − 1 : A^{-1} \textbf{:}

C = A ∣ I = [ 3 1 1 0 3 2 0 1 ] m o d 26 C = A|I = \left [\begin{array}{cc|cc} 3 & 1 & 1 & 0 \\ 3 & 2 & 0 & 1 \\ \ \end{array} \right] \bmod{26}

Using the row operations: 9 ∗ R o w 1 9 * Row_{1} and 23 ∗ R o w 1 + R o w 2 ⟹ 23 * Row_{1} + Row_{2} \implies

C = [ 1 9 9 0 0 1 25 1 ] m o d 26 C = \left [\begin{array}{cc|cc} 1 & 9 & 9 & 0 \\ 0 & 1 & 25 & 1 \\ \ \end{array} \right] \bmod{26}

Using the row operation: 17 ∗ R o w 2 + R o w 1 ⟹ 17 * Row_{2} + Row_{1} \implies

C = [ 1 0 18 17 0 1 25 1 ] m o d 26 C = \left [\begin{array}{cc|cc} 1 & 0 & 18 & 17\\ 0 & 1 & 25 & 1 \\ \ \end{array} \right] \bmod{26}

⟹ \implies

A − 1 = [ 18 17 25 1 ] m o d 26 A^{-1} = \left [\begin{array}{cc|c} 18 & 17\\ 25 & 1 \\ \ \end{array} \right] \bmod{26}

Note: A ∗ A − 1 = I A * A^{-1} = I

Deciphering the first block [ 21 21 ] : \left [\begin{array}{cc|c} 21 \\ 21 \\ \ \end{array} \right] \textbf{:}

X 1 = A − 1 ∗ B 1 m o d 26 = [ 18 17 25 1 ] ∗ [ 21 21 ] m o d 26 = [ 7 0 ] m o d 26 X_{1} = A^{-1} * B_{1} \bmod{26} = \left [\begin{array}{cc|c} 18 & 17\\ 25 & 1 \\ \ \end{array} \right] * \left [\begin{array}{cc|c} 21 \\ 21 \\ \ \end{array} \right] \bmod{26} = \left [\begin{array}{cc|c} 7 \\ 0 \\ \ \end{array} \right] \bmod{26} :

Deciphering the second block [ 8 23 ] : \left [\begin{array}{cc|c} 8 \\ 23 \\ \ \end{array} \right] \textbf{:}

X 2 = A − 1 ∗ B 2 m o d 26 = [ 18 17 25 1 ] ∗ [ 8 23 ] m o d 26 = [ 15 15 ] m o d 26 X_{2} = A^{-1} * B_{2} \bmod{26} = \left [\begin{array}{cc|c} 18 & 17\\ 25 & 1 \\ \ \end{array} \right] * \left [\begin{array}{cc|c} 8 \\ 23 \\ \ \end{array} \right] \bmod{26} = \left [\begin{array}{cc|c} 15 \\ 15 \\ \ \end{array} \right] \bmod{26}

Repeat the same procedure for the remaining four blocks.

Our deciphered blocks are:

7 0 7 \: 0

15 15 15 \: 15

24 13 24 \: 13

4 22 4 \: 22

24 4 24 \: 4

0 17 0 \: 17

Our plain text message is:

H A P P Y N E W Y E A R HAPPYNEWYEAR

As a string of integers we have: 7015152413422244017 7015152413422244017 .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

In the question, can you clarify how to "use the matrix" to decipher the message? It is not immediately obvious that we're supposed to do A X j = B ) j A X_j = B)j .

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

I had given the title as Hill cipher so that they can google a Hill cipher which is an example of a block cipher.

I had this discussion with someone else on a second problem I had done using a hill cipher, and they suggested that I just give the title of the topic(Hill cipher) and let them google it.

I can mention that it's a Hill cipher and the square matrix A A is the enciphering matrix, where ( det ⁡ ( A ) , 26 ) = 1 , (\det({A}),26) = 1, and it can be deciphered by obtaining the A − 1 A^{-1} and calculating X j = A − 1 ∗ B j X_{j} = A^{-1} * B_{j} for each integer j , j , which in this case is ( 1 < = j < = 6 ) . (1 <= j <= 6). I can also give more information as well.

For instance, I can state:

For each block B j = [ b j 1 b j 2 ] B_{j} = \left[ \begin{array}{ccc} b_{j1}\\ b_{j2}\\ \\ \end{array} \right] we solve the system A ∗ X j = B j m o d 26 A * X_{j} = B_{j} \mod 26 for X j = A − 1 ∗ B j m o d 26 X_{j} = A^{-1} * B_{j} \mod 26 . Each X j X_{j} is a deciphered block. Last, just convert each X j X_{j} block back to it's plain text message. The matrix is the key to deciphering the enciphered text. For this problem just enter the result as a string of integers, not the deciphered message.

This might be too much information. It's basically telling someone exactly what to do.

Let me know what you prefer.

I also intended to do other block ciphers such as a Knapsack cipher and a cipher involving the Chinese Remainder theorem. Should I do these ciphers?

I am presently doing a problem involving the Chinese Remainder theorem which I will post shortly, then I would like to do an application of the Chinese Remainder Theorem involving a cipher.

For the present problem I am working on I provide two methods in the solution. One method is using the Chinese Remainder theorem and the other is an algebraic approach.

Rocco Dalto - 4 years, 5 months ago

Log in to reply

Please mention that it is a Hill Cipher in the problem, since that is crucial in solving it. There is no need to explain how to set up / solve A X i = B i A X_i = B_i .

I would love to see those Cipher problems. It would be cool if we could turn words into other words, like say "Merry -> Happy".

The problem should be self-contained. E.g. We mention that a problem is on caesar cipher , to indicate what range space to search.

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

@Calvin Lin – I mentioned it in the title of the problem, but I'll also mention it in the problem. It' s done, I mentioned it in the problem.

Rocco Dalto - 4 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...