0
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ I don't have the book in front of me, but if your messages are 2-vectors then this must be a Hill cipher, not affine (I know there are exercises in that chapter on Hill). In that case your key is a matrix and encryption is multiplication of that key against your plaintext vectors. $\endgroup$ – Randall Sep 2 '17 at 13:13
  • $\begingroup$ While this is not your question (yours is easier because you are executing a known plaintext attack), does any of this help you? And if I am wrong about your exercise being Hill, clarify why your messages are vectors (not elements of $\mathbb{Z}_{11}$) and I'll try to help. math.stackexchange.com/questions/2380726/… $\endgroup$ – Randall Sep 2 '17 at 13:16
  • 1
    $\begingroup$ OK, I just checked. This is indeed a Hill cipher, modified to have a constant shift 2-vector $k_2$. You are probably doing the math wrong because of this. Is this helpful? (In particular, the authors say that $k_1$ is a $2 \times 2$ matrix. You give $k_1$ as an element of $\mathbb{Z}_{11}$, not a matrix.) $\endgroup$ – Randall Sep 2 '17 at 13:30
  • 1
    $\begingroup$ What you have here, is a known plaintext attack, not chosen plaintext attack. That would be a lot easier. $\endgroup$ – Henno Brandsma Sep 6 '17 at 14:35
1
$\begingroup$

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...

$\endgroup$
1
$\begingroup$

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}$$

$\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.