1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .