Plaintext attacks: affine cipher

Question

Consider an affine cipher with encryption function $e$, key $k=(k_1,k_2)$ and some prime $p$. The encryption function $e$ is defined as

$e(m)=k_1m+k_2$ modulo $p$, where $m$ is some message (integer).

Suppose $p$ is known. I know that if both $k_1$ and $k_2$ are unknown, I can find their value if two plaintexts, with corresponding ciphertexts, are provided (that is: two pairs of values $(m_1,c_1)$ and $(m_2,c_2)$).

Suppose now that $p$ is unknown. In my homework, it says that if I have three pairs of values $(m_1,c_2),(m_2,c_2)$ and $(m_3,c_3)$ it is possible to retrieve the prime $p$; without knowing $k_1$ and $k_2$.

Is this really possible? If yes: How would I start proving this? If no: is it possible if both $k_1$ and $k_2$ are known? How would I start proving this?

Answer 1

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

Answer 2

If you know two pairs $(c_1.m_1)$ and $(c_2,m_2)$ isn't it possible to find $\kappa_1$ from equality $c_1-c_2=\kappa_1(m_1-m_2)$ mod p? I thinks ($m_1,m_2$) always has a multiplicative inverse mod p, since p is prime.

And then, after calculating $k_1$, you can find $k_2$ with the help of the third known pair ($c_3.m_3$).