common modulus attack steps

241.py

from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse
from binascii import hexlify,unhexlify
from base64 import b64decode

# STEP 1 => import the public keys and get both moduli (n1,n2) and exponents (e1,e2)
key1 = RSA.import_key(open('key1.pem').read())
key2 = RSA.import_key(open('key2.pem').read())

n1,n2,e1,e2 = key1.n, key2.n, key1.e, key2.e

assert n1 == n2, 'Not a common modulus'

# STEP 2 => Equation: a1e1 + a2e2 = 1
# a1 = Modular inverse of e1 and e2. solve for both a1 and a2
# a2 = (1 - modinv(e1,e2)*e1)/e2

a1 = inverse(e1, e2)
a2 = (1 - (a1 * e1)) / e2

assert (a1*e1) + (a2*e2) == 1, 'Wrong Values for a1 and a2'

#STEP 3 => solve for message: formula: m = [(c1**a1 mod n1) * (c2**a2 mod n1)] mod n1
#c1 and c2 are the respective ciphertexts in long int formats

c1 = int(hexlify(b64decode(open('message1').read())),16)
c2 = int(hexlify(b64decode(open('message2').read())),16)

# solve for each segment of the above equation separately
# c1 ** a1 mod n1

r1 = pow(c1,a1,n1)

#solve for c2**a2 mod n1
tmp2 = pow(c2,-1,n1) # first solve the inverse of c2 modulo n1 then raise the result to positive a2
r2 = pow(tmp2,abs(int(a2))) #converting a2 from float to int and returning its positive value

#solve the overall equation
decrypted_message = (r1*r2) % n1 #long int
final_message = unhexlify(hex(decrypted_message)[2:]) # slice to remove the 0x else: error Non-hexadecimal digit found
print(final_message)