For this challenge we had to find all possible messages that are unconcealed when applying RSA with the given e and n, this means that the ciphertext is equal to the plaintext (these messages are called quines in this chall). According to a paper by Rivest, Shamir and Adleman there are always at minimum 9 messages that are unconcealed using (textbook) RSA, that’s one of the reasons you should use a padding scheme!
The naive solution would be to bruteforce every possible message from 0 to n, but clearly this is not an option. If we factorize n we can reduce the search space: if we find a message that is a quine mod p and mod q then we can use the Chinese Reminder Theorem to trivially get a message that is a quine mod n. This is not enough though: p and q are still too big to bruteforce every possible message from 0 to p or q.
We can further improve our approach using the following observations:
- we need to find a number m, s.t. m^e == m mod p and m^e == m mod q
- this is the same as saying m^(e-1) == 1 mod p and m^(e-1) == 1 mod q
- if g is a generator modulo p (same applies for q), then :
- g^k != 1 mod p, for 0<k<p-1
- g^(k*(p-1)) = 1 mod p, for all k>=0
- for each number m with 0<m<p, there exists a x, so that m = g^x mod p (same applies for q)
- so we win if we can find x such that g^(x*(e-1)) = 1 mod p (same applies for q)
Then the only possible solutions are the solutions of the equation k * (p-1) = x * (e-1)
Then we need also to take into account simpler cases, when m = 0 mod p and m != 0 mod q and viceversa, and when m = 0 both mod p and q. We also know that 0, 1 and -1 mod n are always quines.
This script automates the work
Notes:
it uses msieve to factor N in a fast way
i was lazy to find a generator for the group so i just use every odd integer from 3 to 999 as generators (if you have a better solution please comment :) )
After 30 rounds we get the following message:
You are a quine expert!
N = 4760936732132148733835163454914877142839304381211726703612075106971605028843321:58
e = 1911620795404519167398359644484695319372104199151994008417324443382194555245721:58
Flag = 17630078123828546547280811273779001091999247374212025584116067808315926297333
Now we can factor N, compute the private exponent and decrypt the flag.
flag: 0ctf{I_br1ng_5alt_f0r_my_53lf}