# Launching a Plaintext Attack against Affine Cipher

Update 2

Being new to the world of Stack Exchange I did not realize that there exists a site solely devoted to cryptography. In light of this, I hope someone could help me migrate this question to the appropriate site. Unless, of course, someone could answer the question here instead. I am not getting anywhere with this question.

Background

Last year, a question concerning plaintext attacks was posted on on this website. I have no problem to see how to solve it when we are given two ciphertexts and $(c_1,c_2)$ and their corresponding plaintexts $(m_1,m_2)$. But, when I am to deal with the situation where $p$ is unknown it gets complicated. In this instance, I have three pairs of ciphertexts and plaintexts - $c_i \not =c_j$ for $i,j \in \{1,2,3\}$ and $m_i \not = m_j$ for $i,j \in \{1,2,3\}$. This differs then from the previous question in the sense that I cannot use the method that fkraiem provided given two of the ciphertexts are equal.

To find $p$:

You have $k_1m_1+k_2 \equiv k_1m_2+k_2 \equiv c_2 \pmod p$ so $k_1(m_1-m_2) \equiv 0 \pmod p$. This means that either $k_1$ or $m_1-m_2$ is a multiple of $p$ (this is where the fact that $p$ is prime comes in). $k_1$ can't be a multiple of $p$, because otherwise the encryption function is constant, which is absurd, so $m_1-m_2$ is a multiple of $p$.

You can now try to find $k_1,k_2$ using each prime divisor of $m_1-m_2$ as modulus until you find one which works for the two pairs $((m_1,c_2),(m_3,c_3))$ and $((m_2,c_2),(m_3,c_3))$.

Thus my question is this: How would one go about determine $p$ if the ciphertexts are all different?

Update

For example, suppose $(c_1,c_2,c_3)=(13,19,3)$ and $(m_1,m_2,m_3)=(5,10,23)$. How do I go about to determine $p$?

## 1 Answer

You know from the affine equations that there are $t_i$ such that $5k_1 + k_2 = 13 + t_1p, 10k_1 +k_2 = 19+t_2p$ and $23k_1+k_2=3+t_3p$. The first 2 subtracted tells us that $5k_1 -6$ is a multiple of $p$, and the third minus the first tells us $18k_1+10$ is a multiple of $p$ as well.

Multiply $5k_1 -6$ by $18$ and $18k_1+10$ by $5$ and we still have multiples of $p$. Subtract and we know $158$ is a multiple of $p$.

Now you can fill in the rest I think.