17

I need to decrypt c and I was given only n, e and c and computing p and q or phi(n) would be close to impossible so what other alternatives do I have? I tried calculating p and q but I made very little progress with the search in the last 24 hours of continuous running the program.
These are the values I was given:
n: 58900433780152059829684181006276669633073820320761216330291745734792546625247
e: 65537
c: 56191946659070299323432594589209132754159316947267240359739328886944131258862

Also, in another challenge only c and n were given and the values were a lot bigger. Do you have any suggestions for that too?

9
  • 1
    @LukeJoshuaPark I understand that, but the challenge was supposed to be easy. The challenge description is You've overheard a discussion between two classmates arguing whether the size really matters. Commented Apr 17, 2018 at 12:45
  • 2
    Clearly hinting at the fact that n isn't that big yes? That is your hint. Commented Apr 17, 2018 at 12:46
  • @LukeJoshuaPark I figured as much. But still, I have no idea what to do besides trying to bruteforce for the next years or so Commented Apr 17, 2018 at 12:47
  • 1
    Your factors are: 176773485669509339371361332756951225661 and 333197218785800427026869958933009188427 - thanks to sourceforge.net/projects/msieve
    – Iridium
    Commented Apr 17, 2018 at 12:51
  • @Iridium Thanks a lot for the help. As for the second challenge, the hint is something about NP-completeness. Given only n and c this time do you think that I could use msieve to solve this one too? Commented Apr 17, 2018 at 13:09

2 Answers 2

31

Well, it seems that this question is CTF related, because the patterns of n, e, and c are weak numbers.

You can solve it with RsaCtfTool:

python RsaCtfTool -n 58900433780152059829684181006276669633073820320761216330291745734792546625247 -e 65537 --uncipher 56191946659070299323432594589209132754159316947267240359739328886944131258862

timctf{CENSORED}

4
4

https://www.dcode.fr/rsa-cipher Try this one but it need p and q. So I use the hand calculator to find p and q. Using Fact(n), ex: Fact(91)= 7x13, so p=7, q=13

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.