RSA 加密算法及其数学思想

AI Generated Abstract

RSA 加密算法是一种非对称加密方法，其核心思想基于数论中的欧拉定理和大素数分解的困难性。本文从 RSA 的基本原理出发，详细介绍了其加密与解密过程，并通过数学证明验证了其正确性。此外，文章深入探讨了 RSA 的设计思想，包括恒等映射的构造、模数选择的策略以及安全性分析，帮助读者全面理解 RSA 算法的数学本质与应用场景。

像 DES 以及 AES 还有那些经典的古典加密算法，都属于对称密码体制，加密和解密必须要使用同一套密钥。这样一套对称的密码系统，发送信息和接收信息的双方都要掌握这个密钥才能加密和解密，任何一方泄露了密钥，数据的安全就会遭到威胁。

RSA 算法是 1977 年由 Ron Rivest, Adi Shamir, Leonard Adleman 提出的公钥密码体制 (public-key cryptosystem)，公钥密码体制也称非对称密码体制 (asymmetric cryptosystem)。

在公钥密码体制中，加密密钥与解密密钥是不同的，加密密钥简称公钥 (public key)，是可以公开的，解密密钥简称私钥 (private key)，是需要被保护的。

在一些场合下，比如说消息接收者在一个安保措施非常好的军事中心，而消息发送者是散布在世界各地的探员，我们可以只告诉这些探员公钥，他们只知道如何利用它加密，而不知道如何解密，就算被抓了，也无法威胁这套加密系统的安全性，因为能破译这些消息的人只有受到严格保护的拥有私钥的人。这也是这套非对称加密系统的强大之处。

看了看网上很多关于 RSA 的文章，也看了白洪欢的密码学讲义，甚至还翻了翻《离散数学及其应用》，发现对 RSA 的讲解都是证明完其正确性就点到为止了。

但是显然 RSA 的精髓是其构造过程，其设计思想。在我看来，光证明其正确性没有任何意义。除了知道它是对的，不能带来任何收获。

这篇文章除了简单的介绍 RSA 算法的过程，并对其正确性做一个数学证明，还会从构造法的角度仔细讨论 RSA 的核心设计思路。这个思路并不复杂，只要对基本的数论知识有所了解，就很容易顺着逻辑走通。文章会涉及到一些比较基础的数论知识，如果对相关知识不太熟悉，可以参考：RSA 中的数论知识。

基本模式¶

随机选择两个不等的大素数 p 和 q。
计算出 n=p*q。
挑选一个数 e，使得它和 (p-1)(q-1) 互素。
计算 e 在模 (p-1)(q-1) 意义下的逆元 d。
公开（e,n）作为公钥。
保留（d,n）作为私钥。
加密一个数 M：$Cipher=M^e\ \ (mod\ n)$
解密一条密文：$Plaintext=Cipher^d\ \ (mod\ n)$

分析¶

RSA 算法保证：在公开 e 和 n 的情况下，对于满足一定条件（小于 n，不被 p 和 q 整除）的 M，任何人都可以通过$Cipher=M^e \ mod\ n$ 来对 M 加密。通过保存的私钥 d 可以恢复：$Plaintext=Cipher^d\equiv M\ (mod\ n)$。

RSA 中，n 是两个大素数 p 和 q 的乘积，e 是挑选出来的一个与 (p-1)(q-1) 互素的数 e，d 是 e 在模 (p-1)(q-1) 意义下的乘法逆元。

这个设计非常的讲究，要理解其意义，我们先要能证明，上述解密变换的正确性。

变换的正确性¶

$M^{ed} \equiv M \ \ (mod \ n)$

\[ 已知 ed \equiv 1 \ [mod \ (p-1)(q-1)] \]

\[ 则 ed=k(p-1)(q-1)+1 \]

\[ M^{ed}=M * M^{ k(p-1)(q-1) } \]

由费马小定理：$ p 为素数，若 a 不能被 p 整除，则 a^{p-1} \equiv 1 \ (mod\ p) $

\[ 则只要 M 既不是 p 也不是 q 的倍数：M^{ed} \equiv M \ (mod\ p) \ \ ; \ \ M^{ed} \equiv M \ (mod \ q) \]

\[ M^{ed}-M \equiv 0 \ (mod \ p) \]

\[ M^{ed}-M \equiv 0 \ (mod \ q) \]

由中国剩余定理：

\[ 正整数 m_1,m_2,m_3,......,m_n 两两互素，a_1,a_2,a_3,......,a_n 是任意整数。 \]

\[ x \equiv a_1 \ (mod\;m_1) \]

\[ x \equiv a_2 \ (mod\;m_2) \]

\[ ...... \]

\[ x\equiv a_n(mod \ m_n) \]

\[ 有唯一的模 m=m_1m_2......m_n 的解。 \]

\[ 令 M_k=\frac{m}{m_k},M_k 在模 m_k 意义下的乘法逆元为 y_k[即 M_ky_k\equiv1\;(mod\;m_k)] \]

\[ x=a_1M_1y_1+...+a_nM_ny_n. \]

\[ 由于 p 和 q 互素。 \]

\[ 因此，M^{ed}-M \equiv 0 * (..) + 0 * (..) \equiv 0 \ (mod\ n) \]

得证 $M^{ed}\equiv M \ (mod\ n)$

设计思想¶

前面我们给出了 RSA 正确性的简单证明，可以看到如何证明 RSA 的正确性并不是一件困难的事。但是会证明 RSA 的正确性，只能说明你知道 RSA“为什么对”，但是你可能并无法理解其真正的设计思想。

在 RSA 的设计中，我们发现有两个关键的要素：大素数 p 和 q，(p-1)(q-1)。既然取了 n=pq，为什么还要取 (p-1)(q-1)，为什么要取一个与之互素的 e，逆元 d 又是为了什么？在我看来，只有能够回答上面这些问题，才能真正算得上对 RSA 有所理解。

这一小节，我们将会针对 RSA 的设计思想做一个简单的讨论。

RSA 非对称加密的核心特征

其实 RSA 所谓的非对称无非就是利用了这样一个性质：

\[ M^{ed}\equiv M\ (mod\ n) \]

这是一个怎样的性质呢？这其实就是一个恒等映射的性质：一个数字被幂函数变换后，总是等于自己。。。这里的函数$f(x)=x^{ed}$就是在模 n 的剩余系中的一个恒等映射罢了。

恒等映射？恒等映射意味着什么呢？

无论什么加密系统，对于加密函数$En(x)$和解密函数$De(x)$来说，它们的复合：$En \cdot De$ 其实都是恒等映射。。。反过来讲，任何一个恒等映射，只要能被写成一对函数复合的形式，那么这对函数就可以分别作为加密函数和解密函数。。。

巧了，这里的$f(x)=x^{ed}$正好就可以做这样的分解：$x^e 和 x^d$。。。所以这对函数就能用来加解密。。

传统的对称加密，使用的一对加解密函数依赖于相同的密钥。但是这里函数的参数 e 和 d 可能是不同的，因此加解密依赖不同的密钥，所以就是非对称的。
恒等映射怎么来的？

了解了所谓的非对称加密的本质后。我们第二个问题自然是：这个恒等映射是怎样的？

对于 RSA，它采用了幂函数的形式。

那么我们就来考察一下：幂函数的指数应该满足什么条件才能让这个映射在特定的剩余系中是一个恒等映射呢？

\[ a^x\equiv a\ (mod\ n) \]

看到这个形式，很容易想到费马小定理，或者欧拉定理。

前者给出：

\[ a^{p-1}\equiv1\ (mod\ p) \]

后者给出：

\[ a^{\Phi(n)}\equiv 1\ (mod\ n) \]

当然，很显然，前者是后者的一个特例。

欧拉定理的条件很宽松，只要求 a 和 n 互素。而一般来说，n 取一个素数，a 如果小于 n，那么这个条件一定满足。或者 n 的素因子很少，且都很大，a 比任意一个素因子都小，那么这个条件也一定能满足。

那么我们要构造这样的一个恒等映射再容易不过了，找一个比较好的 n，指数 x 取$k*\Phi(n)+1$就行了。
如何分解？

我们在一开始说了，一套密码系统，首先要有个恒等映射，其次这个恒等映射要可分解。

所以对于我们找到的 n，它的欧拉函数必须要保证 $k*\Phi(n)+1=ed$ 这样的分解是可操作的。

换句话说：$ed\equiv1\ [mod\ \Phi(n)]$

再换句话说，e 和 d 再模$\Phi(n) $意义下互为乘法逆元？

卧槽？这句话是不是很耳熟？RSA 不是求了 e 在模 (p-1)(q-1) 意义下的逆元 d 么？

但是你自己想想 (p-1)(q-1) 究竟是啥呢？

$(p-1)(q-1)=\Phi(p)*\Phi(q)=\Phi(pq)=\Phi(n)$
为啥 e 被要求和 (p-1)(q-1) 互素？

这个在之前的RSA 中的数论知识也讲过，当一个数和模数互素的时候，可以保证逆元存在且唯一。所以其实我们可以看到，这里强迫 e 与 (p-1)(q-1) 互素，就是为了保证在欧拉函数$\Phi(n) $为模的剩余中，存在这样一对乘法逆元。
既然 n 取一个大素数就可以很好的利用欧拉函数构造，为什么 RSA 还要用一对大素数的乘积作为 n 呢？

思考这样一个问题：现在你用一个大素数作为 n，那么显然它的欧拉函数$\Phi(n)=n-1$，你公钥里面给了 e 和 n，我们知道 d 是 e 在模欧拉函数$\Phi(n) $意义下的乘法逆元，那么我有了 n-1，有了 e，求 d 还不是分分钟钟的事情。。。这个根本没什么加密能力。。

于是我们退而求其：拿一个有两个大素数因子 p 和 q 的 n 来。现在 n 不是素数了，你有了 e，还需要我的欧拉函数才能算出 d。但是我的欧拉函数不再像素数那样就等于 n-1 了，要求我的欧拉函数，你必须得有我的两个素因子 p 和 q。但是众所周知，大数的质因数分解是一个 NP 为题。嘿嘿嘿，现在你要破解就没那么容易了。
总结

总结起来，RSA 的思路无非可以整理成这样几点：
1. 我想要一个以剩余系为数域，形式为幂函数的加密系统。
2. 那么我需要一个可以分解的幂函数恒等映射。
3. 我发现这个恒等映射可以用欧拉函数构造。
4. 构造这个恒等映射的时候，模数 n 要选一个稍微好点的，最好是一个质数或者是一个质因数很少且很大的数。
5. 这个恒等映射还需要可分解。
6. 我发现，可分解其实等价于找一对$\Phi(n) $为模数的剩余系中的乘法逆元。这也并不是特别难的事情。。
7. 好了，现在我想明白了。拿个大素数作为 n 试试。构造倒是构造出来了，但是发现好像公开了 e 和 n，d 很容易就算出来了。
8. 那我再拿两个大素数的乘积作为 n 试试，现在我发现你好像要算出 d 必须得算出 n 的欧拉函数，而这必须先解决大数质因数分解，这是非常困难的，那么现在我的加密系统就显得非常安全了。
9. 然后你还会想到，显然 n 不一定非要是两个素因子 p 和 q 的乘积，我们还可以取多个大素数的乘积来作为 n，也能达到类似的效果。

安全性¶

在设计思想中，我们已经梳理得很清楚了，RSA 算法本质上利用了大数字质因数分解的困难性：对于一个 N 位的数字，对其进行质因数分解，时间复杂度都是关于 N 的指数数量级，不存在多项式复杂度的算法。