Add challenge files and solutionHEADmaster

1 files changed, 37 insertions, 0 deletions

diff --git a/solve/solve.py b/solve/solve.py
new file mode 100644
index 0000000..4f38cde
--- /dev/null
+++ b/solve/solve.py
@@ -0,0 +1,37 @@
+#!/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"))