RSA算法原理（二）：概述

经过上一篇的讲解，相信大家已经与了一定的数学基础，可以开始理解 RSA 算法的原理了。本文重点是介绍 RSA 的原理，尽量让初学者也能理解，并不会做太多高深的数学探讨，太复杂的的数学证明也不会详述，并不会特别严谨（因为笔者也不是专业的数学家 😅）

我们先从 RSA 算法的加密过程说起，然后说下 RSA 算法的原理，最后说下 RSA 的可靠性和优缺点。

在下一篇中，我们还会补充讲解关于 RSA 算法的更多知识。

RSA 算法的加密过程

我们假设 Bob 要和 Alice 发消息，要发送的数据是 m （message 的意思）。

为此，Alice 要先计算出公私玥，然后公开公钥，这样 Bob 才能用公钥来加密，Alice 收到后用私钥进行解密。

公私玥的生成

这里说下公私钥是怎么生成的

1. 首先，Alice 选择一对不相等且足够大的质数，记为 p 和 q
2. 计算 pq 的乘积，记为 n，也就是 p × q = n
3. 计算 n 的欧拉函数，φ(n) = φ(p×q) = φ(p) × φ(q) = (p -1 ) × (q - 1)
4. 随机选取一个与 φ(n) 互质的数 e，并且 1 < e < φ(n)
5. 计算出一个 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）？

1. ed mod φ(n) ≡1 。只有知道 e 和 φ(n)，才能算出 d。
2. 而 φ(n)= (p-1) (q-1)。只有知道 p 和 q，才能算出 φ(n)。
3. 而 n=pq。只有将 n 因数分解，才能算出 p 和 q。

结论：如果 n 可以被因数分解，d 就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

RSA 算法的优缺点

优点：一是安全，即使别人拿到了公钥和密文，也无法解密。二是方便了密钥的管理。公钥是公开的，可以随便发布

缺点：RSA 公钥密码系统存在的主要缺陷是：加密操作和解密操作都涉及到复杂的指数运算，处理速度很慢，较对称密码算法慢几个数量级。与典型的对称加密算法（例如 DES）相比，即使在最理想的情况下，RSA 也要比 DES 慢上 100 倍。

因此，使用 RSA 只能加密少量数据，大量的数据加密还要靠对称密码算法。实际应用中一般用来加密对称算法的密钥，而密文多用对称加密算法加密传输。

举个例子：服务端生成一个非对称加密的密钥对，私钥自己保存，公钥发送给客户端，客户端拿到这个公钥之后，再生成一个对称加密的密钥，然后把对称加密的密钥通过公钥进行加密，加密之后发送给服务端，服务端通过私钥进行解密，这样客户端和服务端就可以通过对称加密进行通信了。

总结

严谨的证明过程不必细致追究，主要是搞清楚 RSA 算法是如何加密和解密的，底层的数学原理是什么。个人建议只要对这些原理性的东西知道个大概就可以了。如果想深入理解需要很强的数学功底，做工程的实在是没必要。

关于加密规则和解密规则是怎么想出来的，这里笔者也不知道，只能说大神是存在的 😄😄😄，而且这也不是本文的重点，欢迎读者留言补充

静下心来，每一步都是我们之前讲过的知识，可能看一次两次看不懂，看多几次总可以的。目前网上的说明基本上我都看不懂，因此自己仔细钻研了 5 天，才略有所得，特地将心得分享出来，希望能帮到读者们。