Known-plaintext attack on two-dimensional affine cipher

Question

Problem:

We have a two-dimensional affine cipher with $n = 2,\,\,\,\mathcal{P} = \mathcal{C} = {\mathbb{F}_{16}^2}$, where $\mathcal{K} = \{ A,\,\,b\} $ and $b = (0,0)$. The encryption and decryption is in ${\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $. The task is to recover first part of the key - $A$ given two plaintext-ciphertext pairs: ${e_K}((d,5)) = (7,4)$ and ${e_K}((3,1)) = (d,c)$. A known-plaintext attack should be applied to find $A$.

Some observations:

For a typical one-dimensional case in ${\mathbb{Z}_{26}}$ this task is easy. All we need to do is to solve for $A$ ${e_K}(x) - {e_K}(y) \equiv A(x - y)\,(\bmod \,26)$, considering $\exists \,{(x - y)^{ - 1}} \in {\mathbb{Z}_{26}} \wedge (x - y){(x - y)^{ - 1}} \equiv 1\,(\bmod \,26)$ is true. In this case we just multiply both sides by ${(x - y)^{ - 1}}$ and get the value for $A$.

Now in my case its more complicated. The difficulties come from the fact that we need to perform all calculations in ${\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $ and the plain text - cipher text data is in hexadecimal format. Furthermore we are dealing with $2 \times 2$ matrix not just simple decimal value...

Solution attempt:

Based on the one dimensional case i tried to solve for $A$ using $${e_K}(x) - {e_K}(y) \equiv A(x - y)\,(\bmod{x^4} + x + 1)$$

$\begin{gathered} x = \left[ \begin{gathered} d \\ 5 \\ \end{gathered} \right] = \left[ {\begin{array}{*{20}{c}} {{x^3} + {x^2} + 1} \\ {{x^2} + 1} \end{array}} \right],\,\,\,\,y = \left[ \begin{gathered} 3 \\ 1 \\ \end{gathered} \right] = \left[ {\begin{array}{*{20}{c}} {x + 1} \\ 1 \end{array}} \right] \\ {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{*{20}{c}} {{x^2} + x + 1} \\ {{x^2}} \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} {{x^3} + {x^2} + 1} \\ {{x^3} + {x^2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{x^3} + x} \\ {{x^3}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} a \\ 8 \end{array}} \right] \\ x - y = \left[ {\begin{array}{*{20}{c}} {{x^3} + {x^2} + 1} \\ {{x^2} + 1} \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} {x + 1} \\ 1 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{x^3} + {x^2} + x} \\ {{x^2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} e \\ 4 \end{array}} \right] \\ {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{*{20}{c}} {{x^3} + x} \\ {{x^3}} \end{array}} \right] \equiv A \cdot \left[ {\begin{array}{*{20}{c}} {{x^3} + {x^2} + x} \\ {{x^2}} \end{array}} \right]\,\,\,(\bmod \,{x^4} + x + 1) \\ \end{gathered} $

How can i proceed from the last step?

Answer 1

Your subtracting two known solutions would be one way to eliminate $b$ from the equations and allow you to work only with $A$.

However, you've already been told that $b = (0,0)$, and so we don't need to eliminate it.

Instead, we know that the cipher satisfies the relations (omitting $b$ because that's known to be 0):

$$\begin{gathered} A \times \left[ \begin{gathered} d \\ 5 \\ \end{gathered} \right] = \left[ \begin{gathered} 7 \\ 4 \\ \end{gathered} \right]\end{gathered}, \begin{gathered} A \times \left[ \begin{gathered} 3 \\ 1 \\ \end{gathered} \right] = \left[ \begin{gathered} d \\ c \\ \end{gathered} \right]\end{gathered} $$

Where $A$ is a 2x2 array, and all math is done in $GF(16)$. So, if we replace $A$ with the array $A = \begin{gathered} \left( \begin{gathered} x \\ z \end{gathered} \begin{gathered} y \\ w \end{gathered} \right) \end{gathered}$ (where $x, y, z, w$ are unknown values in $GF(16)$, we have:

$$d \cdot x + 5 \cdot y = 7$$

$$d \cdot z + 5 \cdot w = 4$$

$$3 \cdot x + 1 \cdot y = d$$

$$3 \cdot z + 1 \cdot w = c$$

By doing Algebra in $GF(16)$, it's easy to solve these simultaneous equations (hints: remember, $GF(16)$ is a field, and so algebra works there just as you'd expect; you'll need to compute multiplications and inverses in $GF(16)$, if you don't have any tooling on hand to do that, you might find it helpful to whip together a quick program.