In the affine cipher with prime $p$, we encrypt a message $m$ as follows:
$$e(m) = k_1m+k_2 ~ (\text{mod } p),$$
and similarly decrypt a ciphertext c as
$$d(c) = k_1^{-1}(c – k2) ~ (\text{mod } p),$$
where $k_1^{-1}$ is the inverse of $k_1$ under modulo $p$. My question is can the keys ($k_1,k_2$) be cracked if we have access to a set of plaintext/ciphertext pairs (i.e., $\{(m_1,c_1),\ldots,(m_n,c_n)\}$)? Intuitively, it seems that the answer should be no, because no matter how many pairs you have it is impossible to figure out $p$ and therefore carry out modulo operations. However, I am not sure how I would go about proving this.
Thanks in advance.
Best Answer
If we have $(m_i,c_i)$ and $(m_j,c_j)$ with $m_i\neq m_j$ then $$c_i-c_j\equiv (k_1m_i+k_2)-(k_1m_j+k_2)\equiv k_1(m_i-m_j)\pmod{p},$$ and so $$k_1\equiv(c_i-c_j)(m_i-m_j)^{-1}\pmod{p}.$$ This holds for all pairs of indices $(i,j)$ so if we also have $(m_k,c_k)$ with $m_k\neq m_i,m_j$ then $$(c_i-c_j)(m_i-m_k)\equiv (c_i-c_k)(m_i-m_j)\pmod{p}.$$ In other words $p$ is a prime factor of $$(c_i-c_j)(m_i-m_k)-(c_i-c_k)(m_i-m_j)=c_i(m_j-m_k)-m_i(c_j-c_k).\tag{1}$$ So the prime factors $p$ of this integer are the only options; factoring this integer yields a finite list of options for $p$.
Of course this is true for any choice of $i$, $j$ and $k$ with $m_i$, $m_j$ and $m_k$ pairwise distinct, so you can take the $\gcd$ of all numbers of the form $(1)$ with $m_i$, $m_j$ and $m_k$ distinct. This will (hopefully) leave a (much) shorter finite list of options for $p$, the more pairs $(m_i,c_i)$ you have.