Task

• 3 times RSA: $n$, $e$, $c$ -- cipher
• Additionally some number $a$ with its order
• order $o(a)=$ smallest $k$ with $a^k\bmod n = 1$

Solution

• element-order divides group-order
• multiplicative group modulo n has $\varphi(n)$ elements
• $o(a) \mid \varphi(n) = (p-1)(q-1)$
• $\varphi(n) \approx n$ (a bit smaller)
• Test phi = n // o(a) * o(a)
• compute private key $d = e^{-1}\mod\varphi(n)$, like in key generation
• decode message
• Approach worked for all 3, gives flag in 3 parts
  • First part of the flag is "SaF{Wikipedia_still"
  • Second part of the flag is "_says_you_have_to_di"
  • Third part of the flag is "scard_odd_orders...}

Original writeup (https://github.com/ENOFLAG/writeups/tree/master/SpamAndFlags2020/shor).