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}

fox