RSA算法原理
在量子计算机问世之前再复习一下RSA算法。
RSA算法是一种非对称加密算法，所谓非对称加密是相对于对称加密而言的。
下面了解一下对称加密、非对称加密以及RSA算法。
对称加密
对称加密算法就是A想要发送一段明文msg给B，但是明文发送会被截获不安全怎么办？A就对明文进行了加密，这个加密算法我将它称之为$f()$，故而明文就被加密为$f(msg)$。B收到密文后使用$f()$的逆算法对$f(msg)$解密出明文。这样的加密算法$f()$就称之为对称加密。
对称加密的缺点是：A必须事先将加密算法$f()$告诉B，这个过程就可能被窃听导致加密算法$f()$泄漏，即使是加密算法没有泄漏，还有可以通过分析密文规律从而破解出明文的。
现在的量子保密通信可以实现密钥分发的保密性，可是量子通信技术还远远没有成熟，目前安全的方法还是非对称加密。
非对称加密
B生成一把公钥和一把私钥，公钥可以公布，私钥要保存好。A需要获取B的公钥，A向B发送信息的时候就使用B提供的公钥加密。B收到密文后使用私钥对其进行解密且不能使用公钥而只能使用B所持有的密钥对密文解密，这就是非对称加密。即使别人窃听了密文和公钥也是无法得知明文。
这样只要B的私钥没有泄露，那么信息就是安全的。当然除非使用大算力暴力破解，不过这样做cost是极高的。
RSA算法就是一种典型的非对称加密算法，它的使用范围非常广并且非常安全。
至于为什么叫RSA？因为算法的三个发明者的名字首字母是这个。
RSA算法的密钥长度越长越难破解。
目前普遍使用的是RSA1024和RSA2048。
RSA算法
欧拉函数
欧拉函数基于一个数学概念“互质”，所谓互质就是两个数如果没有除了1之外的公约数那就称这两个数互质。
对于给定的整数n，有多少个从1到n的数和n互质(包含1)，这就是欧拉函数：
$$
\Phi(n)
$$
比如：$\Phi(1)=1$,$\Phi(5)=4$,$\Phi(8)=4$
既然用到了欧拉函数，为了防止混淆，再回顾一下欧拉公式和欧拉方程是什么东西。
欧拉公式
欧拉方程
算法
- 找两个质数p和q
- n = p * q
- 构造欧拉函数：$\Phi(n)=(p-1)(q-1)$
- 找一个整数公钥e，满足1 < e < $\Phi(n)$，并且e要满足与$\Phi(n)$互质。
- 找一个私钥d，满足条件ed除以$\Phi(n)$后余数为1
- 加密：$m^{e}/n$求出余数c，c就是加密后的密文。（m为明文）
- 解密：现在有密文c还有私钥d，$c^d/n$求出余数，这个求得的余数就是明文m。
安全性
发送信息：公钥e，数字n，密文c
解密信息需要：私钥d，数字n，密文c
通过公钥e算出私钥d是否可行？
需要知道$\Phi(n)$,从而又转化为求p和q，n=pq，质因数分解，大数（比如1024位的二进制数或者2048位的二进制数）的质因数分解非常困难。
故而，我们分析出了RSA算法安全的原因，那就是大数的质因数分解非常困难！
