solve.py (1078B)
1#!/usr/bin/env python3 2 3from Crypto.PublicKey import RSA 4from Crypto.Util.number import long_to_bytes 5from gmpy2 import iroot 6from sympy import primefactors 7 8# Hastad Boardcast: Multiple unpadded ciphertexts with small e. 9# Use Chinese Remainder Theorem to extract plaintext. 10# Possible since N1*N2*N3 larger than M^e for e = 3. 11 12recipients = [ 13 RSA.importKey(open("german_government.pem").read()), 14 RSA.importKey(open("us_government.pem").read()), 15 RSA.importKey(open("russian_government.pem").read()), 16] 17ciphertexts = [int(l.split(": ")[1]) for l in open("intercepted-messages.txt").readlines()] 18 19# C1 = K mod N1, C2 = K mod N2, C3 = K mod N3 20# K = C1 * N2 * N3 * pow(N2 * N3, -1, N1) + ... (mod N1 * N2 * N3) 21# K % N1 = C1 * N2 * N3 * pow(N2 * N3, -1, N1) = C1 22 23N = 1 24for r in recipients: 25 assert(r.e == 3) 26 N *= r.n 27 28K = 0 29for i in range(3): 30 K += ciphertexts[i] * (N // recipients[i].n) \ 31 * pow(N // recipients[i].n, -1, recipients[i].n) 32K %= N 33 34plaintext, real = iroot(K, 3) 35assert(real) 36 37print(long_to_bytes(plaintext).decode().lstrip("A"))