1. 简介

rsa 是一种非对称密码算法，由三位数学家 Rivest、Shamir 和 Adleman 设计。其原理基于大数因式分解的复杂性。通常使用时，生成一对公私钥对，主要应用于以下两个场景。

• 加解密: 使用公钥加密，只有持有私钥的人可以解密。
• 签名和验签：使用私钥进行签名，公钥进行验签，用于一些数据签名，校验的场景。

2. 数学背景

2.1 欧拉函数

假设有正整数$n$，欧拉函数$\varphi (n)$的值等于小于$n$的正整数里有多少个与$n$互为质数。

欧拉函数有以下几个性质：

1. $\varphi (1)=1$ 因为 1 与任何数都保持了互质关系。
2. 如果$n$为质数，$\varphi (n)=\varphi (n-1)$
3. 如果$n$为质数的某一次方，即 $n=p^k$:

这是因为当 $m<n$ 时，当且仅当 $m$ 不为 $p$ 的倍数，$m$才与 $n$ 互质，而这样的数共有$p^{k-1}$个$(1\cdot p,2\cdot p,...,p^{k-1}\cdot p)$。
例如：
对$n=7^3$求$\varphi (n)$，需要枚举所有小于$7^3$的数中不为$7$的倍数的数，这样的数共有$7^3-7^2=294$个。

4. 如果$n$可以分解成两个互质的整数乘积

则：

5. 任意大于 1 的正整数，都可以写成一系列质数的乘积。

根据第四条的结论，可以得到：

也就是欧拉函数计算的通用公式。

2.2 欧拉定理

欧拉函数主要是为了推导出欧拉定理：

如果两个正整数 $a$ 和 $n$互为质数，则$n$的欧拉函数$\varphi (n)$可以让下面的等式成立：

也就是$a$的 $\varphi (n)$ 次方被$n$除的余数为 1。例如，$3$ 和 $7$ 互质，$\varphi (7)=6$，
所以 $3^7-1=728$可以被 $7$ 整除 $(728/7=104)$ 。

当 $p$ 为质数时，$\varphi (p)=p-1$，所以此时可以得到：

这就是著名的费马小定理，是欧拉定理的特例。
欧拉定理是 RSA 的核心。

2.3 模反元素

如果两个整数 $a$ 和 $n$ 互质，则一定可以找到整数 $b$ ，使得 $a\cdot b\mathrm{m}\mathrm{o}\mathrm{d}n=1$，此时称 $b$ 为 $a$ 的模反元素。

欧拉定理可以证明模反元素必定存在：

也即 $a^{\varphi (n)-1}$ 就是 $a$ 的模反元素。

3. 秘钥计算

• Step1：随机选取两个不相等的质数 $p$ , $q$
  如选取$p=61$,$q=53$。该步骤中选取的 $p$，$q$ 越大越难破解。
• Step2：计算 $p$ , $q$ 的乘积设为$n$
  上例可得：

• Step3：计算 $n$ 的欧拉函数 $\varphi (n)$
  因为 $p$ , $q$均为素数，所以

• Step4：随机选择一个整数 $e$，条件是$1<e<\varphi (n)$，且 $e$ 与 $\varphi (n)$ 互质
  如上例中，选择 $e=17$ ，实际应用常选择 65537。
• Step5：计算 $e$ 对于 $\varphi (n)$ 的模反元素 $d$

此时$\varphi (n)$和$e$已知，只需要求得上述二元一次方程 $k,d$的一组解即可。
在以上例子中可以找到一组解 $d=2753，k=15$。

• Step6：将 $(n,e)$ 封装成公钥，$(n,d)$封装成私钥。

4. 可靠性分析

上面的密钥生成步骤，一共出现六个数字：

其中，公钥用到了两个（$n$ 和 $e$），其余四个数字都是不公开的。其中最关键的是$d$，因为 $n$ 和 $d$ 组成了私钥，一旦 $d$ 泄漏，就等于私钥泄漏。

所以如果要破解 rsa，就要在已知 $n$ 和 $e$ 的情况下破解 $d$。

因为 $e,d$，对于 $\varphi (n)$ 互为对方的模反元素，所以要想算出 $d$ 必须算出$\varphi (n)$，若要由 $n$ 算出 $\varphi (n)$ 需要将 $n$ 分解成两个素数的乘积，也就是算$n=p\cdot q$中的 $p$ 和 $q$。而对于极大整数因式分解是极其困难的，所以 RSA 几乎不可能被破解。

5. 加解密过程

5.1 加密

设消息为 $m$， 公钥为 $(e,n)$

可以算出密文 $c$ 为：

如上例中，假设 $m=65$：

5.2 解密

解密要用私钥：

假设收到的信息为 2970，解密过程可得：

注意： RSA 只能加密小于$n$的整数，如果要加密大于 $n$ 的整数怎么办？主要有两种解决方法，种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如 DES），用这种算法的密钥加密信息，再用 RSA 公钥加密 DES 密钥。

6. 私钥解密的证明

要证明私钥解密过程是有效的，也就是证明：

根据加密规则：

所以原式等价于证明：

因为$e,d$ 对于 $\varphi (n)$ 互为模反，所以 $ed\mathrm{m}\mathrm{o}\mathrm{d}\varphi (n)=1$。
也即$ed=t\cdot \varphi (n)+1$

接下来分两种情况：
(1) $m$, $n$ 互质：
由欧拉定理可得：

由上面的式子推到出结论是因为一个取模的性质：乘积的模等于模的乘积。
(2) $m$, $n$ 不互质：
此时，由于$n=pq$，所以要么$m=kp$，要么$m=kq$。
假设$m=kp$，此时 $m$ 与 $q$ 互为质数，由欧拉函数可得：

($\equiv$表示同余，上面的式子表示两边对 $n$ 取余数相等) 这里用到同余的一个性质，对 $n$ 同余的两个数乘以一个相同的数之后结果依然对 $n$ 同余。将$m=kp$带入上式可得：

也即

以上关系转换成等式可以写成：

因为$q$，$p$互质，所以 $t$ 必然被 $p$ 整除，$t=t^{\prime }p$。

将 $kp$ 重新替换成 $m$，$pq$ 替换成 $n$ 就可以得到：

参考

• RSA 算法原理（一）
• RSA 算法原理（二）