blob: aa7e1bbf999655a8f303ff6b7b7bab58b28472e2 (
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
|
#!/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())
|
