# Radio Station Apocalypse
## Challenge
```Bob is trying to stop a Apocalypse can u help him decode his output
File Author : Wh1t3r0se
The file:ct= 15927954374690152068700390298074593196253864077169207071831999310211243220084198633824761313226756137217716813832139827281860280786151119392571330914043785795154126460993477079312886238477507766509831010644388998659565303441719615131661670116956449101956505931748018171190878765731317846254607404813297135537090043417404895660853320127812799010027005785901634939020872408881201149711968120809368691413105318444873712717786940780346214959475833457688794871749017822337860503424073668090333543027469770960756536095503271163592383252371337847620140632398753943463160733918860277382675572411402618882039992721158705125550e= 65537n= 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:
![](https://render.githubusercontent.com/render/math?math=$(p-q)^2=p^2%2Bq^2-2pq$)
![](https://render.githubusercontent.com/render/math?math=$(p%2Bq)^2=p^2%2Bq^2%2B2pq$)
So
![](https://render.githubusercontent.com/render/math?math=$(p%2Bq)^2=(p-q)^2%2B4pq$)
And because we assume `p+q` to be **positive** mod `n`:
![](https://render.githubusercontent.com/render/math?math=$p%2Bq=\sqrt{(p-q)^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:
![](https://render.githubusercontent.com/render/math?math=$ed\equiv1\mod\phi(n)$)
where `d` is the private exponent of RSA (i.e. decrypts your message.)
![](https://render.githubusercontent.com/render/math?math=$\phi(n)=(p-1)(q-1)$)
where ![](https://render.githubusercontent.com/render/math?math=$\phi(n)$) is Euler's totient function, `p` and `q` are hopefully primes.
That also means that
![](https://render.githubusercontent.com/render/math?math=$\phi(n)=pq-p-q%2B1$)
Or rather,
![](https://render.githubusercontent.com/render/math?math=$\phi(n)=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
```pythonfrom 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)+1d=inverse_mod(e,totient)
print(long_to_bytes(c.powermod(d,number)))```
And thus, we receive our flag:
```Trollcat{R5A_1s_n0t_Th4t_ezzz!}```
