How to break 512-Bit RSA Key for $0 in 0 seconds On-prem

A few months ago I read the article: How We Cracked a 512-Bit DKIM Key for Less Than $8 in the Cloud.

Oh, it looks interesting. Everyone is intrigued by hacking.

Yes but I wandered if that could have been archived in a cheaper and faster way.

Well, you need to have a more powerful machine.

Not necessary. In fact a few years ago I participated in a CTF contest and I arrived second. I learned a lot about RSA encryption. The technique that I used is not bruteforce but instead is a sort of dictionary attack.

Do we have a dictionary of RSA key?

No but we have a database of factorized numbers called https://factordb.com/.
Back in 2014 I remember this database was around 200MB in size and today it has doubled:

This means that the database is constantly expanding and is finding new factorized numbers every year.
This means that every year there are more and more RSA key that are easier to brake.
And now is time to say something boring…

Oh, no please, I already see where we are going…

Let me drop the phrase:

How RSA encryption works

Please kill me.

We warn readers that this example will be broadcasted in a shortened form to accommodate our mental capabilities:

Element name	What it is	Formula	Is contained in
p	is large prime number		Private Key
q	is large prime number		Private Key
n	is called Modululs	p * q	Public Key
r	is Euler's totient function	(p-1) * (q -1)	Private Key
e	is a prime number. It must be lower than r and it mustn't be a divisor of n. most of the time you will find the number 65537		Public Key
d	is the private key exponent	e^-1 mod * (r)	Private Key

I know it still might look like a mess. So you know what I like to do?

Tell me…

I like to do…

Hands on

Follow these steps:

Copy/paste the Public Key that you find in the article. It looks like this:

-----BEGIN PUBLIC KEY----- 
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQ==
-----END PUBLIC KEY-----

-----BEGIN PUBLIC KEY-----

MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQ==

-----END PUBLIC KEY-----

And save it into a file called 512_public_key.pem

Now save this code into a file called Test_RSA.py:

import sys
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.backends import default_backend
from factordb.factordb import FactorDB
from sympy import mod_inverse
from cryptography.hazmat.primitives.asymmetric import rsa

def extract_rsa_key_info(pem_file):
    with open(pem_file, "rb") as f:
        public_key = serialization.load_pem_public_key(f.read(), backend=default_backend())
    
    if hasattr(public_key, 'public_numbers'):
        numbers = public_key.public_numbers()
        n, e = numbers.n, numbers.e
        print(f"n: {n}")
        print(f"e: {e}")
        
        # Factorizing n using FactorDB
        f = FactorDB(n)
        f.connect()
        factors = f.get_factor_list()
        
        if len(factors) == 2:
            p, q = map(int, factors)
            print(f"p: {p}")
            print(f"q: {q}")
            
            # Compute d
            phi = (p - 1) * (q - 1)
            d = int(mod_inverse(e, phi))
            print(f"d: {d}")
            
            # Generate and print the private key
            private_key = rsa.RSAPrivateNumbers(
                p=p,
                q=q,
                d=d,
                dmp1=d % (p-1),
                dmq1=d % (q-1),
                iqmp=pow(q, -1, p),
                public_numbers=rsa.RSAPublicNumbers(e=e, n=n)
            ).private_key(default_backend())
            
            pem = private_key.private_bytes(
                encoding=serialization.Encoding.PEM,
                format=serialization.PrivateFormat.TraditionalOpenSSL,
                encryption_algorithm=serialization.NoEncryption()
            )
            print("\nPrivate Key (PEM format):")
            print(pem.decode())
        else:
            print("Unable to factorize n into two prime numbers.")
    else:
        print("Invalid RSA public key.")

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print("Usage: python script.py &lt;path_to_pem_file&gt;")
        sys.exit(1)
    
    pem_file = sys.argv[1]
    extract_rsa_key_info(pem_file)

import sys

from cryptography.hazmat.primitives import serialization

from cryptography.hazmat.backends import default_backend

from factordb.factordb import FactorDB

from sympy import mod_inverse

from cryptography.hazmat.primitives.asymmetric import rsa

def extract_rsa_key_info(pem_file):

with open(pem_file, "rb") as f:

public_key = serialization.load_pem_public_key(f.read(), backend=default_backend())

if hasattr(public_key, 'public_numbers'):

numbers = public_key.public_numbers()

n, e = numbers.n, numbers.e

print(f"n: {n}")

print(f"e: {e}")

# Factorizing n using FactorDB

f = FactorDB(n)

f.connect()

factors = f.get_factor_list()

if len(factors) == 2:

p, q = map(int, factors)

print(f"p: {p}")

print(f"q: {q}")

# Compute d

phi = (p - 1) * (q - 1)

d = int(mod_inverse(e, phi))

print(f"d: {d}")

# Generate and print the private key

private_key = rsa.RSAPrivateNumbers(

p=p,

q=q,

d=d,

dmp1=d % (p-1),

dmq1=d % (q-1),

iqmp=pow(q, -1, p),

public_numbers=rsa.RSAPublicNumbers(e=e, n=n)

).private_key(default_backend())

pem = private_key.private_bytes(

encoding=serialization.Encoding.PEM,

format=serialization.PrivateFormat.TraditionalOpenSSL,

encryption_algorithm=serialization.NoEncryption()

)

print("\nPrivate Key (PEM format):")

print(pem.decode())

else:

print("Unable to factorize n into two prime numbers.")

else:

print("Invalid RSA public key.")

if __name__ == "__main__":

if len(sys.argv) != 2:

print("Usage: python script.py <path_to_pem_file>")

sys.exit(1)

pem_file = sys.argv[1]

extract_rsa_key_info(pem_file)

Now run python .\Test_RSA.py .\512_public_key.pem , and in less than one second you have the results:
As you can see the elements n, e, p, q, d are all the same as in the article and the Private Key as well.

This exercise took $0 and 0 seconds on-prem.

As explained in the article you will pay $8 and “few hours” in the Cloud.

Did you write that code with ChatGPT?

No, I used Perplexity.ai in this case as ChatGPT was a bit sleepy. The code I was using in 2014 is forever lost with no shame.

Conclusion

So now I can go out in the wild and use your code to brake RSA keys in seconds! That is beautiful and horrifying at the same time

No, I think you should use RsaCtfTool. This is the go-to tool for braking RSA keys.
It contains all sort of method and attack and the tool just try all of them one after another till it brakes the key.

But 512-bit keys are easy to brake, everything higher than that will require more computer power.

Not really, back in 2014 this is the article that I used to instruct myself about RSA key and the guy was braking 768-bit RSA Encryption.
Once again, this is not bruteforce, this is a sort of dictionary attack: if the factorized number is in the database you have 100% of chance to brake the RSA encryption. If the factorized number is not the database you have 0% of chance to brake the RSA encryption.
That’s why the RsaCtfTool is the go-to tool.

OK but what about 1024-bit RSA Encryption?

The year 2014 was also remembered as the year of the Heartbleed attack.
This is an article from 2014 that explains how you can brake the RSA encryption through the ./heartbeat.py script.
Read the article.
If that script doesn’t works just follow the steps, run echo | openssl s_client -connect 192.168.1.13:443 2>/dev/null | openssl x509 and use my script to extract the factorized numbers from the Public Key.
It might work or it might not work.

OK but what about 2048-bit RSA Encryption?

That is solid.
But, in a scenario of DKIM key you might not be allowed to use it.

Are you completely mad? We are in 2025! Everyone should accept 2048-bit RSA Encryption!

I know, I faced this scenario in 2020 with G-Suite and AWS DNS.
I was the guy setting up DMARC, DKIM, and SPF and it turned out that with 2048-bit lots of mail got rejected.
And we were using G-Suite and AWS DNS! What can possibly go wrong?
We had to switch back to 1024-bit.

We still live in an insecure World…

We live every day in a more insecure World. But you can test the strength of your DKIM key thanks to my script or the RsaCtfTool . Or send an e-mail to https://dmarcchecker.app/

Good night

How RSA encryption works

Hands on

Conclusion

Related

Leave a Reply Cancel reply