RSA-common-modulus

import base64
from Crypto.PublicKey import RSA
from Crypto.Util import number

def egcd(b, n):
    (x0, x1, y0, y1) = (1, 0, 0, 1)
    while n != 0:
        (q, b, n) = (b // n, n, b % n)
        (x0, x1) = (x1, x0 - q * x1)
        (y0, y1) = (y1, y0 - q * y1)
    return (b, x0, y0)

if __name__=='__main__':
    pubkey_2='''-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCtbdQAzdaO7GHXxUsVZ+FmcddA
Hrugq+azkVdfgnHu6teK3hDQlk0BdNz9LlQT3BoHXg5/g9FDv3bBwaulpQEQPlGM
UXEUnQAJ69KSVaLxHb5Wmb0vqX/qySKc8Hseqt5wbXklOrnZeHJ3Hm3mUeIplpWP
f19C6goN3bUGrrniwwIDBTy3
-----END PUBLIC KEY-----'''
    pubkey_1 = '''-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCtbdQAzdaO7GHXxUsVZ+FmcddA
Hrugq+azkVdfgnHu6teK3hDQlk0BdNz9LlQT3BoHXg5/g9FDv3bBwaulpQEQPlGM
UXEUnQAJ69KSVaLxHb5Wmb0vqX/qySKc8Hseqt5wbXklOrnZeHJ3Hm3mUeIplpWP
f19C6goN3bUGrrniwwIDAQAB
-----END PUBLIC KEY-----'''
    c1 = base64.b64decode('BzFd4riBUZdFuPCkB3LOh+5iyMImeQ/saFLVD+ca2L8VKSz0+wtTaL55RRpHBAQdl24Fb3XyVg2N9UDcx3slT+vZs7tr03W7oJZxVp3M0ihoCwer3xZNieem8WZQvQvyNP5s5gMT+K6pjB9hDFWWmHzsn7eOYxRJZTIDgxA4k2w=')
    c2 = base64.b64decode('jmVRiKyVPy1CHiYLl8fvpsDAhz8rDa/Ug87ZUXZ//rMBKfcJ5MqZnQbyTJZwSNASnQfgel3J/xJsjlnf8LoChzhgT28qSppjMfWtQvR6mar1GA0Ya1VRHkhggX1RUFA4uzL56X5voi0wZEpJITUXubbujDXHjlAfdLC7BvL/5+w=')
    c1,c2 = int.from_bytes(c1,'big'),int.from_bytes(c2,'big')
    pubkey_1 = RSA.import_key(pubkey_1)
    pubkey_2 = RSA.import_key(pubkey_2)
    ## e diff
    '''
    e1*d1 + phi(n)*k = 1 %(phi(n))
    e2*d2 + phi(n)*k = 1 %(phi(n))

    e1*d1 - e2*d2 = 0 %(phi(n))

    c1 = pow(m,e1,n); m = pow(m,(e1*d1)%phi(n),n)
    c2 = pow(m,e2,n); m = pow(m,(e2*d2)%phi(n),n)

    pow(m,(e1*d1)%phi(n),n) * pow(m,(e2*d2)%phi(n),n)
    pow(m,(e1*d1+e2*d2)%phi(n),n)

    e1*a + e2*b = 1 %(phi(n))
    m = pow(m,(e1*a+e2*b)%phi(n),n) == pow(m,1,n)
    '''
    g,a,b = egcd(pubkey_1.e,pubkey_2.e)
    # print(g,a,b)
    m = (pow(c1,a,pubkey_1.n)*pow(number.inverse(c2,pubkey_1.n),-b,pubkey_1.n))%pubkey_1.n
    print(m.to_bytes((m.bit_length()+7)//8,'big'))
    '''
    Yeah man, you got the message. The flag is W311D0n3! and this is a
    padding to have a long text, else it will be easy to decrypt.
    '''