Tags: crt crypto broadcast-attack
Rating:
We start by checking the `script.py` script given to us:
```python
from Crypto.Util.number import *
flag = "This flag has been REDACTED"
moduli = "This array has been REDACTED"
m = bytes_to_long(flag.encode())
e = 3
remainders = [pow(m,e,n) for n in moduli]
f = open('output.txt','w')
for i in range(len(moduli)):
f.write(f"m ^ e mod {moduli[i]} = {remainders[i]}\n")
f.write(f"\ne = {e}")
f.close()
```
We are also provided with the `output.txt` file which contains 7 $moduli$, $remainder$ pair. So, what we are given is:
$$m^3 \equiv c_1 \mod n_1$$
$$m^3 \equiv c_2 \mod n_2$$
$$\vdots$$
$$m^3 \equiv c_7 \mod n_7$$
Here, the $c_i$, $n_i$ pairs are known. We need to find $m$. This is a very classic problem called the broadcast attack. If we take the `chinese remainder theorem` of the pairs, what we are going to get is:
$$ m^3 \equiv c \mod (n_1 * n_2 * \ldots * n_7 ) $$
What happens in such cases is that, the modulo(which is the product of all the $n_i$) is much bigger than $m^3$.
$$ m^3 << c$$
$$m << \sqrt[3] c$$
Thus, just taking `cube-root` of the resulting $c$ yields the message.
```python
from gmpy2 import iroot
m1, v1 = 231689896592553079225008346159565141292942746185614335113030628126523977770897610833 ,70932244057518414814271820586538428333420562252483260602196856595136636875881109254
m2, v2 = 7171431858055720778675521 ,6776581747370220150625940
m3, v3 = 66926822362327139196541990168817936306935699 , 48565469191356626147008517582743644359421796
m4, v4 = 437335592290538364420374052921942150635299817629860400585996176158735283605573507708521 , 8794419984130129081066440741470891653922464557881503503363167507918405790466608773101
m5, v5 = 289641633885807692370107575915133663791 , 172864555741817549854149625512946760571
m6, v6 = 667489211907833441904090408183964916738111 , 123698332225047871848637413013333477895868
m7, v7 = 3567528272153764003837574317682649383619949327607 , 2621823962661199268500092259451160990545103771980
e = 3
mods = [m1, m2, m3, m4, m5, m6, m7]
vals = [v1, v2, v3, v4, v5, v6, v7]
sol = crt(vals, mods)
sol = iroot(sol, 3)
sol = sol[0]
long_to_bytes(int(sol))
```
