Linear matrix cryptosystem

Question

You intercept the following message:

$VOBG!?FRWZ?RPAGYJFGWX?$

which was sent using a linear matrix cryptosystem $[x, y]^{T} \rightarrow A[x,y]^{T}$ on digraph message units (i.e. each unit consists of two symbols) in the 29-letter alphabet

$$ \begin{array}{cccc} &A&B&C&D&E&F&G&H&I&J&K&L&M&N&O \\ &0 &1 &2 &3 &4 &5 &6 &7 &8&9&10&11&12&13&14\\ \end{array} $$ $$ \begin{array}{cccc} &P&Q&R&S&T&U&V&W&X&Y&Z&\fbox{}&?&!&\\ &15&16&17&18&19&20&21&22&23&24&25&26&27&28\\ \end{array} $$

The last five letters of plaintext are the senders='s signature "$KYLIE$". Determine the inverse of the encryption matrix $A$ and decrypt the message.

Don't seem to have many class notes on this so would appreciate some help setting it up and some pointers on what steps to take. Thanks in advance :)

Answer 1

You decode the ciphertext as a set of pairs from $\mathbb{Z}_{29}$, using the given encoding. This gives:

[(21, 14), (1, 6), (28, 27), (5, 17), (22, 25), (27, 17), (15, 0), (6, 24), (9, 5), (6, 22), (23, 27)]

The last two pairs should correspond to the plain pairs

YLIE=[(24, 11), (8, 4)]

So in terms of $2\times 2$ matrices, when $E$ is the encrypting matrix we know that

$$E \begin{bmatrix}24&8\\11&4 \end{bmatrix} = \begin{bmatrix}6&23 \\ 22 & 27\end{bmatrix} $$

So that

$$E= \begin{bmatrix}6&23 \\ 22 & 27\end{bmatrix} \begin{bmatrix}24&8\\11&4 \end{bmatrix}^{-1}$$

which gives (working in the field $\mathbb{Z}_{29}$ of course):

$$E = \begin{bmatrix}4&5\\21&1 \end{bmatrix}$$ and its inverse the decryption matrix:

$$D = \begin{bmatrix}2&19\\16&8 \end{bmatrix}$$

which gives us the plain text (first in digits, and converted using the encoding) as:

SNAGS ON BARBIE? KYLIE

with the crib at the end,as it ought to be.

Answer 2

Well first you want to get the pairs of letters and put them in a matrix:

$$Y=\left[\begin{array}{cc}V & B & ! & F & W & ? & P & G & J & G & X \\ O & G & ? & R & Z & R & A & Y & F & W & ?\end{array}\right]$$

Now you know that this matrix was found using the matrix $A$ as such:

$$Y=AX$$

Where $X$ is the original matrix. If $A$ is invertible, then:

$$X=A^{-1}Y$$

This is why if you find $A^{-1}$ you'll be able to decode the text.

Now you are told that the last five characters of the original text are $KYLIE$ so your $X$ matrix looks like this:

$$X=\left[\begin{array}{cc} - & - & - & - & - & - & - & - & - & Y & I \\ - & - & - & - & - & - & - & - & K & L & E\end{array}\right]$$

Where each$-$ is the corresponding letter from the original text (which you don't know yet). This also means if you take the last $2\times3$ block of the matrices $X$ and $Y$ that:

$$\left[\begin{array}{cc} - & Y & I \\ K & L & E\end{array}\right]=A^{-1}\left[\begin{array}{cc} J & G & X \\ F & W & ?\end{array}\right]$$

Say $A^{-1}=\left[\begin{array}{cc} a & b \\ c & d\end{array}\right]$. You have:

$$\left[\begin{array}{cc} - & Y & I \\ K & L & E\end{array}\right]=\left[\begin{array}{cc} a & b \\ c & d\end{array}\right]\left[\begin{array}{cc} J & G & X \\ F & W & ?\end{array}\right]$$

Now replace the letters by their numerical values and solve the system of equations to find $a$, $b$, $c$ and $d$. Once you have them you'll have $A^{-1}$ and you'll be able to decode the text.

Note: Are you sure there is no mistake in your message or in the last five characters $KYLIE$ ? Because the results are not coherent ...

Edit:

If the message and the name are correct then there must be something wrong with the assumptions I made. Since the only assumption I made was that the matrix was a $2\times2$ matrix, this is the only thing we can change. Everything else is correct.

So maybe it's a $3\times2$ matrix, or even a $k\times2$ matrix, $k\geq1$

For example:

$$\left[\begin{array}{cc} K & Y & L & I & E\end{array}\right]=\left[\begin{array}{cc} a & b \end{array}\right]\left[\begin{array}{cc} P & G & J & G & X \\ A & Y & F & W & ?\end{array}\right]$$

Or maybe:

$$\left[\begin{array}{cc} K \\ Y \\ L \\ I \\ E \end{array}\right]=\left[\begin{array}{cc} a & b \\ c & d \\ e & f \\ g & h \\ i & j \end{array}\right]\left[\begin{array}{cc} X \\ ?\end{array}\right]$$

This last one for example is probably not a good one because you have 10 unknowns for only 5 equations. Now try some of these and let me know if you have some results. I'll try it too when I'll have some time ;)