#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
import gmpy2
from Crypto.PublicKey import RSA
import base64

def ntos(x):
    n = hex(x)[2:].rstrip("L")
    if len(n)%2 != 0:
        n = "0"+n
    return n.decode("hex")


pvKey = RSA.importKey(open("../files/your_pvt_key.txt").read())

n = pvKey.n
e = pvKey.e
d = pvKey.d

pbKey = RSA.importKey(open("../files/CEO_pb_key.txt").read())

e_ceo = pbKey.e
c =  int(open("../files/message.enc").read().encode("hex"), 16)

k = ((e*d)-1)/n
phi = ((e*d)-1)/k
while phi*k != ((e*d)-1):
    k += 1
    phi = ((e*d)-1)/k
d2 = gmpy2.invert(e_ceo, phi)
m = pow(c,d2,n)
print ntos(m)