RSA算法python实现

dsqzhaoyue

　　RSA算法是一种非对称加密算法，是现在广泛使用的公钥加密算法，主要应用是加密信息和数字签名。详情请看维基：http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
　　算法基本思路：
　　1.公钥与私钥的生成：
　　(1)随机挑选两个大质数 p 和 q，构造N = p*q；
　　(2)计算欧拉函数φ(N) = (p-1) * (q-1)；
　　(3)随机挑选e，使得gcd(e, φ(N)) = 1，即 e 与 φ(N) 互素；
　　(4)计算d，使得 e*d ≡ 1 (mod φ(N))，即d 是e 的乘法逆元。
　　此时，公钥为（e, N），私钥为（d, N），公钥公开，私钥自己保管。
　　2.加密信息：
　　(1)待加密信息（明文）为 M，M < N；（因为要做模运算，若M大于N，则后面的运算不会成立，因此当信息比N要大时，应该分块加密）
　　(2)密文C = Me mod N
　　(3)解密Cd mod N = (Me)d mod N = Md*e mod N ；
　　要理解为什么能解密？要用到欧拉定理（其实是费马小定理的推广）a&phi;(n) &equiv; 1 (mod n)，再推广：a&phi;(n)*k &equiv; 1 (mod n)，得：a&phi;(n)*k+1 &equiv; a (mod n)
　　注意到 e*d &equiv; 1 mod &phi;(N)，即：e*d = 1 + k*&phi;(N)。
　　因此，Md*e mod N = M1 + k*&phi;(N) mod N = M
　　简单来说，别人用我的公钥加密信息发给我，然后我用私钥解密。
　　3.数字签名：
　　(1)密文C = Md mod N
　　(2)解密M = Ce mod N = (Md)e mod N = Md*e mod N  = M ；（原理同上）
　　简单来说，我用自己的密钥加密签名，别人用我的公钥解密可以看到这是我的签名。注意，这个不具有隐私性，即任何人都可以解密此签名。
　　
　　算法的安全性：基于大整数N难以分解出p和q，构造&phi;(N)；或由N直接构造&phi;(N)同样难。
　　
　　算法的实现：
　　1.快速幂取模；http://www.iyunv.com/7hat/p/3398394.html
　　2.素性测试；http://www.iyunv.com/7hat/p/3400831.html
　　3.扩展欧几里得求乘法逆元和最大公约数；http://www.iyunv.com/7hat/p/3406494.html
　　实现代码：





import random
def fastExpMod(b, e, m):
"""
e = e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n)
b^e = b^(e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n))
= b^(e0*(2^0)) * b^(e1*(2^1)) * b^(e2*(2^2)) * ... * b^(en*(2^n))
b^e mod m = ((b^(e0*(2^0)) mod m) * (b^(e1*(2^1)) mod m) * (b^(e2*(2^2)) mod m) * ... * (b^(en*(2^n)) mod m) mod m
"""
result = 1
while e != 0:
if (e&1) == 1:
# ei = 1, then mul
result = (result * b) % m
e >>= 1
# b, b^2, b^4, b^8, ... , b^(2^n)
b = (b*b) % m
return result
def primeTest(n):
q = n - 1
k = 0
#Find k, q, satisfied 2^k * q = n - 1
while q % 2 == 0:
k += 1;
q /= 2
a = random.randint(2, n-2);
#If a^q mod n= 1, n maybe is a prime number
if fastExpMod(a, q, n) == 1:
return "inconclusive"
#If there exists j satisfy a ^ ((2 ^ j) * q) mod n == n-1, n maybe is a prime number
for j in range(0, k):
if fastExpMod(a, (2**j)*q, n) == n - 1:
return "inconclusive"
#a is not a prime number
return "composite"
def findPrime(halfkeyLength):
while True:
#Select a random number n
n = random.randint(0, 1