2
$\begingroup$

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?

$\endgroup$
4
  • $\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$ Jan 29, 2014 at 16:50
  • $\begingroup$ I do not understand your comment (?). $\endgroup$
    – bobbo
    Jan 29, 2014 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, 2014 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, 2014 at 23:36

2 Answers 2

0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ sorry, did the question state $c_1=c_2$ mod $p$? $\endgroup$
    – kodlu
    Jan 27, 2016 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, 2016 at 2:37
0
$\begingroup$

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

$\endgroup$
1
  • $\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$ Feb 4, 2014 at 0:47

You must log in to answer this question.

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