## RSA implemented in Python

March 31st, 2011 • Comments Off on RSA implemented in PythonJust 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)