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$?

Improve this question
$\endgroup$
1
  • $\begingroup$ 1s/factor/product/ $\endgroup$
    – dave_thompson_085
    Sep 26, 2017 at 0:11

1 Answer 1

Reset to default
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$)

Improve this answer
$\endgroup$
0

Your Answer

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

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