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}
```
