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?

  • $\begingroup$ Affine ciphers don't need to use prime numbers. The modulus should be the size of the cipher alphabet, to which $k_1$ and $k_2$ need to be relatively prime. Picking a sufficiently large prime modulus just ensures that any $k_1$ and $k_2$ will fulfill that requirement. $\endgroup$ – AJMansfield Jan 29 '14 at 16:50
  • $\begingroup$ I do not understand your comment (?). $\endgroup$ – bobbo Jan 29 '14 at 16:52
  • $\begingroup$ Okay, thanks! So if we take $p$ to be an integer, what are the answers to my questions? $\endgroup$ – bobbo Jan 29 '14 at 17:09
  • $\begingroup$ @AJMansfield It is true that affine ciphers do not require a prime modulus, but they are not forbidden either. Here, we have a prime modulus, period. Also, it is only $k_1$ which needs to be relatively prime with the modulus. $\endgroup$ – fkraiem Feb 3 '14 at 23:36

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

  • 1
    $\begingroup$ sorry, did the question state $c_1=c_2$ mod $p$? $\endgroup$ – kodlu Jan 27 '16 at 2:35
  • $\begingroup$ @kodlu There is no $c_1$ in that part of the question (the part where $p$ is unknown). $\endgroup$ – fkraiem Jan 27 '16 at 2:37

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

  • $\begingroup$ This is assuming that $p$ is known, when the OP specified that $p$ is unknown (not to mention the value he was solving for!). $\endgroup$ – AJMansfield Feb 4 '14 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.