# Problem

I RSA encrypted the same message 3 different times with the same exponent. Can you decrypt this?

# Solution

As usual, my first instinct in attempting to solve this problem was to just factor the modulus using msieve. But, a quick test reveals that the moduli are to large for msieve to even attempt to factor (on the order 1024 bits).

Put simply this attack hinges on the Chinese Remainders Theorem; a thousand year old identity that proves recreational math has far reaching implications unfathomable at the time of it’s discovery.

To understand the CRT’s relavence to this problem we must first recall both the Textbook RSA function:

and that we are given three of these pairs in which $p$ and $e$ are held constant.

The Chinese Remainder Theorem tells us that given

we can uniquely determine x. This is great news because this is the exact situation we are in.

With Some more searching I found that one of my favorite haskell libraries already has a function to compute $x$ or $p^e$ from Eq. 2 and 3.

So, after a bit of proccessing and guessing at the public key (it ends up being 3!!!) we end up with the flag (code):

abctf{ch!n3s3_rema1nd3r_the0rem_is_to0_op_4_m3}