WeakRSA (HackTheBox)

G'day everyone! In this write-up we are going to solve the retired WeakRSA challenge on Hack The Box. In order to do so however it is important you understand some of the basics. You will learn

• Basic RSA
• Decoding pem formats

How does RSA work?

RSA is an encryption algorithm which has been around since 1977. To use it you will need to chose two different large prime numbers these will be named p and q.

By multiplying p and q together you get your modulus named N. Then you can choose your exponent which we will name e.  Now you are ready to encrypt your secret message. Using RSA our encryped message will be calculated like this : (message^e) mod N

In python3 it can be computed like this :

pow(message,e,N)

Decrypting RSA

Decrypting will be a little bit harder. To do so we first must find phi φ(N). We can do so like this : φ(N) =  (p-1) * (q-1).

Remember that we need to know p and q to decrypt this is important. We are finally ready to calculate d, the modular inverse of e. This can be done by using the extended euclidean algorithm. You don't have to understand how (or why) it works but saying it will make you look smart. In python I use xgcd from the libnum library. d will be the first value the algorithm outputs.

d = xgcd(e,φN) [0]

 The plaintext can then be calculated :

plaintext = pow(encrypted, d, N)

Solving the challenge

After downloading and extracting the zip we get a key encoded in the pub format. We can decode it using python or just by using an online tool which gives us the following data :

The Modulus being the public key N and the public exponent is our e

We know that the modulus is just p * q but it will take forever to factor such a large number. If only there was a quicker method. Wait a minute what if there are databases containing the factors of large number... That would be really helpful. After some searching I encountered this site. Let's try to input our N :

Looks like we found p and q. From here we can get the flag using python :

The script should output the flag :

HTB{s1mpl3_Wi3n3rs_4tt4ck}

The lesson this challenge is trying to teach us is that p and q should be above 512 digits. This way the public key is less likely to be factorized, so p and q cant be found and your secret messages wont be able to be decrypted.