1
$\begingroup$

Suppose we have an RSA encryption oracle $E(m)$ which basically just calculates $m^e \mod n$ for a given message $m$. Here $e=65537$ is known but $n$ is not. Can we determine the value of $n$ without trying all values below $n$, assuming $2^{1023}\leq n <2^{1024}$?

I thought of using $E(-1)$ but sadly only positive messages are allowed. Another idea that i had was to just use $E(2)$ and if $e$ was small it would wrap the modulus only a few times and we would be able to determine $n$. Sadly $2^{65537}$ is many times bigger than $n$ so it doesn't work either.

Improve this question
$\endgroup$
2
  • $\begingroup$ In the present question $e$ is known and $m$ can be chosen. It can only make finding $n$ easier than in said similar question. $\endgroup$
    – fgrieu ♦
    Dec 18, 2018 at 18:52
  • $\begingroup$ Its for a private CTF challenge $\endgroup$
    – Jannes Braet
    Dec 18, 2018 at 19:09

1 Answer 1

Reset to default
5
$\begingroup$

We have $E(x) = x^{65537} - k \cdot n$, for some integer $k$ (which will be different for different values of $x$), and the unknown modulus $n$, and hence $x^{65537} - E(x)$ will always be a multiple of $n$.

So, compute:

$$\gcd( 2^{65537} - E(2), 3^{65537} - E(3) )$$

That will be $n$ multiplied by some integer which is likely to be small...

As similar method (that doesn't involve computing on such large integers, and even works even if you don't know $e$) is to compute:

$$\gcd( E(2)^2 - E(4), E(3)^2 - E(9) )$$

How this works should be fairly obvious...

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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