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!

Comments

  • Hey Philip, yes you are on the right track! But pay attention on how you analyse the public key ;)

  • 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 :)

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

    FloptimusCrime

  • 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.

  • edited July 2018

    Spoiler Removed - Arrexel

  • @sender thx a lot for the link to the tool

    Worked Great :)

  • edited May 2018

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

  • edited June 2018

    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?

  • edited June 2018

    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

    dodo

  • If someone is still interested in the (mathematical) methods of factorizing n, I recommend this 29C3 talk: .
    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.

    ms1028

  • edited January 2019

    @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!

    Arrexel

  • I can't get that tool to work. I always get

    "error: command 'x86_64-linux-gnu-gcc' failed with exit status 1"

    Vex20k

  • 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 :) Thanks

    sesha569

  • Couldn't resist posting this. Hope it doesn't count as a spoiler.
    image

    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.

Sign In to comment.