common mod

rsa.py

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
 
a = RSA.importKey(open("/tmp/key1_pub.pem").read())
b = RSA.importKey(open("/tmp/key2_pub.pem").read())
 
m1 = int(open("/tmp/message1","rb").read().decode("base64").encode("hex"), 16)
m2 = int(open("/tmp/message2","rb").read().decode("base64").encode("hex"), 16)
 
assert(a.n == b.n)
 
def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
 
 
def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m
 
gcd, aa, bb = extended_gcd(a.e, b.e)
 
if aa < 0:
    m1 = modinv(m1, a.n)
    aa = -(aa)
 
if bb < 0:
    m2 = modinv(m2, b.n)
    bb = -(bb)
 
m = (pow(m1, aa, a.n) * pow(m2, bb, b.n))%a.n
print long_to_bytes(m)