0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.