# Is affine cipher vulnerable to a known plaintext attack if prime p is unknown?

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.

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.