Hill Cipher - Digraph Block Frequencies

Number Theory Level pending

A digraph cipher is a cipher in which each two block of letters of plaintext is replaced by a block of two letters of ciphertext.

Suppose that the most common digraph in English is T H TH followed closely by H E HE . Using a hill cipher system the two most common digraphs in the ciphertext message are R H RH and N I NI . We guess that R H RH and N I NI correspond to the two most common digraphs in the English text T H TH and H E HE .

Let A → 0 , B → 1 , … , Z → 25 A \rightarrow 0, B \rightarrow 1, \ldots , Z \rightarrow 25 .

If each plaintext block P j P_{j} was enciphered using a Hill digraphic cipher described by A ∗ P j ≡ C j m o d 26 , A * P_{j} \equiv C_{j} \mod 26, where each C j C_{j} is a ciphertext block, find the 2 X 2 2 \: X \: 2 matrix A A modulo 26 and find the det ⁡ ( A ) \det(A) modulo 26 .

The answer should be det ⁡ ( A ) \det(A) modulo 26.


The answer is 19.

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 8, 2017

Let A A be the 2 X 2 2 \: X \: 2 Matrix.

A ∗ [ 19 7 7 4 ] ≡ [ 17 13 7 8 ] m o d 26 \ A * \left [\begin{array}{cc|c} 19 & 7\\ 7 & 4 \\ \ \end{array} \right] \equiv \left [\begin{array}{cc|c} 17 & 13\\ 7 & 8 \\ \ \end{array} \right] \mod{26}

Let B = [ 19 7 7 4 ] m o d 26 B = \left [\begin{array}{cc|c} 19 & 7\\ 7 & 4 \\ \ \end{array} \right] \mod{26}

To find the B − 1 B^{-1} modulo 26 26 so that A ≡ [ 17 13 7 8 ] ∗ B − 1 m o d 26 A \equiv \left [\begin{array}{cc|c} 17 & 13\\ 7 & 8 \\ \ \end{array} \right] * B^{-1} \mod{26}

C = B ∣ I = [ 19 7 1 0 7 4 0 1 ] m o d 26 C = B|I = \left [\begin{array}{cc|cc} 19 & 7 & 1 & 0\\ 7 & 4 & 0 & 1 \\ \ \end{array} \right] \mod{26}

R o w 1 + R o w 2 ⟹ Row_{1} + Row_{2} \implies

C = [ 19 7 1 0 0 11 1 1 ] m o d 26 C = \left [\begin{array}{cc|cc} 19 & 7 & 1 & 0\\ 0 & 11 & 1 & 1 \\ \ \end{array} \right] \mod{26}

11 ∗ R o w 1 ⟹ 11 * Row_{1} \implies

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

To avoid confusion Note: \textbf{Note:} We wanted 19 j ≡ 1 m o d 26 ⟹ 19 j − 26 k = 1. 19 j \equiv 1 \mod 26 \implies 19 j - 26 k = 1.

Using the Euclidean algorithm repeatedly we obtain:

26 = 19 ∗ 1 + 7 , 19 = 7 ∗ 2 + 5 , 7 = 5 ∗ 1 + 2 , 5 = 2 ∗ 2 + 1 ⟹ 26 = 19 * 1 + 7, \: 19 = 7 * 2 + 5, \: 7 = 5 * 1 + 2, \: 5 = 2 * 2 + 1 \implies

1 = 5 − 2 ∗ ( 2 ) = 5 − ( 7 − 5 ) ∗ 2 = 5 ∗ 3 − 7 ∗ 2 = ( 19 − 7 ∗ ( 2 ) ) ∗ 3 − 7 ∗ 2 = 1 = 5 - 2 * (2) = 5 - (7 - 5) * 2 = 5 * 3 - 7 * 2 = (19 - 7 * (2)) * 3 - 7 * 2 =

19 ∗ ( 3 ) − 7 ∗ ( 8 ) = 19 ∗ ( 3 ) − 8 ∗ ( 26 − 19 ) = 19 ∗ ( 11 ) − 26 ∗ ( 8 ) ⟹ j ≡ 11 m o d 26 19 * (3) - 7 * (8) = 19 * (3) - 8 * (26 - 19) = 19 * (11) - 26 * (8) \implies j \equiv 11 \mod{26}

19 ∗ R o w 2 ⟹ 19 * Row_{2} \implies

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

Note: \textbf{Note:} 19 ∗ 11 ≡ 11 ∗ 19 ≡ 1 m o d 26. 19 * 11 \equiv 11 * 19 \equiv 1 \mod{26}.

R o w 2 + R o w 1 ⟹ Row_{2} + Row_{1} \implies

C = [ 1 0 4 19 0 1 19 19 ] m o d 26 C = \left [\begin{array}{cc|cc} 1 & 0 & 4 & 19\\ 0 & 1 & 19 & 19 \\ \ \end{array} \right] \mod{26}

⟹ B − 1 ≡ [ 4 19 19 19 ] m o d 26 \implies B^{-1} \equiv \left [\begin{array}{cc|c} 4 & 19 \\ 19 & 19 \\ \ \end{array} \right] \mod{26}

⟹ \implies

A ≡ [ 17 13 7 8 ] ∗ [ 4 19 19 19 ] m o d 26 ≡ [ 3 24 24 25 ] m o d 26 A \equiv \left [\begin{array}{cc|c} 17 & 13\\ 7 & 8 \\ \ \end{array} \right] * \left [\begin{array}{cc|c} 4 & 19\\ 19 & 19 \\ \ \end{array} \right] \mod{26} \equiv \left [\begin{array}{cc|c} 3 & 24\\ 24 & 25 \\ \ \end{array} \right] \mod{26}

⟹ det ⁡ ( A ) = − 501 ≡ − 7 m o d 26 ≡ 19 m o d 26. \implies \det(A) = -501 \equiv -7 \mod 26 \equiv 19 \mod 26.

∴ det ⁡ ( A ) ≡ 19 m o d 26 \therefore \boxed{\det(A) \equiv 19 \mod 26} .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...