2
$\begingroup$

Is it possible to calculate the private exponent when only the RSA public key (e;N) = (9292162750094637473537; 13029506445953503759481) is given?

$\endgroup$
  • $\begingroup$ That would only be possible for definitions of RSA that uniquely define the private exponent, such as FIPS 186-4; not for definitions of RSA that allow several private exponents, such as PKCS#1. $\endgroup$ – fgrieu Nov 27 '16 at 4:22
1
$\begingroup$

Yes, since $N=p \times q$, so we have $13029506445953503759481 = 109217267039×119298960679$, also the private and public exponent $e$ and $d$ are related by the equation $ed\equiv1\text{ mod }\phi(N)\equiv1\text{ mod }((109217267039-1)×(119298960679-1)) $. You should then be able to find $d$, the private exponent.

$\endgroup$
  • $\begingroup$ How were you able to find the primes? $\endgroup$ – Arsalan Amjid Nov 26 '16 at 17:32
  • 2
    $\begingroup$ @ArsalanAmjid probably by handing the modulus to a factoring tool? $\endgroup$ – SEJPM Nov 26 '16 at 17:47
  • 1
    $\begingroup$ @Arsalan Wolfram Alpha factored it in about 3 seconds. Note that in real life, N (and hence p and q) would be much, much larger... $\endgroup$ – Dan Nov 26 '16 at 20:11
  • 1
    $\begingroup$ Yes, @Dan is right, now the standard for the modulus $N$ is at least $1024$ bits. $\endgroup$ – freak_warrior Nov 27 '16 at 3:54

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.