No Huddle Offense

"Individual commitment to a group effort-that is what makes a team work, a company work, a society work, a civilization work."

RSA implemented in Python

March 31st, 2011 • Comments Off on RSA implemented in Python

Just needed to work through some algorithms lately. Best book/reference in that area is most probably the third edition of Introduction to Algorithms. Here is some python code with references to the pages in this book describing the RSA algorithm:

#!/usr/bin/python

def euclid(a, b):
    """
    Taken from page 935
    """

    if b == 0:
        return a
    else:
        return euclid(b, a % b)

def extended_euclid(a, b):
    """
    Taken form page 937
    """
    if b == 0:
        return [a, 1, 0]
    else:
        previous_d, previous_x, previous_y = extended_euclid(b, a % b)
        d, x, y = (previous_d, previous_y, previous_x - a // b * previous_y)
        return [d, x, y]

def generate_keys(p, q):
    """
    Generation of public and private keys...
    """

    n = p * q
    m = (p - 1) * (q - 1)

    e = long(2)
    while e < m:
        if euclid(e, m) == 1:
            break
        else:
            e = e + 1

    dd, x, y = extended_euclid(m, e)
    if y > 0:
        d = y
    else:
        d = y % m

    return [(e, n), (d, n)]

def rsa(p, q, msg):
    """
    RSA walkthrough - Taken from page 962
    """
    pub_key, priv_key = generate_keys(p, q)

    print 'Public Key: ', pub_key
    print 'Private Key: ', priv_key

    e, n = pub_key
    d, n = priv_key

    crypted = (msg ** e) % n
    print 'Crypted value is: ', crypted

    original = crypted ** d % n
    print 'The original number was: ', original

if __name__ == "__main__":
    p = long(raw_input('First prime: '))
    q = long(raw_input('Second prime: '))

    msg = long(raw_input('Number to test rsa with: '))

    rsa(p, q, msg)

Comments are closed.