blob: 4f38cded82b222c1dbf6f47065c884e4e1e73e96 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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"))
|
