When signing using RSA with $e = 65537$ and many pairs of m and c, where $$c^e \bmod (n)=m$$ is there a way to find n (n is 2048 bits)?
I planned on computing $ c^e-m $ and then treating those as a basis for a lattice. But $c^e$ was too large.
2
-
$\begingroup$ Duplicate of crypto.stackexchange.com/questions/26188 $\endgroup$– Samuel NevesAug 22, 2021 at 22:50
-
$\begingroup$ The answer provided by @poncho worked well. Also, moving from Python to SageMath improved the speed and made this doable on my machine. $\endgroup$– roziAug 22, 2021 at 22:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
is there a way to find n (n is 2048 bits)?
Yes, if you assume deterministic padding (which is sometimes used for signatures, which appears to be the case you're considering)
You're on the right track by considering $c^e - m$ (which will be a multiple of $n$); given that we have several, what we can do is take two, and compute:
$$\gcd( c^e-n, c'^e-m' )$$
This will be $n$ (multiplied by an integer with a high probability of being small; that's easy to scrap off); that's your answer.
The values we're taking the GCD of are about $2^{27}$ bits in length - using the standard binary or Euclidean algorithms would probably take rather longer than we would prefer to wait. However, Lehmer's GCD algorithm should bring it into a range that's not intolerable...
