Weak RSA

Are you guys saying there’s no way of solving this without the tool?

Hi, i did it with the tool from @sender (thank you very much sender) and everthing works finally. I would really like to know, how the tool did it. How did it proceed after i typed the command and pressed enter? What exactly happened with the key, and possibly what mathematical operations were involved?

It’s not necessary to use the tool, you just have to “calculate” p and q and then use the “non public key” to read the flag.

(maybe this is a spoiler)

@MADHOLUB if you want you can PM me

If someone is still interested in the (mathematical) methods of factorizing n, I recommend this 29C3 talk: 29C3: FactHacks (EN) - YouTube .
For the slides just search for “FactHacks: RSA factorization in the real world”.

Since I did not solve the challenge yet, I can’t say wether it is helpfull for the problem in “weak rsa”. But it is a clear recommendation for anyone interested in this topic.

@sender said:
Actually it is working with an older version I had in my notes. Could not get it to work with the recent version either. I uploaded the working tool Spoiler Removed.

This helped a lot thanks for this!

I can’t get that tool to work. I always get

“error: command ‘x86_64-linux-gnu-gcc’ failed with exit status 1”

The tool on offer is not working at all, it looks like you can no longer install gmpy2 and it’s not supported for python3. I have tried to start solving this manually (not by hand), am I on the right lines trying to factor N or am I wasting my time?

Gmpy2 is available, but you need to manually compile it. However this challenge doesn’t need the gmpy2 module. So just comment ut the import Gmpy2.

Got it working in the end, solved, thanks.

@REdwards365 said:
The tool on offer is not working at all, it looks like you can no longer install gmpy2 and it’s not supported for python3. I have tried to start solving this manually (not by hand), am I on the right lines trying to factor N or am I wasting my time?

Use python 2.7 and don’t forgot to use pip for the requirements .txt for the next one.

@AgentTiro said:
Gmpy2 is available, but you need to manually compile it. However this challenge doesn’t need the gmpy2 module. So just comment ut the import Gmpy2.

This is good suggestion. Tool working now for me :slight_smile: Thanks

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