RSA算法原理（二）：概述
# 50.RSA算法原理（二）：概述
经过上一篇的讲解，相信大家已经与了一定的数学基础，可以开始理解RSA算法的原理了。本文重点是介绍RSA的原理，尽量让初学者也能理解，并不会做太多高深的数学探讨，太复杂的的数学证明也不会详述，并不会特别严谨（因为笔者也不是专业的数学家😅）
我们先从RSA算法的加密过程说起，然后说下RSA算法的原理，最后说下RSA的可靠性和优缺点。
在下一篇中，我们还会补充讲解关于RSA算法的更多知识。
# RSA算法的加密过程
我们假设Bob要和Alice发消息，要发送的数据是m （message的意思）。
为此，Alice要先计算出公私玥，然后公开公钥，这样Bob才能用公钥来加密，Alice收到后用私钥进行解密。
# 公私玥的生成
这里说下公私钥是怎么生成的
- 首先，Alice选择一对不相等且足够大的质数，记为p和q
- 计算pq的乘积，记为n，也就是 p × q = n
- 计算n的欧拉函数，φ(n) = φ(p×q) = φ(p) × φ(q) = (p -1 ) × (q - 1)
- 随机选取一个与 φ(n) 互质的数e，并且 1 < e < φ(n)
- 计算出一个 e 对于φ(n)的模反元素 d，也就是说 ed mod φ(n) = 1
至此，公私玥都已经生成了。n 和 e 就是公钥，d 和 n 就是私钥。关于p 和 q我们可以不要了。
# 加密数据
有了公玥，就可以对数据进行加密了。
第一步，选取要加密的数据。这里假设明文是m ，这里先声明下，m必须是整数（字符串可以取ascii值或unicode值），且m 必须小于n。如果要加密大于n的整数，该怎么办？有两种解决方法：
- 一种是把长信息分割成若干段短消息，每段分别加密；
- 另一种是先选择一种"对称性加密算法"，用这种算法的密钥加密信息（例如AES），再用RSA公钥加密AES密钥。
第二步，我们求m的e次幂（e指encrypt，可以理解为是密钥），得到 m^e^。
第三步，然后我们将结果对N取模， 最后得到的就是密文，设为 c（cipher，密钥）：m^e^ mod n = c
至此，加密就完成了。之前我们讲过取模运算是不可逆的，所以加密后的 c 是很难反推出原本的明文 m。
小结：加密公式为 m^e^ mod n = c
# 解密数据
Alice收到密文后，如何解密呢？使用这个解密公式：c^d^ mod n = m，这样就能得到明文了。接下来会给出为什么这样就能解密出来的证明。
# 私钥解密的证明
# 公式变换
接下来我们一步步证明解密规则怎么成立： c^d^ mod n = m
首先，密文 c 是是通过 m的e次幂然后对N取模得到的，m^e^ mod n = c ，代入上式
可得 c^d^ mod n = （m^e^ mod n ）^d^ mod n
而根据取模运算的运算规律： (a^b^) mod p = ((a mod p)^b^) mod p
可得：（m^e^ mod n ）^d^ mod n = m^ed^ mod n
而我们说过，d是e对于 φ(n) 的模反元素，也就是说 ed mod φ(n) = 1，因此存在一个整数k，使得ed = kφ(n) + 1，这样 ed mod φ(n) = （kφ(n) + 1） mod φ(n) = 1。
因此 m^ed^ mod n 可以写成： m^kφ(n)+1^ mod n，我们要证明 m^kφ(n)+1^ mod n = m
注：上式也可以转为：（m^kφ(n)^ × m） mod n = （m^kφ(n)^ mod n * m mod n ） = m
接下来，分成两种情况证明上面这个式子。
（1） m 与 n 互质
（2） m 与 n 不互质
# m与n互质
还是根据模的运算规律：(a^b^) mod p = ((a mod p)^b^) mod p
因此，m^kφ(n)^ mod n = （m^φ(n)^ mod n）^k^ mod n，根据欧拉定理， m^φ(n)^ mod n = 1，1的k次方mod n，还是等于1.
因此，（m^kφ(n)^ mod n * m mod n ） = 1 * m mod n = m mod n
最后我们可以得到，m mod n = m 。
为什么m mod n = m？ 因为 m 对 n 取模就是 m ÷ n，而 m < n，因此商为0，余数为m。
# m 与 n 不互质
由于n等于质数p和q的乘积，而m与n不互质，因此得有一个公因数，n的因数只有p和q， 所以m必然等于kp或kq （k是整数）
以 m = tp为例（t为另一个正整数，即使m=tq，也是一样的证明方式），则t与q必然互质，并且由于p,q是素数，tp（也就是m）与q也是互质的。
如果t 与 q不互质，因为q是质数，所以t 只能是q的倍数，假设t = aq，那么m =tp = aqq = an > n，但我们前面说过，m < n。所以t与q互质。
因此根据欧拉定理，这个式子是成立的 ：(tp)^φ(q)^ = m^φ(q)^ ≡ 1 (mod q)
我们两边同时取 kφ(p) 次幂，并根据模运算规律：(a^b^) mod p = ((a mod p)^b^) mod p
可得 （m^φ(q)^）^kφ(p)^ mod q = ( (m^φ(q)^ mod q )^φ(p)^) mod p = 1^φ(p)^ mod p = 1
因此，m^φ(q)kφ(p)^ mod p = 1
而φ(p) * φ(q) = φ(n)， 因此，m^kφ(n)^ ≡1 ( mod q )，
也就是 m^kφ(n)^ mod q = 1，或者说m^kφ(n)^ ÷ q 的余数为1。那么假设商就是r，则有m^kφ(n)^ = rq+1 ，
那么，两边同时乘以m，则由m × m^kφ(n)^ = m(rq+1) ，=tp(1+rq) = tp + tprq = m + trn，
如果我们让 (m + trn) ÷ n，可以得到商为tr，余数为m
那么，也就是m × m^kφ(n)^ mod n= m，也就是 m^kφ(n)+1^ mod n= m，因此，原式得证。
# RSA算法的可靠性
n 和 e 就是公钥，d 和 n 就是私钥，有没可能通过公钥推导出私钥（推导出d）？
- ed mod φ(n) ≡1 。只有知道e和φ(n)，才能算出d。
- 而φ(n)= (p-1) (q-1)。只有知道p和q，才能算出φ(n)。
- 而n=pq。只有将n因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。
# RSA算法的优缺点
优点：一是安全，即使别人拿到了公钥和密文，也无法解密。二是方便了密钥的管理。公钥是公开的，可以随便发布
缺点：RSA公钥密码系统存在的主要缺陷是：加密操作和解密操作都涉及到复杂的指数运算，处理速度很慢，较对称密码算法慢几个数量级。与典型的对称加密算法（例如DES）相比，即使在最理想的情况下，RSA也要比DES慢上100倍。
因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称密码算法。实际应用中一般用来加密对称算法的密钥，而密文多用对称加密算法加密传输。
举个例子：服务端生成一个非对称加密的密钥对，私钥自己保存，公钥发送给客户端，客户端拿到这个公钥之后，再生成一个对称加密的密钥，然后把对称加密的密钥通过公钥进行加密，加密之后发送给服务端，服务端通过私钥进行解密，这样客户端和服务端就可以通过对称加密进行通信了。
# 总结
严谨的证明过程不必细致追究，主要是搞清楚RSA算法是如何加密和解密的，底层的数学原理是什么。个人建议只要对这些原理性的东西知道个大概就可以了。如果想深入理解需要很强的数学功底，做工程的实在是没必要。
关于加密规则和解密规则是怎么想出来的，这里笔者也不知道，只能说大神是存在的😄😄😄，而且这也不是本文的重点，欢迎读者留言补充
静下心来，每一步都是我们之前讲过的知识，可能看一次两次看不懂，看多几次总可以的。目前网上的说明基本上我都看不懂，因此自己仔细钻研了5天，才略有所得，特地将心得分享出来，希望能帮到读者们。
