# Radio Station Apocalypse

## Challenge

```
Bob is trying to stop a Apocalypse can u help him decode his output

File Author : Wh1t3r0se

The file:
ct= 15927954374690152068700390298074593196253864077169207071831999310211243220084198633824761313226756137217716813832139827281860280786151119392571330914043785795154126460993477079312886238477507766509831010644388998659565303441719615131661670116956449101956505931748018171190878765731317846254607404813297135537090043417404895660853320127812799010027005785901634939020872408881201149711968120809368691413105318444873712717786940780346214959475833457688794871749017822337860503424073668090333543027469770960756536095503271163592383252371337847620140632398753943463160733918860277382675572411402618882039992721158705125550
e= 65537
n= 25368447768323504911600571988774494107818159082103458909402378375896888147122503938518591402940401613482043710928629612450119548224453500663121617535722112844472859040198762641907836363229969155712075958868854330020410559684508712810222293531147857306199021834554435068975911739307607540505629883798642466233546635096780559373979170475222394473493457660803818950607714830510840577490628849303933022437114380092662378432401109413796410640006146844170094240232072224662551989418393330140325743682017287713705780111627575953826016488999945470058220771848171583260999599619753854835899967952821690531655365651736970047327
(p-q)= 13850705243110859039354321081017038361100285164728565071420492338985283998938739255457649493117185659009054998475484599174052182163568940357425209817392780314915968465598416149706099257132486744034100104272832634714470968608095808094711578599330447351992808756520378741868674695777659183569180981300608614286
```

## OkEnoughPleasantriesLetsBegin

Unless you are completely new to CTF crypto, it should be painfully obvious that the cryptosystem in interest is `RSA` (for the [uninitiated](https://en.wikipedia.org/wiki/RSA_(cryptosystem))).

We are given a ciphertext `ct`, public exponent `e`, modulus `n`, and an... **interesting** number `p-q`.

That's about it for this challenge really.

## In Which N00bcak Goes Back to Secondary School

Basically here's why `p-q` is interesting:

^2=p^2%2Bq^2-2pq$)

^2=p^2%2Bq^2%2B2pq$)

So

^2=(p-q)^2%2B4pq$)

And because we assume `p+q` to be **positive** mod `n`:

^2%2B4pq}$)

### Ok cool, but why is this useful exactly?

Recall (or go to the [Wikipedia page](https://en.wikipedia.org/wiki/RSA_(cryptosystem))) that:

$)

where `d` is the private exponent of RSA (i.e. decrypts your message.)

=(p-1)(q-1)$)

where $) is Euler's totient function, `p` and `q` are hopefully primes.

That also means that

=pq-p-q%2B1$)

Or rather,

=n-(p%2Bq)%2B1$)

So since we HAVE `n` and `p+q`, we can compute `d` using the `Extended Euclidean Algorithm`.

### Verdict: Secondary School Math + Following Instructions.

## And Now, Actually Solving For The Flag

Haha Sagemath go brr

```python
from Crypto.Util.number import long_to_bytes

number=25368447768323504911600571988774494107818159082103458909402378375896888147122503938518591402940401613482043710928629612450119548224453500663121617535722112844472859040198762641907836363229969155712075958868854330020410559684508712810222293531147857306199021834554435068975911739307607540505629883798642466233546635096780559373979170475222394473493457660803818950607714830510840577490628849303933022437114380092662378432401109413796410640006146844170094240232072224662551989418393330140325743682017287713705780111627575953826016488999945470058220771848171583260999599619753854835899967952821690531655365651736970047327

e=65537

c=15927954374690152068700390298074593196253864077169207071831999310211243220084198633824761313226756137217716813832139827281860280786151119392571330914043785795154126460993477079312886238477507766509831010644388998659565303441719615131661670116956449101956505931748018171190878765731317846254607404813297135537090043417404895660853320127812799010027005785901634939020872408881201149711968120809368691413105318444873712717786940780346214959475833457688794871749017822337860503424073668090333543027469770960756536095503271163592383252371337847620140632398753943463160733918860277382675572411402618882039992721158705125550

p_q=13850705243110859039354321081017038361100285164728565071420492338985283998938739255457649493117185659009054998475484599174052182163568940357425209817392780314915968465598416149706099257132486744034100104272832634714470968608095808094711578599330447351992808756520378741868674695777659183569180981300608614286

ppq=sqrt((p_q)^2+4*number)
print(ppq==int(ppq))
totient=number-int(ppq)+1
d=inverse_mod(e,totient)

print(long_to_bytes(c.powermod(d,number)))
```

And thus, we receive our flag:

```
Trollcat{R5A_1s_n0t_Th4t_ezzz!}
```

Original writeup (https://github.com/IRS-Cybersec/ctfdump/blob/master/TrollCAT%202021/Radio%20Station%20Apocalypse.md).