RSA算法python实现

RSA算法是一种非对称加密算法，是现在广泛使用的公钥加密算法，主要应用是加密信息和数字签名。详情请看维基：http://zh./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 = M^e mod N

(3)解密C^d mod N = (M^e)^d mod N = M^d*e mod N ；

要理解为什么能解密？要用到欧拉定理（其实是费马小定理的推广）a^φ(n) ≡ 1 (mod n)，再推广：a^φ(n)*k ≡ 1 (mod n)，得：a^φ(n)*k+1 ≡ a (mod n)

注意到 e*d ≡ 1 mod φ(N)，即：e*d = 1 + k*φ(N)。

因此，M^d*e mod N = M^{1 + k*φ(N)} mod N = M

简单来说，别人用我的公钥加密信息发给我，然后我用私钥解密。

3.数字签名：

(1)密文C = M^d mod N

(2)解密M = C^e mod N = (M^d)^e mod N = M^d*e mod N  = M ；（原理同上）

简单来说，我用自己的密钥加密签名，别人用我的公钥解密可以看到这是我的签名。注意，这个不具有隐私性，即任何人都可以解密此签名。

 

算法的安全性：基于大整数N难以分解出p和q，构造φ(N)；或由N直接构造φ(N)同样难。

 

算法的实现：

1.快速幂取模；http://www.cnblogs.com/7hat/p/3398394.html

2.素性测试；http://www.cnblogs.com/7hat/p/3400831.html

3.扩展欧几里得求乘法逆元和最大公约数；http://www.cnblogs.com/7hat/p/3406494.html

实现代码：

Python