RSA算法流程

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密(LZ77也是1977年，这一年发生了什么...)。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
秘钥生成流程：
1、随机选择两个不同质数p和q，例如p=5和q=7(实际应用中这两个数越大就越安全)
2、计算n=pq=35。n的长度就是秘钥的长度，35的二进制表示是6位100011，所以秘钥长度为6，实际应用中秘钥长度一般是1024位，重要的场合是2048位。
3、计算n的欧拉函数φ(n)=(p-1)(q-1)=24。
4、随机选择一个元素e，使得1《e《φ(n)，且e和φ(n)互质。假设随机选择了e=5。
5、计算e对φ(n)的模反元素d，ed-1=kφ(n)，5d+(-24k)=1(k取整数)，根据扩展欧几里得算法，一定存在解(d,k)，选择特解(29,6)，也就是d=29。
6、将(n,e)封装为公钥，(n,d)封装为私钥。
加密解密过程：
在上面的例子中，公钥为(35,5)，私钥为(35,29)。
假设对m加密得密文c，则m^e≡c(mod n)，c^d≡m(mod n)。