#!/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())

# Primes close to sqrt(N) can be found quickly with Fermat factorization.

a = isqrt(pubkey.n)+1
prog = tqdm(total=inf)
has_sqrt = lambda n: isqrt(n)**2 == n
while not has_sqrt(a * a - pubkey.n):
    prog.update()
    a += 1
prog.close()
b = isqrt(a * a - pubkey.n)

p = a + b
q = a - b
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())