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 素数测试算法；虽然其性能仍然不能满足需求，但具有重要的学术意义。