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…

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

- 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