Weak RSA

Couldn’t resist posting this. Hope it doesn’t count as a spoiler.

Tool works fine as of this posting and will give you hint on method used to break the encryption. The flag itself should lead you to the right wiki page if you want to deep dive on how it works.

hi everyone
i git the exponent and modulus from the public key but after that i am stuck. I studies how RSA works and it seems there is no way to generate private key from public key. How to proceed further with this challenge?

there is a way to generate a private key from a public key the whole point of this challenge is to show you that with rsa if primes can be factored it will give you the other mathematical pieces you need to create a private key

Critical piece of information I became aware solving this challenge, if e is huge, so d is small.

Has anybody got p and q out of this with python?
Looks like my python script is going to run forever. It can solve factors of small numbers like 970295970782681553380331135367494949, but this challenge’s n seems to be too big for it…

So I have just finished this and it was more challenging than expected just on the basis of how difficult the tool is. So in order to get this to work properly I went through the process of installing SageMath (if you start the tool without it installed you will get a bunch of messages saying some attacks can’t be performed). You don’t need those attacks so don’t do not spend the time getting SageMath working.

When you run the tool it will get stuck on a particular attack so run each attack individually and you will get the flag.

I finished this too and I agree it was very challenging. In fact it was the hardest challenge that I did on HTB but only because of the tool. It took me several days and lots of hours to make it work. I was nearly crying tears of joy :smiley:

One question remains though: How would you tackle that chall in a manual way without using a tool?
How would you know which attack to try and how would you go about doing it?

Are there any resources out there?

Edit: That video @ms1028 posted is very promising

I installed all the modules but it still seems like it won’t work.

I get the following message
“private argument is not set, the private key will not be displayed, even if recovered.”

p/q/d/N are your friends … that took a long long long time to figure out … I would still like to know why the tool mentioned does not work on this particular public key.

--ORIGINAL POST--

Ditto.  I've also tried openssl and there seems to be an issue with dependencies and unsupported modules so it appears finding older versions of everything is required.

[CORRECTION] if you specify the --private flag you do not get an error you just get nothing.

Thinking it was a Kali issue I tried Parrot Linux no luck although you can install sage math from repository.

Posted this to the GitHub repo/issue:  https://github.com/RsaCtfTool/RsaCtfTool/issues/392

I am sure there is another way to do this but this is really not beginner stuff ...

[UPDATE] using openssl, etc. you can see this is a 1026 key but when I generate one myself and test I can get n and e and all is well.  There is something odd about key.pub in that it's e is not 'normal' it's as if there are two keys in one file but I'm not sure what to do with that.
1 Like