The sender message is signed by RSA in main.c
The receiver verify message by main.py
If signed message contains 'YES, I did eat the last cookie', we can have flag. However, the service block us from getting the message signed directly by checking if 'YES' is inside the message.
Apparently, we can use RSA blind attack to forge the signed message. However, the input length and characters are restricted by c api. Only 30 characters can be input and the maximum value of character have to be under 0x7f.
The blind attack attack can bypass the check by…
But, we cannot send to service and get signed.
Since we cannot use RSA blind attack directly, we can try to factor the forged message and use modular multiplicative inverse to find all our ingredients.
use sage to find prime factors.
after few minues, we have a good candidate.
then, we try to send those factors into sign service with different multiplier to control our characters are under 0x7f.
Here is the final exploit.
Send the signed message to receiver to get the flag.
It is an excellent challenge, good job.