The RSA common modulus attack

rsa_common_modulus_attack.py

# Some parts of this code is taken from
# https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/

from Crypto.PublicKey import RSA
from base64 import b64decode
from binascii import unhexlify



# load keys (n, e1, e2)
key1 = RSA.importKey(open("key1_pub.pem").read())
key2 = RSA.importKey(open("key2_pub.pem").read())
if (key1.n != key2.n):
    print("Public modulus are different!")
    exit()
n = key1.n
e1 = key1.e
e2 = key2.e
key1 = None
key2 = None



# load messages and change their format to int
c1 = int(b64decode(open("message1").read()).hex(), 16)
c2 = int(b64decode(open("message2").read()).hex(), 16)



# define some useful functions
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
    
def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m



# now, the attack itself

# find the linear combination of exponents
gcd, x, y = egcd(e1, e2) 
assert(e1*x + e2*y == gcd)

# if x or y are negative, this will cause problems with c^x mod n
# but luckily, it can be fixed as follows:
if (x<0):
    x = -x
    c1 = modinv(c1, n)
if (y<0):
    y = -y
    c2 = modinv(c2, n)

# restore the original message
m = pow(c1, x, n) * pow(c2, y, n)
m %= n
print(unhexlify(hex(m)[2:]).decode('ascii'))