上一篇介绍了RSA加密算法的一些历史常识及数学知识
这篇文章将通过经典的密码学狗男女Alice和Bob，来介绍RSA加密算法的具体实现办法。
- 如果Alice要给Bob发送信息，又不想直接把加密规则告诉Bob，那么需要怎么做呢？
一，选择两个质数
这里Alice选择了两个质数~
71 和 89
实际中，这两个数字不会这么小的，质数数值越大，破解的难度也就越大
二，计算两个质数的乘积
#这里为了方便公式化，有如下假设
#p = 17, q = 19, n = p*q
17 * 19 = 323
n的长度(二进制)就是密钥长度，323 的密钥长度就是101000011的长度，9位。
实际应用中，RSA的密钥长度为1024,如果安全级别更高则是2048。
第三步，计算n的欧拉函数φ(n)
依据欧拉函数
φ(n) = (p-1)(q-1)
φ(323)=16*18 = 288
第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
我随机选择了 23 ，在规定区间内，且与288互质
第五步，计算e对于φ(n)的模反元素d。
e * d ≡ 1 (mod φ(n))
转换后得到
e * d - 1 = kφ(n)
相当于 求二元一次方程的x,y 解
ex + φ(n)y = 1
将已知量带入,准备求解
23 * x + 288 * y = 1
求解的办法可以参考欧几里得扩展算法，这里不多复述。
python 实现欧几里得扩展
def ext_euclid(a, b):
old_s,s=1,0
old_t,t=0,1
old_r,r=a,b
if b == 0:
return 1, 0, a
else:
while(r!=0):
q=old_r//r
old_r,r=r,old_r-q*r
old_s,s=s,old_s-q*s
old_t,t=t,old_t-q*t
return old_s, old_t, old_r
x = 551, y = -44 是其中的一组解，即 ** d = 551 **
所有计算至此结束
六，封装，将n和e封装成公钥，n和d封装成私钥。
那么Alice 将（n,e)即(323,23) 封装成公钥，(n,d)即(323,551)封装成私钥
实际工程中，公钥和私钥的数据都采用ASN.1格式表达
七，RSA算法安全性的保证依赖于极大整数的分解是非常困难的事情
计算中用到的变量如下:
p -- 质数1
q -- 质数2
n -- 两质数积
φ(n) --欧拉函数值
e -- 随机取值
d -- 模反元素
公钥中用到了(n,e) 其余的四个元素(p,q,d,φ(n))是不公开的。
最关键的是d,如果d泄露，相当于私钥(n,d)泄露。
那么有无可能在知道公钥(n,e)的情况下推导出d呢？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
如果n可以被因数分解，d就可以算出，也就意味着私钥被破解.
但是，但是，大整数因数分解到目前为止，人类的历史记录是：232个十进制位，768个二进制位
就这么说把，1024位的破解还早着呢~
八、加密和解密
有了密钥，就可以进行加密解密了，那么如何实现对密文的非对称加密呢？
1，加密公钥(n,e)
假设bob要向alice发送加密信息m，
他就要用爱丽丝的公钥 (n,e) 对m进行加密。
这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），
且m必须小于n。
所谓加密就是算出下列式子的c
m^e ≡ c (mod n)
alice 的公钥是 (323,23)，Bob的m假设是92，
那么可以有以下等式
92 ** 23 ≡ c (mod 323)
于是 c = 92^23%323 =80
bob 将92加密后得到80，发送给了alice
2,解密要用私钥(n,d)
alice 持有私钥，在接到密文32后，使用私钥(323,551)进行解密。
可以证明，下面的等式一定成立。
c**d ≡ m (mod n)
结合密文和公钥可以得出
80 ** (551) = m (mod 323)
通过以上，得到原文明文
80 ^ (551) % 323 = 92
至此加密解密已经完成。为了演示方便，这里采用了较小的两个质数，
在实际生产中通常都是两个大质数相乘。
有疑问是，如果消息m的大于两质数的积n,那么要怎么办呢？通常有两种办法
①一种是把长信息分割成若干段短消息，每段分别加密
②另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
最后的最后，献上可汗学院的古典密码学和现代密码学，我也是看了这个视频开始接触密码学的。