forked from jvdsn/crypto-attacks
-
Notifications
You must be signed in to change notification settings - Fork 0
/
hastad_attack.py
29 lines (23 loc) · 893 Bytes
/
hastad_attack.py
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
import os
import sys
from math import gcd
path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
sys.path.insert(1, path)
from attacks.rsa import low_exponent
from shared.crt import fast_crt
def attack(N, e, c):
"""
Recovers the plaintext from e ciphertexts, encrypted using different moduli and the same public exponent.
:param N: the moduli
:param e: the public exponent
:param c: the ciphertexts
:return: the plaintext
"""
assert e == len(N) == len(c), "The amount of ciphertexts should be equal to e."
for i in range(len(N)):
for j in range(len(N)):
if i != j and gcd(N[i], N[j]) != 1:
raise ValueError(f"Modulus {i} and {j} share factors, Hastad's attack is impossible.")
c, _ = fast_crt(c, N)
return low_exponent.attack(e, c)