RSA加密

场景

人物：卧底余罪、警长老许、毒枭老傅
事件：老许安排余罪潜伏到老傅的身边

RSA是什么？

RSA是一种非对称加密算法，是目前最好的加密方法。非对称加密又叫公钥加密，也就是说成对的密钥，其中一个是对外公开的，所有人都可以获得，称为公钥，而与之相对应的称为私钥，只有这对密钥的生成者才能拥有。这是警局成立初期一直在延用的一个加密算法。

RSA能干啥

余罪发现老傅近期有一次毒品贩卖活动，需要将信息汇报给老许，让其安排抓捕行动。为了防止信息被窃听，需要使用RSA对信息进行加密。

RSA加密规则

在卧底行动以前，警局需要制作本次行动的RSA秘钥，一个公钥，一个私钥。根据RSA的规范，分以下几步进行生成

1. 随机选择两个不相等的质数p和q。 老许选了 17 和 11，既p=17, q=11；
2. 计算两个数的乘积n。既n = 17x11 = 187；
3. 计算n的欧拉函数φ(n)。φ(n) = (p-1)x(q-1) = (17-1)x(11-1) = 160；
4. 选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。老许就在1到160之间选择了37；
5. 到此公钥已经生成，既（n, e) = (187, 37)。下面生成私钥；
6. 计算e对于φ(n)的模反元素d（模反元素存在，当且仅当e与φ(n)互质）。根据模反元素的计算公式，既解下面的二元一次方程，ed+φ(n) n=1，既。
   37d+160n = 1;

我是通过下面的python脚步计算出的，方法比较局限。如果有更好的解二元一次方程的方法欢迎留言。
大概思路：
第一步：37d+160n = 1，既37d-1=-160n。
第二步：假设d为正整数，d落在[0, 100]区间内。
第三步：将区间内的每一个整数依次赋予d，判断37乘d 加1 或 减1 余160 是否为0。如果余0，根据当前d就可以求出一组[d, n]的整数解。
第四步：如果[0, 100]区间内没有找到结果，可以扩大区间，重复第三步。
def jisuan(a, b):
    d=0
    while(d<100):
       d+=1
        if((a*i-1)%b==0 or (a*i+1)%b==0):
            print d

7. 二元一次方程可能会有很多个整数解，这里选择了求出的第一组整数解(d, n) = (13, -3)
8. 至此公钥和私钥都已生成。公钥（n, e）= (187, 37)。私钥（n, d) = (187，13)
9. 私钥会留在老许的手里，其他人谁又不知道。公钥会给到余罪用于发送情报

RSA怎么用

余罪要向老许发送情报k，首先要用公钥对k进行加密。这里需要注意，k必须是整数（字符串可以取ascii值、unicode值），且k必须小于n。

所谓"加密"，也就是根据以下公式计算出密文
密文= k 的 e次方 模 n

根据计算公式，这是python的实现

miwen=pow(k, e, n)

最后将密文发送给老许，老许收到后使用私钥进行解密，操作和加密类似
明文= miwen 的 e次方 模 n

根据计算公式，这是python的实现

k=pow(miwen, d, n)

可以看出如果没有私钥d ，即使得到了miwen，也是无法解析的。

公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥， 这里推荐第二种，网易云音乐也是使用的第二种方案。