This was a 150 point challenge with the description:
We have set up this fancy automatic signing server!
We also uses RSA authentication, so it’s super secure!
nc 18.104.22.168 54321
Connecting to the service, we get the following
Obviously, we cannot feed the message
get_your_hands_off_my_RSA! to the oracle. So, we will only receive signatures, but no way to verify them; this means we don’t know either the public modulus, nor the public exponent. But, of course, we could guess the public exponent… there are a few standard ones:
First, I obtained the signatures for and from the provided service. Denote these , respectively. We note that given a correct public exponent , we may compute and . Inevitably, . Hoping for to be small, we can use serveral pairs until we find one that works.
Trying all the listed (guessed) public exponents, we find that (this was performed surprisingly fast in Sage with my Intel hexacore). Hence, we have now determined the modulus
Now, note that
libnum.strings.s2n('get_your_hands_off_my_RSA!') % 3 == 0
OK, so we may split this message into a product of two message factors: and and sign them. Then, we compute the final signature . Mhm, so what now?