Weak RSA

Hello!

I started the “Weak RSA” challenge today. It contains two files the “key.pub” which , as the name implies, is the public key and the “flag.enc” which is the file I need to decrypt.

I have tried to analyze the public key through OpenSSL but the modulo doesn’t seem to be non-random i.e ( lots zeroes or any specific sequence).

Also what puzzled me was that the Exponent seemed way to big

Am I heading in the right track? Any help would be appreciated

Thanks in advance!

Hey Philip, yes you are on the right track! But pay attention on how you analyse the public key :wink:

Im stuck at the same place, i tried factorizing the modulus but to no avail

@ninjat said:
Im stuck at the same place, i tried factorizing the modulus but to no avail

Remember that the weak RSA it’s a common CTF style problem. I’m sure you find tools to help you solve the challenge :slight_smile:

I used the only tool i could find, still no luck

if that tool fails, maybe see if others have suggested a fix to it

The tool does work. Be sure to install all dependencies. There is a requirements.txt in the folder. Do pip install -r requirements.txt to install them. And the extra one aswell.

Spoiler Removed - Arrexel

@sender thx a lot for the link to the tool

Worked Great :slight_smile:

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