# A classical [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) Problem

The file **enc.txt** contains the public key (e, n) and the ciphertext

We have n, but we dont have p and q
We can try to bruteforce the values of p and q with the following script:

```
for i in range(2, 100000000):
if n % i == 0:
p = i
q = n//p
print("Factors found")
print(p, q)
break
```
Running the above script with pypy yields the factors in around 30sec

*Alternatively you can use [factordb](http://www.factordb.com/index.php?query=408579146706567976063586763758203051093687666875502812646277701560732347095463873824829467529879836457478436098685606552992513164224712398195503564207485938278827523972139196070431397049700119503436522251010430918143933255323117421712000644324381094600257291929523792609421325002527067471808992410166917641057703562860663026873111322556414272297111644069436801401012920448661637616392792337964865050210799542881102709109912849797010633838067759525247734892916438373776477679080154595973530904808231)*

Now we can find phi, using p and q
```
phi = (p-1) * (q-1)
```

And d will be
```
d = pow(e, -1, phi)
```

Now the decryption formula
```
M = pow(C, d, N)
```

Whole Script
```
n = 408579146706567976063586763758203051093687666875502812646277701560732347095463873824829467529879836457478436098685606552992513164224712398195503564207485938278827523972139196070431397049700119503436522251010430918143933255323117421712000644324381094600257291929523792609421325002527067471808992410166917641057703562860663026873111322556414272297111644069436801401012920448661637616392792337964865050210799542881102709109912849797010633838067759525247734892916438373776477679080154595973530904808231
e = 65537
c = 226582271940094442087193050781730854272200420106419489092394544365159707306164351084355362938310978502945875712496307487367548451311593283589317511213656234433015906518135430048027246548193062845961541375898496150123721180020417232872212026782286711541777491477220762823620612241593367070405349675337889270277102235298455763273194540359004938828819546420083966793260159983751717798236019327334525608143172073795095665271013295322241504491351162010517033995871502259721412160906176911277416194406909

for i in range(2, 100000000):
if n % i == 0:
p = i
q = n//p
print(p, q)
break

# p = 15485863
# q = 26384008867091745294633354547835212741691416673097444594871961708606898246191631284922865941012124184327243247514562575750057530808887589809848089461174100421708982184082294675500577336225957797988818721372546749131380876566137607036301473435764031659085276159909447255824316991731559776281695919056426990285120277950325598700770588152330565774546219611360167747900967511378709576366056727866239359744484343099322440674434020874200594041033926202578941508969596229398159965581521326643115137

phi = (p-1)*(q-1)
d = pow(e, -1, phi)
M = bytes.fromhex(hex(pow(c,d, n))[2:])
print(M)
```

```
b"csictf{sh0uld'v3_t4k3n_b1gg3r_pr1m3s}"
```