rsa.py

def mod(x, y, z):
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number


def egcd(a, b):
        u, u1 = 1, 0
        v, v1 = 0, 1
        g, g1 = a, b
        while g1:
                q = g // g1
                u, u1 = u1, u - q * u1
                v, v1 = v1, v - q * v1
                g, g1 = g1, g - q * g1
        return u, v,


def test(p, q, e, message):
    print 'try with p is', p, 'q is', q
    n = p * q
    euler = (p - 1) * (q - 1)
    ''' d^e = 1 mod euler '''
    x, _ = egcd(e, euler)
    print 'plain message', message
    d = euler + x
    print 'public key is', e, n
    print 'private key is', d, n
    encrypted_message = mod(message, e, n)
    print 'encrypt', encrypted_message
    decrypted_message = mod(encrypted_message, d, n)

    print 'decrypt', decrypted_message
    print
    assert message == decrypted_message

test(3557, 2579, 3, 123456)
test(
    0x87c296ed480f9ab17885decd31197d617779c0dac70c3234996e1,
    0x4fa84812157119acc8ecca98c404b2e5ee24ce18f60ea818091895,
    0x10001,
    int('The Secret Message'.encode('hex'), 16))