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 104.196.116.248 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?
Phew 🙂