# 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)
```