2
$\begingroup$

Alice and Bob decide to use the prime $p = 601$ for their affine cipher. The value of $p$ is public knowledge, and Eve intercepts the ciphertexts $c_1 = 324$ and $c_2 = 381$ and also manages to find out that the corresponding plaintexts are $m_1 = 387$ and $m_2 = 491$. Determine the private key and then use it to encrypt the message $m_3 = 173$.

Since the encryption and decryption functions are defined as $$e_k(m)=k_1\cdot m + k_2 (\mod p)$$ and $$d_k(c) = k_1'\cdot (c-k_2) (\mod p), \quad k_1' = \text{inverse of k1 modulo p)}$$ I began by setting up the system $$387k_1 + k_2 (\mod 601) = 324$$ $$491k_1 + k_2(\mod 601) = 381$$

But I can't figure out how to solve for $(k_1, k_2)$

$\endgroup$
1
  • 2
    $\begingroup$ With proper notation, you want to solve$$\begin{align}387k_1+k_2&\equiv324&&\pmod{601}\\491k_1+k_2&\equiv381&&\pmod{601}\end{align}$$I suggest subtracting the first equation from the second, eliminating $k_2$; then solving for $k_1$. You'll need to find an inverse using the Extended Euclidean algorithm; or using that for $x\not\equiv0\pmod p$, it holds that $x^{-1}\equiv x^{p-2}\pmod p$ given that $p$ is prime, per Fermat's little theorem. $\endgroup$
    – fgrieu
    Jul 17, 2017 at 17:32

1 Answer 1

2
$\begingroup$

Remember when you solved systems of linear equations in school? This is essentially the same. You just swap out $K=\mathbb R$ for $K=\mathbb F_{601}$ which allows you to essentially do the same things as with $\mathbb R$, even if it is a little bit less inttuitive.

First too $\mathbb F_{601}$, as $p=601$ is prime, this is what is called a field. Essentially instead of doing normal addition, you do normal addition first and then reduce the result $\bmod p$ (ie take the remainder after integer division by $p$), same for subtraction and multiplication. Exponentiation works the same (as it is just repeated multiplication) and you can use the identity $1/a:=a^{p-2}\bmod p$. Now you can view your problem to solve the following equation over this field:

$$\begin{pmatrix} m_1&1\\ m_2&1 \end{pmatrix} \cdot \begin{pmatrix} k_1\\k_2 \end{pmatrix} = \begin{pmatrix} c_1\\c_2 \end{pmatrix}$$

Obviously you will bring the matrix into triangle form (by subtracting the first line from the second) resulting in $$\begin{pmatrix} m_1&1\\ m_2-m_1&0 \end{pmatrix} \cdot \begin{pmatrix} k_1\\k_2 \end{pmatrix} = \begin{pmatrix} c_1\\c_2-c_1 \end{pmatrix}$$

Implying that $k_1=\frac{c_2-c_1}{m_2-m_1}$, which is indeed expected if we consider the cipher to be a linear function like those you learned in school. Now it immediately follows that $k_1\cdot m_1+k_2=c_1\iff k_2=c_1-k_1\cdot m_1$ and you have thus successfully recovered the full key $\begin{pmatrix} k_1\\k_2 \end{pmatrix}$.

I'll leave it as an exercise to plug-in the numbers and recover the concrete values using a calculator or some online tool.

$\endgroup$
1
  • $\begingroup$ If you are feeling fancy you could also invert the matrix and multiply it from the left with the $c$ vector :p $\endgroup$
    – SEJPM
    Jul 17, 2017 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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