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

  • 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 '17 at 17:32

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.

  • $\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 '17 at 20:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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