0
$\begingroup$

I have two ciphertexts

$c_1 = m_1^e \bmod n$

$c_2 = m_2^e \bmod n$

I know $c_1, c_2, m_1, m_2$ and $e$. Is there a way to derive n from this? I first thought Franklin Reiter but I'd need an $n$ for that which is precisely what I am missing. What other approaches are there?

$\endgroup$
  • $\begingroup$ Hint: $$a\equiv b\pmod m\iff \exists k\in\mathbb Z:a=b+k\cdot m$$ $\endgroup$ – SEJPM Mar 16 at 12:25
  • $\begingroup$ So from this I derive: $m_1^e + m_2^e - c_1 - c_2 = (j+k) * n$ $\endgroup$ – S. L. Mar 16 at 12:33
  • $\begingroup$ But this doesn't help for $e=65537$ $\endgroup$ – S. L. Mar 16 at 12:38
  • $\begingroup$ Is this homework? I ask because if you're learning, I'd attempt to give you a hint; if you're just trying to solve the problem (while learning as little as possible), I'll just give you the answer $\endgroup$ – poncho Mar 16 at 13:21
  • $\begingroup$ @poncho I'd rather get a hint and if all else fails the answer :) it's not homework but I still want to learn $\endgroup$ – S. L. Mar 16 at 13:30
2
$\begingroup$

Here is the hint you requested:

  • We know that we have $m_1^e - c_1 = k_1n$ for some integer $k_1$

  • We know that we have $m_2^e - c_2 = k_2n$ for some integer $k_2$

So, given that we know the values $k_1n$ and $k_2n$, how can we recover the common $n$ value? Hint: look at the $\gcd$ function...

$\endgroup$
  • $\begingroup$ Worked, had to use sage though $\endgroup$ – S. L. Mar 16 at 14:43
  • 1
    $\begingroup$ With that kind of hint, who needs a solution? $\endgroup$ – fgrieu Mar 16 at 15:01

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.