Affine cipher and plaintext attacks, how to find the base modulo?

Question

Last year, a question concerning plaintext attacks was posted at Mathematics.SE: “Plaintext attacks: affine cipher”.

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

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

I am not applying it to any exciting problem other than textbook style number problems.

Answer 1

Well, to start off with, we have:

$$k_1 m_1 + k_2 - n_1 p = c_1$$ $$k_1 m_2 + k_2 - n_2 p = c_2$$ $$k_1 m_3 + k_2 - n_3 p = c_3$$

Where we know $m_1, c_1, m_2, c_2, m_3, c_3$, and we don't know $k_1, k_2, p, n_1, n_2, n_3$. I chose to use explicit unknown integers $n_1, n_2, n_3$, rather than modulo an unknown $p$, as it makes it easier to justify the operations we'll do.

The first step is to cancel out the $k_2$ unknown; if we take the first equation, and subtract the second equation, this gives us:

$$(k_1 m_1 + k_2 - n_1 p) - (k_1 m_2 + k_2 - n_2 p) = (c_1) - (c_2)$$

or

$$k_1(m_1 - m_2) - (n_1 - n_2)p = c_1 - c_2$$

Subtracting the second and the third equation gives us:

$$k_1(m_2 - m_3) - (n_2 - n_3)p = c_2 - c_3$$

The next step is to cancel out the $k_1$ unknown; to do this, we multiply the first equation by $(m_2 - m_3)$, multiply the second equation by $(m_1 - m_2)$, and then subtract the two. Doing this (and performing algebraic simplification) results in:

$$((m_2 - m_3)(n_1 - n_2) - (m_1 - m_2)(n_2 - n_3))p =\\ (m_2 - m_3)(c_1 - c_2) - (m_1 - m_2)(c_2 - c_3)$$

Or, in other words, $p$ is a factor of $(m_2 - m_3)(c_1 - c_2) - (m_1 - m_2)(c_2 - c_3)$, which is composed entirely of known values (that is, we can compute it).

Hence, the solution is to compute that value, and if it nonzero, factor it, and go through the factors to search for plausible values of $p$.