RSA加密算法（一）

Table of Contents

本文大量使用$\LaTeX$公式，建议刷新一次使渲染更新后食用

前言

内行吹得天花乱坠、外行死活看不懂的深奥数论和其他近现代数学分支到底有什么用处？近现代数学取得的成果到底有何现实意义？数学家到底在思考什么、研究什么？这几个问题困扰了我这个数学废物很久很久。直到如今成为一名网安小白，接触了密码学之后，这个疑惑才终于散去几分。希望看了这篇关于 RSA 加密算法的介绍之后，你也能得到些许明悟。

历史杂谈

1976 年以前，人类所有的加密算法都使用同一种模式

发送方选择一种加密规则对信息进行加密
接收方使用同一种规则对信息进行解密

由于加密和解密使用同一种规则，因此这种加密算法称为“对称加密算法”。

不难看出，对称加密算法最大的弱点在于，发送和接受双方必须事先约定加密规则，此时要想保密地传递和保存密钥变得十分困难。随着计算机技术的快速发展，这个问题变得更加严峻。最著名的例子就是二战时期纳粹德国的密码系统恩尼格玛被计算机科学之父艾伦·图灵设计的机器破解。

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

接收方生成公钥和私钥两把密钥，其中公钥是公开的，而私钥是保密的
发送方获取公开的公钥，使用它对信息进行加密
接收方使用保密的私钥对信息进行解密

公钥加密的信息只能通过私钥解得，只要私钥不泄露，通信就是安全的。

这种加密算法称为“非对称加密算法”。

1977 年，三位数学家 Rivest、Shamir 和 Adleman（封面图）设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做 RSA 算法。直到现在，RSA 算法依旧是最广为使用的非对称加密算法。毫不夸张地说，只要有计算机网络的地方，就有 RSA 算法。

RSA算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长 RSA 密钥是 768 个二进制位。也就是说，长度超过 768 位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024 位的 RSA 密钥基本安全，2048位的密钥极其安全。

数学基础

互质

若两个正整数除了 1 以外没有其他公因子，则我们称这两个数是互质关系（coprime）。注意，构成互质关系的两个数不一定是质数。

欧拉函数

先来引入一个问题：

任意给定正整数n，则在小于等于n的正整数之中，有多少个与n构成互质关系？

欧拉函数可以用来解决则个问题。

约定用$\phi(n)$来表示欧拉函数。欧拉函数本身并不复杂，下面来一步步讨论。

第一种情况

若 n=1，显然$\phi(1)=1。$

第二种情况

若 n 是质数，则$\phi(n)=n-1$。因为质数与小于它的每个数都构成互质关系。

第三种情况

若 n 是质数 p 的 k 次方，即$n=p^k$，则

$$ \phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p}) $$

这是因为一个数只有当它不包含 p 时才能与 n 互质；而小于 n 且包含 p 的数有$1\times p、2\times p、3\times p、\ldots、(n-1)\times p$共$p^{k-1}$个,将它们剔除后剩下的就是与 n 互质的数。

第四种情况

若 n 可以分解成两质数的乘积，即$n=p_1\times p_2$，则 $$ \phi(n)=\phi(p_1p_2)=\phi(p_1)\phi(p_2) $$ 这条式子的证明需要用到著名的“中国剩余定理”,无奈限于本人水平限制，在这里就暂不展开了。

第五种情况

因为任意一个大于 1 的正整数 n 都可以分解成一系列质数的乘积 $$ n=p_1^{k1}p_2^{k2}\ldots p_r^{kr} $$ 又根据第四种情况，我们可以得到 $$ \phi(n)=\phi(p_1^{k1})\phi(p_2^{k2})\ldots \phi(p_r^{kr})=p_1^{k1}p_2^{k2}\ldots p_r^{kr}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\ldots(1-\frac{1}{p_r}) $$ 化简得 $$ \phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\ldots(1-\frac{1}{p_r}) $$ 这就是欧拉函数的通用公式。

欧拉定理

$$ a^{\phi(n)}\equiv1(mod\ n) $$

欧拉定理的意思是 a 的$\phi(n)$次方被n除余数为1。

定理的证明十分复杂且超过本人能力，故暂不叙写证明。

费马小定理

著名的费马小定理其实是欧拉定理的一个特例。

假设正整数 a 与质数 p 互质，则欧拉定理可以写成 $$ a^{p-1}\equiv1(mod\ p) $$

模反元素

若两个正整数 a 和 n 互质，那么一定可以找到一个整数 b，使得 ab-1 能被 n 整除。换句话说即是 ab 被 n 除余数为 1。 $$ ab\equiv1(mod\ n) $$ 此时，我们称 b 为 a 的模反元素。

根据欧拉定理，我们很容易证明模反元素必然存在 $$ a^{\phi(n)}=a\times a^{\phi(n)-1}\equiv1(mod\ n) $$ 可见，a 的$\phi(n)-1$次方是 a 的模反元素。

RSA算法

RSA 算法实际上并不复杂

参数

随机选择两个不相等的质数 p 和 q
- p 和 q 越大，算法越难被破解
计算 p 和 q 的乘积 n
计算 n 的欧拉函数$\phi(n)=(p-1)*(q-1)$
选择一个整数 e，其中$1
- 现实生活中常取 e=65537=0x10001
计算 e 对$\phi(n)$的模反元素 d
- $$ ed\equiv1(mod\ \phi(n)) $$ 式子等价于 $$ ed-1=k\phi(n) $$ 取 x=d，y=-k $$ ex+\phi(n)y=1 $$ 用辗转相除法求解得一组整数解（x,y），从而得到 d
- 在 python 中可以直接调用 gmpy2 库中的invert()函数得到 d 具体用法为d=gmpy2.invert(e,phi)
算上明文 m 和密文 c，我们得到 RSA 算法的所有参数

加密&解密

使用公钥（n,e）加密

对于明文 m，我们使用下列公式算出密文 c： $$ m^e\equiv c(mod\ n) $$ 值得注意的是，m 必须是一个小于 n 的整数（字符串可以取 ASCII 值或 Unicode 值）。

使用私钥（n,d）解密

对于收到的密文 c，我们使用下列公式解出明文 m： $$ c^d\equiv m(mod\ n) $$ 数学证明依旧暂不给出。

至此，我们完成了 RSA 算法的加密-解密过程。

安全性

由加密-解密过程可看出，若不知道密钥 d，则没有办法由密文 c 解得明文 m，而若想得到d就必须先分解 n，而我们知道大数的质因数分解极其困难，这也保证了现阶段 RSA 算法是安全的。

我们可以看见，RSA 算法在理论上并不是安全的。事实上，现在普遍认为量子计算机的发展很有可能使 RSA 算法变得极不安全。但至少在现阶段人类科技水平下 RSA 算法仍然非常安全。

后记

RSA 算法的 C 语言实现以及 RSA 算法及其相关定理的证明将在后几篇文章给出，敬请期待。

前言