#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
from math import isqrt, inf
from tqdm import tqdm

pubkey = RSA.importKey(open("pubkey.pem").read())

# Small primes can be found with naive approach.

for i in tqdm(range(3, isqrt(pubkey.n), 2), total=inf):
    if pubkey.n % i == 0:
        p = i
        break
else:
    raise

q = pubkey.n // p
phi = (p-1)*(q-1)
d = pow(pubkey.e, -1, phi)

ciphertext = int(open("message.txt").read())
plaintext = pow(ciphertext, d, pubkey.n)

print(long_to_bytes(plaintext).decode())