3
$\begingroup$

I need to decrypt a message encrypted using RSA. I only know the public keys $n$ and $e$.

I need to get the private key $p$ and $q$ in order to get the decryption exponent $d$. Now to do so, I know I have to factorize the value of $n$, but when I do so using the ifactor function in Maple 2015, the answer given to me is a multiplication of many numbers instead of just 2 like it did in the past. I am clueless on how I should proceed in order to factorize this $n$, any advices would be greatly appreciated

n := 74752948599375228832232800265920355903229476316972757692116239589318799769667409077851878093676056216568921626754052480650902973870821108799

ifactor();
$(3445752473)\space (1246180487)^2\space (91139)\space (84229)\space (82799) (47563)^5\space (31847)\space (21787)\space (15629)\space (89189)\space (58337)\space (30631)\space (45853)\space (91951)\space (88411)\space (11987)\space (74797)\space (25561)\space (65287)\space (73417)\space (45817)\space (27847)$

Thank you in advance for your much needed help

$\endgroup$
  • 1
    $\begingroup$ Hi William, I believe that your value of $n$ is not a multiplication of 2 primes $p$ and $q$. $\endgroup$ – freak_warrior Nov 17 '16 at 1:55
  • 7
    $\begingroup$ Given that factorization, which is probably correct, you can still compute $\varphi(n)$ and compute $d$, then decrypt. $\endgroup$ – mikeazo Nov 17 '16 at 1:57
  • $\begingroup$ A loop which starts in sqrt(n) and ends in 2 testing if n mod iterator = 0 is not enough for you? You can get p and consequently q, phi and d. $\endgroup$ – eightShirt Nov 18 '16 at 1:09
  • $\begingroup$ Furthering on @mikeaso's comment: well, you can decrypt, except if the ciphertext (or equivalently plaintext) is divisible by 47563 or 1246180487, which has probability about 1/47561 for random plaintext. $\endgroup$ – fgrieu Jan 17 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.