This is what we're given:

```
from Crypto.Util.number import *
import sympy.ntheory as nt
import random
p=getPrime(1024)
q=nt.nextprime(p)
for _ in range(random.randint(500,10000)):
q=nt.nextprime(q)
N=p*q
msg="UDCTF{REDACTED}"
pt=bytes_to_long(msg)
e=65537
ct=pow(pt,e,N)
print(N)
print(e)
print(ct)
```

I love this textbook ([https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/](http://)). We can use Fermat's attack since q is the next prime after p according to the source code, and thus q - p is very small. gmpy2.iroot makes it trivial!

UDCTF{F3rma7_c4n_sur3_fac70r!}

```
import gmpy2

n=17740803753336460891508014077951088945415214329359164945595622460861617151883658129377771074141448545977293824812472806768754107334272113784618671425945265453677763300584120796664192793654787317526905676618168560287204392207536711238413377822113265783504873957094131330620182217422910507867161033695120195691266283498385072573721376398480018719760538723050237163598524153522595496137288270407836138586188296538117138982579560625325815068701431157466298638302885600982291990551448117534677697122276691651611734934147801954625280213769902451417946572231015611006746186167211313556716518863585799128114202130873384852581
e=65537
c=7617664236008252568996899627946125782926068188323112773389474654757630578865481085502759186904920518615173703165984894164411436709177950136929724052191922739861682189280802963747906815275683543148623167088950096943169566195634558711652670745197446307315888349532981492405588457559228674864147994684328968321710022127803384848143475788457274558988285904875669797926919759123645348144531804252200718312650929926931919262408975771593313266992606751663814830129337536342634243623652919127335934704778878412649409415730419077839365246227059700689395639431013008985996793686430486195007712091309878718060405038405039494286

a = gmpy2.iroot(n, 2)[0] + 1
b = a*a - n
while not gmpy2.iroot(b, 2)[1]:
print(b)
b = a*a - n
a += 1

p = a - gmpy2.iroot(b, 2)[0]
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
m = format(m, 'x')
for i in range(0, len(m), 2):
print(chr(int(m[i:i+2], 16)), end='')
```