# ABCTF 2016: a small broadcast

# 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)*.

A quick google of *a small broadcast rsa* reveals the wikipedia page
for Coppersmith’s attack. **Håstad’s broadcast attack** on this page immediatly jumps
out at me for its simmilarity with the name of this problem. Further reading
confirms this hunch. **Håstad’s broadcast attack** is exactly what we need.

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