这篇文章主要介绍rsa算法的python实现示例，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
'''
Created on 2012-11-5
@author: Pandara
'''
import math
import random
import sys
def is_prime(num):
'''
determine wether num is prime
'''
for i in range(int(math.floor(float(num) / 2)) + 1)[2:]:
if num % i == 0:
return False
return True
def random_prime(low = 0, high = 100):
'''
to get prime randomly
low: lower bound of range
high: higher bound of range
'''
rand = random.randint(low, high)
while(True):#is prime or not
if not is_prime(rand):
rand = (rand + 1) % (high - low) + low
else:
return rand
def gcd(a, b):
'''
get gcd from a and b
'''
if a < b:
a, b = b, a
while b:
a, b = b, a % b
return a
def egcd(a,b):
'''
Extended Euclidean Algorithm
returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
'''
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def modInverse(e,n):
'''
d such that de = 1 (mod n)
e must be coprime to n
this is assumed to be true
'''
return egcd(e,n)[0]%n
def generate_key(e):
p = random_prime(1000, 2000) #get p and q, to make p and q big enough
q = random_prime(1000, 2000) #such that e < euler_n
n = p * q #n equal to p * q
euler_n = (p - 1) * (q - 1) #euler(n) = (p - 1)(q - 1)
#adjusting e
while gcd(euler_n, e) != 1:
e += 2 #keep it odd
d = modInverse(e, euler_n)
return e, d, n
def rsa_encrypt(e, n, msg):
'''
e: such that ed mod(n) = 1, public, chosen
n: equal to p * q
msg: needs encrypting
return: list with dicimal digits, from elements in msg after encrypted
'''
cmsg = []
for elem in msg:
cmsg.append(pow(ord(elem), e, n))
return cmsg
def rsa_dencrypt(d, n, cmsg):
'''
d: such that ed mod(n) = 1, private, calculated
n: equal to p * q
cmsg: list with dicimal digits, from elements in msg after encrypted
'''
msg = []
for elem in cmsg:
msg.append("%c" % pow(elem, d, n))
return "".join(msg)
if __name__ == "__main__":
while(True):
print "##############menu###############"
print "1.generate keys"
print "2.encryption"
print "3.decryption"
print "other for quit"
chose = input("input your choice:")
if chose == 1:
e, d, n = generate_key(65537)
print "generate keys as follow:"
print "e = %d, d = %d, n = %d" % (e, d, n)
print "public key(e, n) = (%d, %d), private key(%d, %d)" % (e, n, d, n)
elif chose == 2:
msg = raw_input("input your message:")
e, n = input("input the public key(with format \"e,n\"):")
sys.stdout.write("ciphertext:")
for elem in rsa_encrypt(e, n, msg):
sys.stdout.write(" %d" % elem)
sys.stdout.write("\n")
elif chose == 3:
cmsg_str = raw_input("input your ciphertext:")
d, n = input("input the private key(with format \"d,n\"):")
cmsg = []
for elem in cmsg_str.split(" "):
cmsg.append(long(elem))
print "plaintext:", rsa_dencrypt(d, n, cmsg)
else:
break尚未解决的问题：如何利用扩展欧几里得算法求模逆元？即egcd及modInverse的实现
以上是“rsa算法的python实现示例”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！
