#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from sympy import primefactors

# Hastad Boardcast: Multiple unpadded ciphertexts with small e.
# Use Chinese Remainder Theorem to extract plaintext.
# Possible since N1*N2*N3 larger than M^e for e = 3.

recipients = [
    RSA.importKey(open("german_government.pem").read()),
    RSA.importKey(open("us_government.pem").read()),
    RSA.importKey(open("russian_government.pem").read()),
]
ciphertexts = [int(l.split(": ")[1]) for l in open("intercepted-messages.txt").readlines()]

# C1 = K mod N1,   C2 = K mod N2,   C3 = K mod N3
# K = C1 * N2 * N3 * pow(N2 * N3, -1, N1) + ... (mod N1 * N2 * N3)
# K % N1 = C1 * N2 * N3 * pow(N2 * N3, -1, N1) = C1

N = 1
for r in recipients:
    assert(r.e == 3)
    N *= r.n

K = 0
for i in range(3):
    K += ciphertexts[i] * (N // recipients[i].n) \
        * pow(N // recipients[i].n, -1, recipients[i].n)
K %= N

plaintext, real = iroot(K, 3)
assert(real)

print(long_to_bytes(plaintext).decode().lstrip("A"))