# 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 qWe 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 = 408579146706567976063586763758203051093687666875502812646277701560732347095463873824829467529879836457478436098685606552992513164224712398195503564207485938278827523972139196070431397049700119503436522251010430918143933255323117421712000644324381094600257291929523792609421325002527067471808992410166917641057703562860663026873111322556414272297111644069436801401012920448661637616392792337964865050210799542881102709109912849797010633838067759525247734892916438373776477679080154595973530904808231e = 65537c = 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}"```