RSA Common modulus attack

common_modulus.py

import argparse
import math
from binascii import unhexlify



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):
    return pow(a, -1, m)


def attack(c1, c2, e1, e2, N):
    if math.gcd(e1, e2) != 1:
        raise ValueError("Exponents e1 and e2 must be coprime")
    s1 = modinv(e1, e2)
    s2 = (math.gcd(e1, e2) - e1 * s1) // e2
    temp = modinv(c2, N)
    m1 = pow(c1, s1, N)
    m2 = pow(temp, -s2, N)
    return (m1 * m2) % N


def main():
    args = parser.parse_args()
    print('[+] Started attack...')
    try:
        message = attack(args.ct1, args.ct2, args.e1, args.e2, args.modulus)
        print('[+] Attack finished!')
        print('\nPlaintext message:\n%s' % unhexlify(hex(message)[2:])) 
        # format(message, 'x').decode('hex'))
    except Exception as e:
        print('[+] Attack failed!')
        print(e.message)


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description='RSA Common modulus attack')
    required_named = parser.add_argument_group('required named arguments')
    required_named.add_argument('-n', '--modulus', help='Common modulus', type=int, required=True)
    required_named.add_argument('-e1', '--e1', help='First exponent', type=int, required=True)
    required_named.add_argument('-e2', '--e2', help='Second exponent', type=int, required=True)
    required_named.add_argument('-ct1', '--ct1', help='First ciphertext', type=int, required=True)
    required_named.add_argument('-ct2', '--ct2', help='Second ciphertext', type=int, required=True)

    main()

Updates for upstream to support Python 3, added some code to allow me to import it as a module, instead of passing in parameters (so I could manipulate the m, e from a PEM file! :-)

I ran into some problems on line 35, format(message, 'x') returns a string and str object has no attribute decode in python3, my solution is:

from binascii import unhexlify
unhexlify(hex(message)[2:])

BTW, my python version is 3.9.7 and my test message is 8114814712001183532010470067837

Thanks for updating the gist! I ran into the same issue on line 35 and @senventise solution worked flawlessly 🎉 .

how do you run with values?

I ran into some problems on line 35, format(message, 'x') returns a string and str object has no attribute decode in python3, my solution is:

from binascii import unhexlify
unhexlify(hex(message)[2:])

BTW, my python version is 3.9.7 and my test message is 8114814712001183532010470067837

Not sure how I missed this a year ago, but I updated - but haven't tested yet (I always ran from an import). Commented out previous. Thanks!

how do you run with values?

Either import the file and use the functions in your code, or run from the command line and pass in the parameters. 👍