import subprocess, math
from sympy import mod_inverse
out = subprocess.check_output("openssl rsa -in public_main.pem -pubin -modulus -noout", shell=True, text=True)
N_main = int(out.strip().split('=')[1],16)
aux1 = int(subprocess.check_output("openssl rsa -in stage3_pub_aux1.pem -pubin -modulus -noout", shell=True, text=True).split('=')[1],16)
aux2 = int(subprocess.check_output("openssl rsa -in stage3_pub_aux2.pem -pubin -modulus -noout", shell=True, text=True).split('=')[1],16)
p1 = math.gcd(N_main, aux1)
p2 = math.gcd(N_main, aux2)
s_ok=int.from_bytes(open('stage4_sign_ok.bin','rb').read(),'big')
s_faulty=int.from_bytes(open('stage4_sign_faulty.bin','rb').read(),'big')
G = math.gcd(N_main, s_ok - s_faulty)
r = G//(p1*p2)
p4 = N_main // (p1*p2*r)
c = int.from_bytes(open('final_cipher.bin','rb').read(),'big')
E = 65537
primes = [p1,p2,p4]
d_vals=[]
for p in primes:
    d = mod_inverse(E, p-1)
    d_vals.append(d)
a=[]
for (p,d) in zip(primes,d_vals):
    a.append(pow(c, d, p))
from math import prod
def crt(values, moduli):
    M=1
    x=0
    for n_i, a_i in zip(moduli, values):
        M *= n_i
    x=0
    m=1
    for n_i,a_i in zip(moduli, values):
        k = ( (a_i - x) * mod_inverse(m, n_i) ) % n_i
        x += m*k
        m *= n_i
    return x

m_partial = crt(a, primes)
msg_bytes = m_partial.to_bytes((m_partial.bit_length()+7)//8,'big')
try:
    print(msg_bytes.decode())
except Exception as e:
    print('decode error',e)