数论的奥秘：RSA 加密算法背后的数学之美（上篇）

• hello，大家好，我是 Lorin，接下来的两期是给群友答疑的两期，关于 RSA 非对称加密原理，文章分为上下两篇，上篇：“数论的奥秘：RSA算法背后的数学之美” 主要讲解 RSA 背后的故事和相关的数论知识，下篇：“RSA 算法的原理与加密过程深度解析” 主要讲解如何讲解如何使用数论知识实现 RSA 算法，废话不多说，发车：

认真听课.png

历史背景

• 在 1976 年以前，所有的加密方式都是使用同一种方式，即甲方使用一种规则对信息进行加密，乙方使用同样的规则进行解密，由于加密和解密使用同样的规则，因此也称为“对称加密”。这种加密方式有个最大的问题，就是如何安全的保存和传递密钥。

• 1976 年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman 提出了一种崭新的构思，可以在不直接传递密钥的情况下完成解密。这被称为 "Diffie-Hellman 密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为 "非对称加密算法"。

代码语言：txt复制

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。

• 如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

bg2013062702.jpg

• 1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
• 这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

RSA 算法背后的数学之美

• 本篇文章将介绍 RSA 背后涉及的一些数论知识：

质数

• 质数，又称素数，是指大于1的自然数中，除了1和自身以外没有其他正因数的数。换句话说，质数是只能被1和它本身整除的正整数。

互质关系

• 互质关系是指两个或多个整数之间的关系，其中这些整数的最大公因数（最大公约数）等于1。换句话说，如果两个整数a和b的最大公因数是1，那么它们被认为是互质的。
• 例如，整数4和9是互质的，因为它们的最大公因数是1。同样，整数15和28也是互质的，因为它们的最大公因数是1。但是，整数6和9不是互质的，因为它们的最大公因数是3，而不是1。

欧拉函数

• 欧拉函数 φ(n) 的定义是小于等于正整数n且与n互质的正整数的个数。
• 对于任意一个大于1的正整数，都可以写成一系列质数的积（其中p1、p2...pk是不同的质数，e1、e2...ek是它们的指数）：

• 则 φ(n) 可通过如下乘积公式计算：

如何推导欧拉函数

• 我们需要以下几个步骤来完成欧拉函数的推导：

如果 n = 1，则 φ(1) = 1 。

• 因为1与任何数（包括自身）都构成互质关系。

如果整数 m，n 互质，则 φ(mn) = φ(m) * φ(n)

• 可以简单这样理解，如果 a 与 m 互质（a < m）, b 与 n 互质（b < n）, c 与 mn 互质（c < mn）, 且 c 和 数对（a，b）一一对应。 a 有 φ(m) 种可能，b 有 φ(n) 种可能，那么数对 （a，b）有 φ(m) φ(n) 可能，c = φ(mn)，则 φ(mn) = φ(m) φ(n)。
• 实际上需要结合 “中国剩余定理证明”，具体证明感兴趣的同学可以看看：

如果n是质数的某一个次方，即 n = p^k，则φ(n) = p^k - p^(k-1)

• 如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则 φ(n) = p^k - p^(k-1)
• 同样可以简单的这样理解：因为 n = p^k ，如果需要和 n 互质，那么不能为 p 的倍数，则需要去除 1p、2p ... p^2p ... P^(k-1)P，一共有 P^(k-1) 个，即可以得出 φ(n) = p^k - p^(k-1)。
• 严谨的证明可以参考下面的方式：

证明欧拉函数

• 学习了上面几个概念，我们就可以开始进行欧拉函数的推导：

• 可以看出要计算 φ(n) 的值，必须对 n 做质因数分解。当 含有特别大的质因数时，分解 n 将会十分困难，此时求解 φ(n) 也会十分困难。RSA 加密算法正是利用了这一性质，从而保证安全性。

其它性质：如果 n 是质数，则 φ(n) = n-1

• 如果 n 是质数，则 φ(n) = n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

欧拉定理

• 如果a和n是互质的正整数（即gcd(a, n) = 1），则满足以下公式：

代码语言：txt复制

a^φ(n) ≡ 1 (mod n) 
其中，^ 表示乘方，φ(n) 表示欧拉函数φ(n)，≡ 表示模同余，即 a的φ(n)次方被n除的余数为1。

• 欧拉定理的证明比较复杂，这里就不证明了有兴趣的朋友可以去看看。

模反元素

• 如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

代码语言：txt复制

a * b ≡ 1 (mod n)

• 此时，我们称 b 是 a 的模反元素，比如，3 和 11 互质，那么 3 的模反元素就是 4，因为 (3 × 4) - 1 可以被 11 整除。显然，模反元素不止一个，4 的整数倍都是 a 的模反元素。
• 模反元素公式可以使用欧拉定理证明：

代码语言：txt复制

a^φ(n) = a*a^(φ(n) - 1) = 1 (mod n)，即 a^(φ(n) - 1) 是 a 的模反元素。

个人简介