Weak RSA (Beginner Track) - Need a nudge in the right direction

HTB Content Challenges
,
1

Alright, so, I’m working on the ‘beginner’ track to try and improve my skills before I try anything more challenging (as I’m still fairly new to pentesting), but I don’t really know where to start with the Weak RSA challenge. A general push in the right direction would be a big help. Hopefully I don’t spend weeks trying to figure this one out like I did the reverse engineering challenge…

2

I’m not an expert, so this will be tips from newbe as well. But do you know math behind the encryption? I like returning to this wikipedia article.

RSA consists of p, q, n = p * q, e, totient = (p-1)*(q-1), d = inverse(e, totient) and inverse is python function from Crypto library it is just too much math for me in short this is inverse of e modulo totient.

  • The pair of numbers n and e makes public key,
  • d the private exponent is private key.

The strong side of RSA is that you can fairly easy compute it one way but it is hard other way around. And this because p and q are quite big primes numbers so when multiplicated to create n makes even larger number that takes ages to find factors. At the end I linked some more info about RSA encryption in general. I myself recommend one from Gynvael as this was a picoCTF challenge rsa-pop-quiz.

I know about two main reason why RSA could be called weak they are more for sure but I’m no crypto expert just cybersec hobbyst :slight_smile:

  • fairly small e like 3
  • broken primes p or q or both

When e is small whole math is reduced to cube root of encrypted message if I’m not mistaken and you could decrypt message like that

When primes are broken and with that I mean, p or q are factorizable or p == q or they factorize to some weird numbers(Watch out here when n consist of more then 2 numbers the totient formula is different). Then you could use something like factordb to check if your primes are weak and with that recreating the private key and decrypt message that way.

I hope I don’t make too many mistakes, and if I do some please correct me I would be happy to refresh my knowledge on this topic.
Video of Gynvael Coldwind solving pico ctf rsa quiz
Video explaining RSA