RSA算法介绍

非对称密码（公钥密码）体系

非对称密码体系是 1976 年被正式提出的概念，弥补了对称密码的一些缺陷。

其基本方案是：用户生成公钥 \(pub\) 和私钥 \(pri\)，公钥向他人公开并用于信息加密，私钥由本人保管并用于信息解密。

RSA 是 1977 年被提出的公钥密码算法，其核心原理是数论中的欧拉定理，被广泛用于互联网的方方面面（包括 ssh，https 等关键设施）。在量子计算机还未成熟的今天，RSA 可谓公钥密码体系的中流砥柱。

数学基础

完全剩余系

给定正整数 \(m\)，全体整数根据模 \(m\) 的余数显然可以划分为 \(m\) 个集合，每个这样的集合称为模 \(m\) 的剩余类；在整数模 \(m\) 的所有剩余 类中各取一个代表元，构成的集合称为模 \(m\) 的完全剩余系，其中 \(\{0,1,...,m-1\}\) 为最小非负完全剩余系。

定理 1

设 \(m\) 为正整数，整数 \(a\) 和 \(m\) 互素，\(b\) 为任意整数，\(x\) 是模 \(m\) 的一个完全剩余系，则 \(ax+b\) 也是模 \(m\) 的一个完全剩余系。

定理 2

设 \(m_1,m_2\) 为两个互素的正整数。若 \(x\) 为模 \(m_1\) 的一个完全剩余系，\(y\) 为模 \(m_2\) 的一个完全剩余系，则 \(m_1y+m_2x\) 为模 \(m_1m_2\) 的一个完全剩余系。

简化剩余系

在模 \(m\) 的一个剩余类中，如果有一个数与 \(m\) 互素，则显然该剩余类中所有的数均与 \(m\) 互素，此时称该剩余类与 \(m\) 互素。与 \(m\) 互素的剩余类的个数称为欧拉函数，记为 \(\varphi(m)\)，其值等于 \(1\) 到 \(m-1\) 中与 \(m\) 互素的数的个数。欧拉函数有两个重要性质：

• 对于任意素数 \(p\) 有 \(\varphi(p)=p-1\)；
• 若 \(m,n\) 互素，则 \(\varphi(mn)=\varphi(m)\varphi(n)\)。

在与 \(m\) 互素的 \(\varphi(m)\) 个模 \(m\) 的剩余类中各取一个代表元，组成的集合称为模 \(m\) 的一个简化剩余系或既约剩余系。例如 \(\{1,5,7,11\}\) 构成模 \(12\) 的一个简化剩余系。

定理 3

设 \(m\) 是正整数，整数 \(a\) 与 \(m\) 互素。若 \(x\) 为 \(m\) 的一个简化剩余系，则 \(ax\) 也是 \(m\) 的一个简化剩余系。

定理 4

设 \(m_1,m_2\) 是两个互素的正整数，如果 \(x\) 是 \(m_1\) 的一个简化剩余系，\(y\) 是 \(m_2\) 的一个简化剩余系，则 \(m_1y+m_2x\) 是 \(m_1m_2\) 的一个简化剩余系。

欧拉定理

定理 5

将 \(m\) 质因数分解得到

\[m=p_1^{e_1}p_2^{e_2}...p_n^{e_n},\]

则

\[\varphi(m)=m\prod_{i=1}^{n}(1-\frac{1}{p_i}).\]

定理 6（欧拉定理）

设 \(r,m\) 是正整数，且 \(gcd(r,m)=1\)，则 \(r^{\varphi(m)}\equiv 1\pmod{m}\)。

证明：取模 \(m\) 的一组简化剩余系

\[\{r_1,r_2,...,r_\varphi(m)\},\]

由定理 3 知

\[\{rr_1,rr_2,···,rr_\varphi(m)\},\]

也是模 \(m\) 的一组简化剩余系，则有

\[\prod_{i=1}^{\varphi(m)}r_i\equiv\prod_{i=1}^{\varphi(m)}rr_i\equiv r^{\varphi(m)}\prod_{i=1}^{\varphi(m)}r_i\pmod m，\]

又

\[gcd(\prod_{i=1}^{\varphi(m)}r_i,m)=1，\]

因此 \(r^{\varphi(m)}\equiv 1\pmod m\)。

扩展欧几里德算法

扩展欧几里德算法在 RSA 中用于求模意义下的乘法逆元。简单来说，给定整数 \(a,b\)，则 \(a\) 在模 \(b\) 意义下的乘法逆元 \(x\) 满足 \(ax\equiv 1\pmod{b}\)，即 \(ax=by+1\)，求出 \(ax+by=1\) 的一组正整数解即可。

想要求二元一次方程 \(ax+by=c\) 的整数解，其有解的前提是 \(gcd(a,b)|c\)。利用欧几里德算法求最大公因数的思想：

\[gcd(a,b)=gcd(b,a-b\lfloor\frac{a}{b}\rfloor).\]

每次递归会削减 \(a,b\) 的大小，且最终一定会递归至 \(gcd(a',0)\) 的情形，此时 \(a'\) 即二者的最大公因数。因此，为了求解 \(ax+by=c\)，我们可 以先求方程 \(bx'+(a-b\lfloor\frac{a}{b}\rfloor )y'=c\) 的解，原因有两个：

1. 从后者的解可以推出前者的解。求出 \(x',y'\) 的值后，对比两个方程： \[ax+by=c,\] \[ay'+b(x'-y'\lfloor\frac{a}{b}\rfloor)=c,\] 显然可以求出 \(x=y',y=x'-y'\lfloor\frac{a}{b}\rfloor.\)
2. 递归求解的过程是有边界的，即最终会递归至： \[a'x'=c.\] 由欧几里德算法，此时的 \(a'\) 即为最初 \(a,b\) 的最大公因数，只要此方程有解即可通过回代求出最初方程的解。

算法流程

RSA 基于这样一个事实：计算两个大质数的乘积很容易，但将乘积分解回两个质数很困难。其具体流程如下：

1. 选取两个大质数 \(p,q\)，令 \(n=pq\)，则 \(\varphi(n)=(p-1)(q-1)\)；
2. 任取一小于 \(\varphi(n)\) 的正整数 \(e\)，要求 \(e\) 与 \(\varphi(n)\) 互质；
3. 用扩展欧几里德算法求 \(e\) 在模 \(\varphi(n)\) 意义下的乘法逆元 \(d\)，即 \(ed\equiv 1\pmod{\varphi(n)}\);
4. 公钥为 \((n,e)\)，私钥为 \((n,d)\)。

加密明文 \(m\) 时，密文 \(c=m^e\bmod n\)；解密密文 \(c\) 时，显然 \(m\) 和 \(n\) 应当是互质的，由欧拉定理可得：

\[m^{\varphi(n)}\equiv 1\pmod{n},\]

因此

\[c^d\equiv m^{ed}\equiv m^{1+k\varphi(n)}\equiv m(m^{\varphi(n)})^k\equiv m\pmod{n}.\]

试想，作为一个攻击者，在已知公钥 \((n,e)\) 的前提下，想要获取私钥 \((n,d)\) 就必须求出 \(\varphi(n)\) ，也就是得到 \(p,q\) 的值；但在 \(n\) 足够大的前提下，对其进行质因数分解几乎 只有暴力枚举一种方法，这便是 RSA 安全性的根本来源。

RSA 之大素数生成

通过上面对 RSA 算法的介绍，引出了一个新的问题：如何获得足够大的随机质数。

目前 RSA 的主流密钥长度都在 1024 位以上，即 \(p,q\) 的长度要在 512 位。面对 \(2^{512}\) 这样的数量级，无论是试除还是筛法都已经不能满足 筛选质数的要求。

目前对于大质数的判断还没有能百分百符合要求的算法。主流的算法是随机生成一个大数，通过 Miller-Rabin 算法概率性地判断其是否为质数，如 果不是的话则在这个大数附近继续随机地寻 找（根据质数分布的规律，这个随机寻找的过程不会花费太多的时间）。Miller-Rabin 算法在足够多的检测次数下几乎不会判断错误（64 轮检测后误判概率小于 \(2^{-128}\)），因此能够符合 工业级的加密场景。

事实上，百分百确定的素性测试算法也已经被提出了，即 AKS 素数测试算法；虽然其性能仍然不能满足需求，但具有重要的学术意义。