2
$\begingroup$

Assume a common RSA public key $(N,e)$ with $N$ the product of two unknown distinct randomly chosen large primes $p$ and $q$ of about the same size.

Does revealing $p^e\bmod N$ (in addition to the public key) allow factorization of $N$, or otherwise makes it markedly easier to solve the RSA problem? What about also revealing $q^e\bmod N$?

$\endgroup$
  • $\begingroup$ 1s/factor/product/ $\endgroup$ – dave_thompson_085 Sep 26 '17 at 0:11
7
$\begingroup$

Does revealing $p^e\bmod N$ (in addition to the public key) allow factorization of $N$

Yes, with that extra information, $N$ is easy to factor. A computation of $\gcd( N, p^e \bmod N )$ gives the factor $p$ (because $p$ is the only prime the two integers $N$ and $p^e \bmod N$ have in common, it is a factor of both integers, while $q$ is not a factor of $p^e \bmod N$)

$\endgroup$

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.