https://www.youtube.com/watch?v=sYCzu04ftaY

primes.py

from fractions import gcd

from Crypto.PublicKey import RSA
from Crypto.Signature import PKCS1_v1_5
from Crypto.Hash import SHA


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):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("mod inverse does not exist")
    else:
        return x % m


def get_public_keys():
    """ Returns a list of RSA public Keys Some of them have the same p value(!) """
    return {
        "Alice":
        0x00c90e4c65c0a96080df5aaf73caaf1146afb364cb37894f6bb745182191bf577a2777d8b5dbf57b2ad9f902e2d3abadfe6ebeb7366d7b11f0cbfd4371dbadf5f548e60644b3365a654b8efe2de32bbb1cc0288d367c0e8cf9ac8a2544cb067f677c87e82362e3b3ce950d072c5b1baffd650a31db4ff7d7209f0aec0178d7ba8b,
        "Bob":
        0x00db87e4a4774c4c4606faadeb58460d6c62282aced115ae9d256d6ca2d32b49615c9257869aa0b1757b8faaae401f94474ddbf5f54b75dfaa7bef370cc9842a920ff9484cabacece44e7c2c80c2c97775a39d035c59475db93374cbac0d0e4f0830bcc51fe4680ef1d8afce89d61ef7a1fe8f03dd26a7049303f1cbfa94b10323,
        "Carl": 0x00a8e4fe8ddca1a4b8c97376d90e43e78f9df822412215511fa3efc3f96b34c6bdc2090dbbfce2e118ff8168c6ba1ed965f743238467310c97d22918c4549d9c426641469a57ed75557367ad37d3c73485a5d748bbcea211897f72f60e7fbd6bb220e6e56e466dcc3144abb78388865ee5c9bba879ea96c0a2522bdb63383f3591,
        "David":
        0x00b7a2434673e546ff4d7975166a5228e19aa5b43ab79e147f27695aeeeb197bb3152ef1df0b8190a7304b4db49cffdf6f0cdd168f47594d2fd0672787716ae519bf78df1cb96c0968785e7f0ec7de1008644b3cc32c74748f0d0967cdc76b7bba0cb78a15858bcc40063e53c34bb47cf63ba2eb8af3d491131f2aa96388802677,
        "Edward":
        0x00b7882ac1f039ce5c9cef7a66800d2247c465cd5bcbaa80cc48ba34ec2759280a666432f78f53d222a308ea2dc7d455be7d050faeca3fd9847fb43dbaf2a09013778e238b7a79430271c105cb959f3ff4d0e72a756ecc948bc27e1b1dc7dafb3fae6e31c2571c89f06ac854cac98d10e106ec89abd4d093f28e13db54ea8798b3,
        "Fleur":
        0x00cec274724b04bda96d51162abf710fbf1eedb978aa87639e61a166b772cf4bdfc8fdddb3b700b366d68767a5d33cce4e6146fe325de5d9d0dc480dbd4201c3859d1debbf952a1e3a10c0cfeb6413f740748c7a43a346d895c12bf7b14068df33be376b12527b1c7fb390f95d0f878ebb8a38c621eb415a85bf42b9cbcaccc749,
        "Gary":
        0x00bdb08ad1d97628b0d4e9bdcdb0303007e66b9d82b3ca3e7df476911f1d0ffd81f67487b4fafc4e252b30c501055335ab74f1e92e411615b5263d5117daf715740f826a6f8faba2620ddda2852a3595aa9f051d3e0b46766440360f986cc2db7b7f2d9431e9324280109ac1ed43900a57531ee2878e895c6f5b4ba4311051413d,
    }


def get_greatest_common_divisor(key1, key2):
    return gcd(rsa_pkeys[name1], rsa_pkeys[name2])


def reconstruct_private_key(n, p, q):
    e = 65537  # commonly used value
    d = modinv(e, n - (p + q - 1))

    return RSA.construct((n, long(e), d, p, q))


def sign_message(key, text):
    h = SHA.new(text)
    signer = PKCS1_v1_5.new(key)

    return signer.sign(h)

def verify_message(username, text, signature):
    key = RSA.construct((rsa_pkeys[username], long(65537)))
    h = SHA.new(text)
    signer = PKCS1_v1_5.new(key)

    return signer.verify(h, signature)

if __name__ == "__main__":
    rsa_pkeys = get_public_keys()

    for name1 in rsa_pkeys:
        for name2 in rsa_pkeys:
            if name1 != name2:
                cd = get_greatest_common_divisor(
                    rsa_pkeys[name1], rsa_pkeys[name2])
                if cd != 1:
                    print "[+] {} Has a weak public key".format(name1)
                    #print "{} and {} share the same common divisor of {}".format(name1, name2, cd)
                    n = rsa_pkeys[name1]
                    p = cd
                    q = n / p

                    key = reconstruct_private_key(n, p, q)

                    signed_message = sign_message(key, 'admin')

                    print "\nSigned message as {}: {}\n".format(name1, signed_message.encode('hex'))
                    print "Verifies using public key? {}\n\n".format(verify_message(name1, 'admin', signed_message))