Rating:

> As part of his CTF101 class, Gerald needs to find the plaintext that his teacher encrypted. Can you help him do his homework? ( It's definetely not cheating ;) )

> Author: akth3n3rd

We're given p, q, n, e, ct. I adapted a script from stackoverflow that now looks like this:

```python

# based on https://crypto.stackexchange.com/a/68732

import math

import binascii

def getModInverse(a, m):

if math.gcd(a, m) != 1:

return None

u1, u2, u3 = 1, 0, a

v1, v2, v3 = 0, 1, m

while v3 != 0:

q = u3 // v3

v1, v2, v3, u1, u2, u3 = (

u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3

return u1 % m

def main():

p = int(input('p: ').strip())

q = int(input('q: ').strip())

e = int(input('e: ').strip())

ct = int(input('ct (as hex): ').strip(), 16)

n = p*q

# compute n

n = p * q

# Compute phi(n)

phi = (p - 1) * (q - 1)

# Compute modular inverse of e

d = getModInverse(e, phi)

print("n: " + str(d))

# Decrypt ciphertext

pt = pow(ct, d, n)

print() # separate IO

print("pt (as hex): " + hex(pt)[2:])

print("pt (as string): " + binascii.unhexlify(hex(pt)[2:]).decode())

if __name__ == "__main__":

main()

```

Here's the input/output:

```

p: 251867251891350186672194341006245222227

q: 31930326592276723738691137862727489059

e: 65537

ct (as hex): b99efa97a6800b4a07f2ccb1ba0c02d8a1d07e538ac618d773d35a45cacee47

n: 4895611838388522487150697438371515909261488525071715048233750808546849654653

pt (as hex): 6263616374667b5253415f49535f454153595f41465445525f414c4c7d

pt (as string): bcactf{RSA_IS_EASY_AFTER_ALL}

```

Original writeup (https://eb-h.github.io/bcactf-2021/#easy-rsa).