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}*