0

We assume that the message $$!IWGVIEX!ZRADRYD$$ has been encrypted using Hill Cipher and with the correspondence $A=0,...,Z=25,\ \_=26, ? =27,!=28$. We know that the last five letters of plaintext are sender's signature $MARIA$.

We want to find the deciphering matrix and read the message.

My attempt: At first we suppose that $m=2,\ P=C=\Bbb{Z}_{29}$ and $K=\mathrm{GL_2}(\Bbb{Z_{29}})$. By the hypothesis, we know that $MARIA \leftrightarrow ADRYD \iff (12,0,17,8,0)\leftrightarrow (0,3,17,24,17)$.

This implies that, if we assume that the key matrix is $A\in \mathrm{GL_2}(\Bbb{Z_{29}})$, the diciphering function is $$ E_A: (\Bbb{Z}_{29})^2 \longrightarrow (\Bbb{Z}_{29})^2,\\ (12,0)\mapsto (12,0)\cdot A =(0,3), \\ (17,8) \mapsto (17,8)\cdot A=(17,24) $$ so, $ \begin{pmatrix} 12 & 0 \\ 17 & 8 \end{pmatrix} \cdot A = \begin{pmatrix} 0 & 3 \\ 17 & 24 \end{pmatrix} $. We define $B:=\begin{pmatrix} 12 & 0 \\ 17 & 8 \end{pmatrix}$. Then, $\det B=9 \in U_{29} \iff B \in \mathrm{GL}(\Bbb{Z_{29}})$. Also, $\mathrm{adj} B= \begin{pmatrix} 8 & 0 \\ 12 & 12 \end{pmatrix} $ and $9^{-1}=13 \in U_{29}$. So, $$B^{-1}=13 \begin{pmatrix} 8 & 0 \\ 12 & 12 \end{pmatrix} = \begin{pmatrix} 9 & 0 \\ 11 & 11 \end{pmatrix}.$$ And from this, $$A = \begin{pmatrix} 9 & 0 \\ 11 & 11 \end{pmatrix} \cdot \begin{pmatrix} 0 & 3 \\ 17 & 24 \end{pmatrix} = \begin{pmatrix} 0 & 27 \\ 13 & 7 \end{pmatrix} \in \mathrm{GL}(\Bbb{Z_{29}}). $$

But if we use this matrix as a key and encipher the word $MARIA$, we will not take the word $ADRYD$ that we expect, so something is wrong. Is this method correct? Do I miss something?

Thank you.

Henno Brandsma
  • 242,131
Chris
  • 2,763
  • Any help please? – Chris Jun 11 '18 at 17:09
  • $13\times 8\not\equiv 9\pmod{29}$ – Peter Košinár Jun 11 '18 at 17:10
  • 1
    Also, you might need to be careful about position of your known plaintext within the message. Remember, you are encrypting/decrypting pairs of characters, so you are looking at ciphertext split as "!I WG VI EX !Z RA DR YD" and the plaintext pairs corresponding to last two pairs would be "AR" and "IA". – Peter Košinár Jun 11 '18 at 17:18
  • @PeterKošinár Thank you for your comment. Oh God. Did I take a non-existing pair? – Chris Jun 11 '18 at 17:21
  • 1
    There are two separate issues: First is a mistake in calculation of $B^{-1}$ which caused MARIA not to be encrypted as ADRYD, even if considered on its own. But even with the corrected matrix, you would still get nonsensical text if you tried to decrypt the full message - since the pairs would not be aligned with those you used to find the matrix in the first place. – Peter Košinár Jun 11 '18 at 17:40
  • @PeterKošinár You are right, everything works fine if we split the text right! Thank you very much! – Chris Jun 11 '18 at 18:50

1 Answers1

1

You have to split the ciphertext in pairs, and your ciphertext corresponds to the following pairs of elements of $\mathbb{Z}_{29}$:

(28, 8), (22, 6), (21, 8), (4, 23), (28, 25), (17, 0), (3, 17), (24, 3)

And the last 4 letters of your assumed plain text are "ARIA" (two pairs) that equal (0, 17), (8, 0) We cannot use the M, as then we'd have to guess the letter before M too, as encryption is done by pairs. But 4 unknowns with 4 equations should suffice. So if we denote by $E$ the $2 \times 2$ encryption matrix we have that these 2 pairs must become the final two pairs of the cipher text, or written out as a matrix equation $EP = C$ where $P$ is a matrix of plain texts, and $C$ the corresponding ciphertexts:

$$E \cdot \begin{bmatrix} 0 & 8 \\ 17 & 0 \end{bmatrix} = \begin{bmatrix} 3 & 24\\ 17 & 3 \end{bmatrix}$$

As the $P$ matrix is invertible, we compute $E$ as $CP^{-1}$ (using mod $29$ arithmetic and the easy formula for inverses of $2 \times 2$ matrices). Then compute $D$ as $E^{-1}$ and you'll find a nice plaintext indeed ending in ARIA; I checked and it works out.

Henno Brandsma
  • 242,131