Known-plaintext-attack Affine Cipher - Calc $k_1$ and $k_2$ from 3 plaintext / ciphertext pairs.

Question

Question is 1.42(c) of Introduction to Mathematical Cryptography, on page 56.

The encryption and decryption schemes are;

$$e_k(m)\equiv k_1.m + k_2, \mod p $$ $$d_k(m)\equiv k_1^{-1} (c-k_2), \mod p$$

You are asked to calculate $k_1$ and $k_2$ given the below plaintext/ciphertext pairs, and $p=11$.

$$(m_1,c_1)=(\begin{bmatrix}5\\4\end{bmatrix}, \begin{bmatrix}1\\8\end{bmatrix})$$ $$(m_2,c_2)=(\begin{bmatrix}8\\10\end{bmatrix}, \begin{bmatrix}8\\5\end{bmatrix})$$ $$(m_3,c_3)=(\begin{bmatrix}7\\1\end{bmatrix}, \begin{bmatrix}8\\7\end{bmatrix})$$

My attempt;

I found that via taking 3rd congruence away from the 2nd, that I get;

$$k_1\equiv 0 \mod 11$$, and $$9k_1 \equiv -2 \mod 11$$

Solving these two congruences I get

$$k_1\equiv 0 \mod 11$$

and hence

$$k_2 \equiv \begin{bmatrix}8\\-4\end{bmatrix} \mod 11$$.

However when using these values for $k_1$ and $k_2$ in the original 1st and 2nd congruences I find that the congruences are not satisfied.

Questions;

1. Where am I going wrong?
2. What is the correct solution with full working?

Answer 1

Get an understanding of the cipher first and foremost. (I'll work mod 11 everywhere.)

We fix an invertible matrix $k_1 = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ and a vector $k_2 = (u, v)^T$. Plain- and ciphertext messages are also vectors. Given a plaintext vector $\mathbf{p} = (x, y)^T$ we encrypt by $$ \mathbf{c} = k_1 \mathbf{p} + k_2 $$ which is again a 2-vector.

Note that you have 6 parameters: the 4 entries of $k_1$ and the 2 entries of $k_2$. You also have 6 known pieces of data: the 6 vectors in the plain/ciphertext pairs. Start doing the algebra...

Answer 2

Indeed $k_1$ must be a matrix, say $\begin{bmatrix} a & b \\ c & d\end{bmatrix}$ and $k_2$ a vector $\begin{bmatrix} p \\ q \end{bmatrix}$. Then looking at the first row of the matrix and $p$: these are the elements that determine the first component of every $(c,p)$ pair. So the plaintext $\begin{pmatrix} 5\\4\end{pmatrix}$ mapping to the ciphertext $\begin{pmatrix}1\\8 \end{pmatrix}$ gives us the equation $$5a + 4b + p = 1$$ the second pair yields $$8a + 10b + p = 8$$ while the third pair gives $$7a + b + p = 8$$ where all computations are done modulo $11$ of course. So in schematic form we get the system $$\left[ \begin{array}{ccc|c} 5 & 4 & 1 & 1 \\ 8 & 10 & 1 & 8 \\ 7 & 1 & 1 & 8 \end{array}\right]$$

Similarly for $c,d,q$ we get a system with the same coefficients but a different right hand side:

$$\left[ \begin{array}{ccc|c} 5 & 4 & 1 & 8\\ 8 & 10 & 1 & 5\\ 7 & 1 & 1 & 7 \end{array} \right] $$

So we can do elimation on two systems at the same time:

$$\left[ \begin{array}{ccc|cc} 5 & 4 & 1 & 1 & 8\\ 8 & 10 & 1 & 8 & 5\\ 7 & 1 & 1 & 8 & 7 \end{array} \right] $$

where the first column right of the bar is for the $a,b,p$ system, and the other for the $c,d,q$ system.

If we had reals we would subtract the first row $\times \frac{8}{5}$ from the second to eliminate the first variable. Modulo $11$ we note that $5^{-1} = 9$ because $5\times 9 = 45 \equiv 1 \pmod{11}$. So we multiply the first equation (both left and right hand side) with $8 \times 5^{-1} = 8 \times 9 = 72 \equiv 6 \pmod{11}$, which gives $$\left[ \begin{array}{ccc|cc} 30 & 24 & 6 &6 & 48\end{array}\right]$$ which is mod $11$ equivalent to $$\left[ \begin{array}{ccc|cc} 8 & 2 & 6 &6 & 4 \end{array} \right]$$

We substract this from the second equation an get a new equation: $$\left[ \begin{array}{ccc|cc} 0 & 8 & -5 &2 & 1\end{array}\right]$$

which mod $11$ is $$\left[ \begin{array}{ccc|cc} 0 & 8 & 6 &2 & 1\end{array}\right]$$

Also we want to eliminate the first variable from the third equation. So we substract $\frac{7}{5} =7 \cdot 5^{-1}= 63 \equiv 8 \pmod{1}$ times the first equation (the original one) from the third.

First compute $8$ times the first:

$$\left[ \begin{array}{ccc|cc} 40 & 32 & 8 & 8 & 64 \end{array} \right] $$

which modulo $11$ becomes

$$\left[ \begin{array}{ccc|cc} 7 & 10 & 8 & 8 & 9 \end{array} \right] $$

So we get a new third equation:

$$\left[ \begin{array}{ccc|cc} 0 & -9 & -7 & 0 & -2 \end{array} \right] $$

or $$\left[ \begin{array}{ccc|cc} 0 & 2 & 4 & 0 & 9 \end{array} \right] $$

So in total we get the equations after elimination step 1:

$$\left[ \begin{array}{ccc|cc} 5 & 4 & 1 & 1 & 8\\ 0 & 8 & 6 & 2 & 1\\ 0 & 2 & 4 & 0 & 9 \end{array} \right] $$

The next phase: eliminate the second variable from eq. 2 and 3. To this end we do "$\text{eq. } 3 - \frac{2}{8} \text{eq. } 2$" and we note that $8^{-1} \pmod{11} = 7$ so $\frac{2}{8}$ is $14 \equiv 3$. $3$ times the new eq. 2 becomes: $$\left[ \begin{array}{ccc|cc} 0 & 24 & 18 & 6 3 \end{array} \right] $$

which is the same (mod $11$) as

$$\left[ \begin{array}{ccc|cc} 0 & 2 & 7 & 6 & 3 \end{array} \right] $$

So new eq.3 becomes:

$$\left[ \begin{array}{ccc|cc} 0 & 0 & -3 & -6 &6 \end{array} \right] $$

Now we can back-substitute the two equation systems (recall the first column was for the system in terms of $a,b,p$): $-3p = -6$, so $p=2$. Then $8b + 6p = 2$ from the updated second equation. So $8b + 12 = 2 \rightarrow 8b = -10 = 1$, so $b = 8^{-1} \equiv 7 \pmod{11}$.
Finally $5a + 4b + p = 1 \rightarrow 5a + 28 + 2 = 1 \rightarrow 5a = 4 \pmod{11}$, which gives $a=3$ from $5^{-1} = 9$ again.

The same can now be done for $-3q = 6$, so $q = -2 = 9$.
Then $8d + 6q = 1 \rightarrow 8d + 54 = 1 \rightarrow 8d = 2 \pmod{11}$ hence $d = 2 \cdot 7 \equiv 14 \equiv 3$.
Finally $5c + 4d + q = 7 \rightarrow 5c + 12 + 9 = 7 \rightarrow 5c = 8$ so that $c = 4$.

So the cipher was given by $$\begin{bmatrix} c_1 \\ c_2\end{bmatrix} = \begin{bmatrix} 3 & 7 \\ 4 & 3\\ \end{bmatrix}\begin{bmatrix} p_1 \\ p_2\end{bmatrix} + \begin{bmatrix} 2 \\ 9\end{bmatrix}$$