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)
Comments are closed.