1 files changed, 29 insertions, 0 deletions
diff --git a/solve/solve.py b/solve/solve.py
new file mode 100644
index 0000000..aa7e1bb
--- /dev/null
+++ b/solve/solve.py
@@ -0,0 +1,29 @@
+#!/usr/bin/env python3
+
+from Crypto.PublicKey import RSA
+from Crypto.Util.number import long_to_bytes
+from math import isqrt, inf
+from tqdm import tqdm
+
+pubkey = RSA.importKey(open("pubkey.pem").read())
+
+# Primes close to sqrt(N) can be found quickly with Fermat factorization.
+
+a = isqrt(pubkey.n)+1
+prog = tqdm(total=inf)
+has_sqrt = lambda n: isqrt(n)**2 == n
+while not has_sqrt(a * a - pubkey.n):
+    prog.update()
+    a += 1
+prog.close()
+b = isqrt(a * a - pubkey.n)
+
+p = a + b
+q = a - b
+phi = (p-1)*(q-1)
+d = pow(pubkey.e, -1, phi)
+
+ciphertext = int(open("message.txt").read())
+plaintext = pow(ciphertext, d, pubkey.n)
+
+print(long_to_bytes(plaintext).decode())