We're given a broken implementation of RSA in Python:

```from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 65536

def gen_key():
p = getPrime(1024)
q = getPrime(1024)
n = p # q
t = (p-1) * (q-1)
d = inverse(e, t)
return n, d

def encrypt(n, e, m):
c = pow(m, e, n)
return c

# for some reason my decrypt function doesn't work!
# can you help me recover the message?
def decrypt(n, d, c):
m = pow(c, d, n)
return m

FLAG = b'pwnEd{???...?}'

n, d = gen_key()
m    = bytes_to_long(FLAG)

c    = encrypt(n, e, m)
m    = decrypt(n, d, c)

print(f'n = {n}')
print(f'Encrypted flag: {c}')
print(f'It just doesn\'t work!: {long_to_bytes(m)}')
```

The first things to notice are that e isn't the usual 65537, and isn't prime either. Then n evaluates to just p instead of pq, so the output we're given:

``````n = 158956010976836742521330254087275425096501583054825136137040889728364290468342445750425376148898452284963095323948276435573809460871703413808672473157217817381946017879464498512288960101002405275174672926496400917470509079465025417877720664744491054992376496575684398645703346912039046842844204816524282238459
Encrypted flag: 17696325213195819360084027228862087546075383230711834052302081670404491942278399339165629822030797913121661625273125782635636475385580385239446207346095935362399429412825040827923795088154904762207215060766109368707427481633970394393914176132798637385151502305355038711511174834777689397585730318578634645332
uses the wrong private key. So, we're given n which is prime, thus there isn't really a p or q, the ciphertext c and e. Using sources to work out how RSA works and calculate the correct value for d, the totient φ(n) is n-1 since n is prime. Typically this is all that should be done, and RsaCtfTool managed to decrypt the ciphertext with `python3 RsaCtfTool.py -n <N> -e 65536 --uncipher <CIPHER> --attack ecm2`, but this was all we could get to during the CTF. Afterwards, it's revealed that since e isn't coprime with φ(n) we can't decrypt the message as you usually would.
One reason RSA works is that ed = 1 (mod φ(n)) holds, it follows that c^d = m^ed = m (mod n), proof here. Since the decryption isn't working even with the correct d then ed = x (mod φ(n)) where x isn't 1. Finding this x is rather simple, we just evaluate `e*d%n`, which gives us 2. Recall that m^ed = m (mod n), so we've got the message squared. To find the modular square root, we use the Tonelli-Shanks algorithm. Since there's an online implementation, we just enter our m^2 for a and n for p, convert this long into bytes and we get the flag.