RSA 加密算法

RSA 加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA 是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在 1977 年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。

—— 维基百科

互联网是自由的，我们可以在网上获得几乎任何想得到的信息。1960 年，美国国防部高等研究计划署（DARPA）出于冷战的考虑，建立了网络的老祖宗——ARPANET。网络发展初期，人们并没有考虑太多有关网络安全的事，因为那时网络只有军方还有寥寥几所大学在用，大家在网上分享文献书籍，相互交流，如果还要设置密码只会徒增麻烦。网络给人们带来了极大的便利，其巨大的研究价值和商业价值也被人们发现，随之而来的就是互联网的蓬勃发展及大范围普及。随着用户的增多，信息安全越来越重要，人们需要寻找一种可靠的加密算法，这个时候，RSA 算法开始登上历史舞台。

算法的诞生

RSA 算法诞生的具体细节可以看这篇博客，写的挺好

算法过程

假如 Alice 要通过网络向 Bob 发送一条私人信息，她可以通过如下几步得到一个公钥和密钥：

1. 随机选取两个不同的大素数 $p$ 和 $q$，比如位数超过 100 位。将这两个数乘起来，得到 $N=pq$
2. 根据欧拉函数，求得 $r=\varphi(N)=\varphi(p)\times\varphi(q)=(p-1)(q-1)$
3. 选择一个小于 $r$ 且与 $r$ 互质的整数 $e$。此时必然可以找到一个 $d$ 使得 $ed\equiv 1(mod\ r)$
4. 销毁 $p$ 和 $q$。现在 $(N,e)$ 就是的公钥，$(N,d)$ 就是密钥

现在 Alice 把公钥 $(N,e)$ 传给 Bob，私钥 $(N,d)$ 自己藏着。当 Bob 想给 Alice 发送消息 m 时，先约定好信息的处理格式，比如将每一个字转换为这个字的 Unicode 码，然后进行分段加密。将消息 m 的每一段视为数字 n，然后通过：

$$c\equiv n^e(mod\ N)$$

得到加密后的 c。最后将加密后的各段连接起来就可以发给 Alice 了。Alice 收到 Bob 的密文后，先将密文分段，将每一段设为 c，然后就可以通过自己的密钥得到明文：

$$n\equiv c^d(mod\ N)$$

算法原理

前置概念

RSA 加密算法需要一些数论知识，我们首先要知道什么是同余，什么是剩余系，什么是欧拉公式，以及欧拉定理和费马定理的内容¹。这里只给出一些必要的知识点，详细证明不做论证，还请看课本¹。如果这些内容你都了解，那就可以直接跳到理论推导

同余

对于任意非零整数 $a$ 和 $m$，一定可以找到一对整数 $q$ 和 $r$，使得

$$a=mq+r\ (0\leq r\le m)$$

这个时候 $a$ 除以 $m$ 会得到余数 $r$。如果还有一个数 $b$ 同样满足 $b=mq’+r$，则 $a$ 和 $b$ 除以 $m$ 的余数相同。这个时候我们就说 $a$ 与 $b$ 模 $m$ 同余：

$$a\equiv b\ (mod\ m)$$

欧拉公式

欧拉函数 $\varphi(a)$ 是定义在正整数上的函数，它在正数上的值等于序列 $0,1,2,\cdots,a-1$中与 $a$ 互质的数的个数

简化剩余系

对于非零整数 $a$ 来说，所有的整数除以 $a$ 都只能得到 $a$ 个余数：$0,1,\cdots,a-1$，将余数相同的各自分为一组，可以分为 $a$ 组，我们称这些组为模 $a$ 的剩余类；再从这些剩余类中分别取一个数组成一个集合，这样就得到了 $a$ 的完全剩余系，比如 3 的完全剩余系可以为 1，4，3 或者 0，1，2。

如果一个剩余类中的数模 $a$ 得到的余数和 $a$ 互质，我们就称这是一个与模 $a$ 互质的剩余类。将所有这些剩余类找出来，就得到了 $a$ 的简化剩余类。比如对于 6 来说，它的完全剩余类可以为 0，1，2，3，4，5，简化剩余类 1，5。

定理 X 若 $(a,m)=1$，在模 $m$ 的所有简化剩余系中各取一个 $x$，则 $ax$ 也可以构成模 $m$ 的一个简化剩余系

证明：

由于 $(a,m)=1,(x,m)=1$，则 $(ax,m)=1$。若在不同的简化剩余系取 $x_1$，$x_2$，则必有

$$x_1\not\equiv x_2(mod\ m)$$

而 $ax_1\equiv ax_2(mod\ m)$，则 $a(x_1-x_2)\equiv 0(mod\ m)$，从而 $x_1\equiv x_2(mod\ m)$ 与假设矛盾，所以定理得证

欧拉定理

设 $m$ 是大于 1 的整数，$(a,m)=1$，则

$$a^{\varphi(m)}\equiv 1(mod\ m)$$

证明：

我们设 $r_1,r_2,\cdots,r_{\varphi(m)}$ 是模 $m$ 的简化剩余系，则由定理 X 可以得到 $ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 也是模 $m$ 的简化剩余系，所以

$$(ar_1)\cdots(ar_{\varphi(m)})\equiv r_1r_2\cdots r_{\varphi(m)}(mod\ m)$$

则

$$a^{\varphi(m)}(r_1r_2\cdots r_{\varphi(m)})\equiv r_1r_2\cdots r_{\varphi(m)}(mod\ m)$$

又因为 $(r_1r_2\cdots r_{\varphi(m)},m)=1$，所以可以得到

$$a^{\varphi(m)}\equiv 1(mod\ m)$$

费马定理

若 $p$ 是素数，则

$$a^{p}\equiv a(mod\ p)$$

费马定理可以由欧拉定理直接得到：因为 $p$ 是质数，所以 $\varphi(p)=p-1$，因此

$$a^{p}\equiv a^{1+\varphi(p)}\equiv a\cdot 1\equiv a(mod\ p)$$

理论推导

我们用数学语言再复述一遍算法过程：$p$ 和 $q$ 是两个大质数，$N=pq$。$e$ 和 $d$ 满足 $ed\equiv1(mod\ \varphi(N))$。设一个明码为 $a(0\leq a\leq N-1)$，加密程序将 $a$ 通过 $a^e\equiv b(mod\ N)$ 转换为 $b$，并将其发送给接收方。接收方使用密钥通过 $b^d\equiv a(mod\ N)$ 将 $b$ 还原为明码 $a$。

在生成密钥时，根据同余的性质，一定可以找到一对 $e$，$d$，使得 $ed\equiv1(mod\ \varphi(N))$，因而加密过程可以正常进行。在解密时，实际上是计算了如下等式：

$$b^d\equiv a^{ed}\equiv a(mod\ N)$$

从而只需要证明 $a^{ed}\equiv a(mod\ N)$。因为 $ed\equiv1(mod\ \varphi(N))$，所以 $ed=k\varphi(N) + 1$。又由于 $N=pq$，从而我们只需要证明：

$$a^{1+k\varphi(N)}\equiv a(mod\ p),a^{1+k\varphi(N)}\equiv a(mod\ q)$$

因为由欧拉公式可以得到 $\varphi(N)=\varphi(pq)=(p-1)(q-1)$。所以当 $p$ 整除 $a$（即 $a=kp$）时，上面第一个式子肯定成立；若 $p$ 不能整除 $a$ 时，由费马定理知 $a^{p-1}\equiv1(mod\ p)$，从而

$$a^{(p-1)(q-1)}\equiv1^{q-1}\equiv1(mod\ p)$$

从而

$$a^{1+k\varphi(N)}\equiv a\cdot a^{k(p-1)(q-1)}\equiv a\cdot1^{k}\equiv a(mod\ p)$$

同理可以得到

$$a^{1+k\varphi(N)}\equiv a(mod\ q)$$

综上我们就可以证明通过密钥 $d$ 一定可以将密文还原为明码

实例演示

知道了 RSA 的原理后，我们再看一个例子来加深对整个算法流程的理解。假如 Bob 要向 Alice 发送一个数字 173，那么她需要做如下的操作

首先生成密钥。Alice 选择了两个素数 13 和 19，求得 $N$ 为 247，$r$ 为 216。取 $e$ 为 25，则可以找到 $d$ 为 121，此时正好有 $25\times121\equiv 1(mod\ 216)$。自此 Alice 得到了私钥 $(121,247)$，并将公钥 $(25,247)$ 交给 Bob。

有了公钥和私钥，Bob 就可以发信息了，$173^{25}\equiv 147(mod\ 247)$，这样就得到密文 147。Alice 收到密文后，通过 $147^{121}\equiv173(mod\ 247)$ 就能够还原出明文 173

算法的安全性

实际上，公钥 $e,N$ 是可以公开的。就是说，如果某人掌握了密钥 $d$ 而不向其他人泄露，就算别人知道他的公钥是 $e,N$，也几乎不可能将密文解码。因为根据前面的推导可以看到，要想知道密钥 $d$，就必须知道 $\varphi(N)$；而要想求出 $\varphi(N)$，就必须得到 $N$ 的质因数分解。然而令人遗憾的是，迄今为止质因数分解的问题也没有得到解决，只要初始的 $p$ 和 $q$ 设置的足够大，就算量子计算机出马，也够它喝一壶的。

关于 RSA 的保密性能，在历史上有一个有趣的故事。1977 年里维斯、沙米尔和阿德曼用一个 129 位的数 $N$ 和一个 4 位数 $e$ 对一个关于秃鹰的消息在 RSA 中加密，即所谓的 RSA-129，还悬赏 100 美元，奖给第一个破译该密码的人。他们认为按照当时计算机的速度，估计分解一个 129 位的数大约要花 23000 年，计算速度提高可能会降低一两个数量级，但是安全性似乎仍然相当有保证。然而出乎他们的预料，仅仅在 17 年之后 RSA-129 就败下阵来。分解成功的核心在于发明了一种新的筛法——二次筛法，这方法有一个优点是能将工作分散到不同的计算机上去做。人们组织了大约有六百多人的因子分解迷，经过八个月的努力找到了 RSA-129 的分别为 64 位和 65 位的两个质因数。但是，RSA-129 分解的成功，甚至包括数学家们近年来不断创造的许多新算法，例如二次筛法、数域筛法、椭圆曲线算法，目前还不足以威胁 RSA 体制的安全性。因为用以分解数字所需要的计算机的能力，随着数字的位数的增加而飞快地增加。例如，使用 RSA-200 至 RSA-300，那么除非计算数论有惊人的突破，否则因子分解在一个长时期内仍然是个难题

算法的优缺点

优点：RSA 算法是一种非对称加密算法，同时其安全性与质因数分解的难度相关，所以安全性较好。而且 RSA 算法自 1977 年提出一直用到现在，经历了无数次考验，足以见其安全稳定。

缺点：为了确保安全性，需要使用很长的质数生成 $N$，找到超长素数的难度不说，为了存储 $N$ 也要大几百比特，由此导致了该算法的速度非常慢，也不能加密太大的文件，一般是配合对称加密进行使用。