2

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?

bobbo
  • 59
  • 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. – AJMansfield Jan 29 '14 at 16:50
  • I do not understand your comment (?). – bobbo Jan 29 '14 at 16:52
  • Okay, thanks! So if we take $p$ to be an integer, what are the answers to my questions? – bobbo Jan 29 '14 at 17:09
  • @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. – fkraiem Feb 03 '14 at 23:36

2 Answers2

0

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

frabala
  • 3,732
  • This is assuming that $p$ is known, when the OP specified that $p$ is unknown (not to mention the value he was solving for!). – AJMansfield Feb 04 '14 at 00:47
0

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

fkraiem
  • 3,129