Cracking RSA: The Hard Way

Ever since I finished my OSCP in November of 2021, I haven’t done much in the field of cybersecurity. Since I’m awfully rusty, I decided to start from the very basics and play around with the HTB beginner track. One of the more interesting challenges I finished has been the Weak RSA challenge, which involved generating a private key from a public key with a known factorization. RSA is incredibly common, in fact, the connection to this very website has been secured by RSA (check the certificate details), but I never really explored the underlying math.

The Challenge

The challenge consists of a zip archive containing two files, key.pub and flag.enc. flag.enc is the flag encrypted using RSA, and key.pub is a RSA public key in PEM format.

# key.pub
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQMwO3kPsUnaNAbUlaubn7ip
4pNEXjvUOxjvLwUhtybr6Ng4undLtSQPCPf7ygoUKh1KYeqXMpTmhKjRos3xioTy
23CZuOl3WIsLiRKSVYyqBc9d8rxjNMXuUIOiNO38ealcR4p44zfHI66INPuKmTG3
RQP/6p5hv1PYcWmErEeDewKBgGEXxgRIsTlFGrW2C2JXoSvakMCWD60eAH0W2PpD
qlqqOFD8JA5UFK0roQkOjhLWSVu8c6DLpWJQQlXHPqP702qIg/gx2o0bm4EzrCEJ
4gYo6Ax+U7q6TOWhQpiBHnC0ojE8kUoqMhfALpUaruTJ6zmj8IA1e1M6bMqVF8sr
lb/N
-----END PUBLIC KEY-----

TL;DR

After finishing the challenge, I found several people who posted writeups. (See here and here), but most of them focused on using a tool to automate the attack. Instead, I wanted to do it by hand. For completeness sake though, after extracting the files, this command will solve the challenge:

$ podman run -it --rm -v $PWD:/data docker.io/razaborg/rsactftool --uncipher /data/flag.enc --publickey /data/key.pub  

After running the command, the program spits out the flag:

RSA: The Nitty Gritty

I wanted to know how the tool got the answer though, so I started digging into how RSA works under the hood.

RSA is an asymmetric encryption algorithm, meaning that there are two keys used, one for encryption, and one for decryption. The security of RSA depends on the idea that it’s hard to factor the product of two prime numbers, but it’s easy to multiply those numbers.

A public RSA key has two parts, a modulus and a public exponent. typically noted as n and e, respectively. A private key only needs to contain a private exponent, d. This formula, where m is the plaintext message and c is the encrypted message, is used for encryption:

$$ c = m^e\text{ mod } n $$

while:

$$ m = c^d \text{ mod } n $$

is used for decryption.

As an example ¹ imagine we wanted to encrypt the message “The attack will come at dawn” First, we would pick two random prime numbers that are roughly the same size, for example, p = 79 and q = 97.

n, our modulus, is

$$n = np = 79\cdot97 = 7663$$

Next, we pick a random public exponent. Typically, this number is prime, since we must ensure that the exponent is not a factor of

$$(p -1)(q-1) = 7488$$

and picking a prime number simplifies that calculation. For this example, we pick e = 23.

Lastly, we find d using this equation:

Now, we have our public key: 23,7663, and our private key: 2279, 7663. We share the public key with the person sending the message. They then convert the message into a number using a tool like CyberChef²:

$$\text{The attack will come at dawn} = 84 104…97 119 110$$

Since the message must be shorter than the modulus, we break it into 33 three digit chunks:

Now, we raise each chunk to the power of e modulus n

This leaves us with our encrypted string ³! To decrypt, simply repeat the process, but use the private exponent d instead of e:

With the successful decryption, we can now securely communicate over an insecure channel. As long as d is kept secret, and we are unable to factor the modulus, n, this message will stay secure.

Breaking RSA, the old fashioned way

Now that we have an understanding of how RSA works, we can begin attacking this key. In order to decrypt the message, we need to find d. The first step is to see the components of the key. I used the Python library PyCryptodome. To see the components, we just import the key and PyCryptodome will expose the variables:

from Crypto.PublicKey import RSA

with open('key.pub', 'r') as keyfile:
    key = RSA.import_key(keyfile.read())

print ("e:", key.e)
print ("n:", key.n)

Running the program:

Since we know the modulus, we can check a database to see if this particular number has known factors. For this, I’ll use factordb.com. After pasting the modulus into factordb, we see that the two factors of this number are known:

We can copy those into our python code as p and q from the equations above. Now, we know e (which is part of the public key), p, and q, so we can calculate d, the secret key, using one of the above equations!

from Crypto.PublicKey import RSA

with open('key.pub', 'r') as keyfile:
    key = RSA.import_key(keyfile.read())

p = 20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539
q = 28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857
e = key.e
n = key.n

d = pow(e,-1,((p-1) * (q-1))) # e^-1 mod (p-1)(q-1)

print("d:", d)

Now that we have the secret key, we simply have to use our decryption formula! Since the message is much smaller than the key, we don’t have to worry about chunking.

from Crypto.PublicKey import RSA

with open('key.pub', 'r') as keyfile:
    key = RSA.import_key(keyfile.read())

p = 20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539
q = 28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857
e = key.e
n = key.n

d = pow(e,-1,((p-1) * (q-1))) # e^-1 mod (p-1)(q-1)

# Thanks to https://stackoverflow.com/a/62986942 for the decryption code.
with open('flag.enc', 'rb') as flagfile:
    encflag = int.from_bytes(flagfile.read(), 'big')
    pt_int = pow(encflag,d,n) # m^d mod n
    plaintext = pt_int.to_bytes(128, 'big').lstrip(b'\x00')
    print(plaintext)

Finally, we decrypt the flag:

Conclusion

RSA is an incredible invention. It’s strong enough to be used to secure countless SSH or HTTPS connections, but underneath is a small bit of elegant math that college freshman can understand. It’s honestly amazing to me that the simple exponentiation that I was bored with in my college algebra class is used as the foundation of internet security.

As always, if this was interesting or if you learned a trick or two. Please drop me a line. I always appreciate feedback!