RSA 加密算法原理 Nov 15, 2022

互质

两个正整数，除了1之外没有公共因子，那么就称这两个数互为质数。互质关系

欧拉函数

对于正整数 $n$, $n$ 的欧拉函数表示小于等于 $n$ 的正整数里，和 $n$ 互质的数的个数，用 $\varphi (n)$ 表示。欧拉函数

比如 $\varphi (8)=4$，因为符合条件的有 $1,3,5,7$

欧拉函数的一些特性：

1. $n=1$ 时，$\varphi (1)=1$
2. $n$ 为质数时，$\varphi (n)=n-1$
3. $n$ 为质数的幂时，比如 $n=p^k(p\mathrm{为}\mathrm{质}\mathrm{数})$ 时有 $\varphi (p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$ 这是因为当前仅当此数不包含质数 $p$ 时，才互质，总数 $p^k$ 减包含质数的个数 $p^{k-1}$
4. 如果 $n$ 可以被分解为两个互质数 $p_1,p_2$ 的积，那么 $\varphi (n)=\varphi (p_1)\cdot \varphi (p_2)$，证明见 中国剩余定理

欧拉定理

欧拉定理和应用

欧拉定理

如果两个正整数 $a$ 和 $n$ 互质，那么有等式成立：

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

即 $a^{\varphi (n)}$ 被 $n$ 除的余数为 1， 或者 $a^{\varphi (n)}=1+kn$

证明比较复杂略过，应用上，欧拉定理可以简化一些特定的运算，比如求解 $7^{222}$ 的末位数：

特殊的，当欧拉定理里的 $n$ 是质数 $p$ 时，因为 $\varphi (p)=p-1$，所以有 $a^{p-1}\equiv 1(\mathrm{mod}n)$ , 这也是著名的 费马小定理

模反元素(模逆元)

如果两个正整数 $a$ 和 $n$ 互质，那么一定可以找到整数 $b$，使得 $ab-1$ 被 $n$ 整除，即：

$$ab\equiv 1(\mathrm{mod}n)$$

or：

$$abmodn=1$$

此时就称 $b$ 为 $a$ 的模反元素

至此，所有需要了解的数学知识都在上面了，后面正式进入 RSA 算法的原理

1. 随机生成两个质数 $p$ 和 $q$

实际应用中，这两个质数是写成十进制都有几十位的非常大的质数，这里为了简单说明算法，我们挑选质数

$$p=37,q=41$$

2. 计算 $p$ 和 $q$ 的乘积 $n$

$$n=pq=1517$$

3. 满足一定条件挑选一个随机整数 $e$

需要有 $1<e<\varphi (n)$ 且 e 与 $\varphi (n)$ 互质

首先计算一下

$$\varphi (n)=\varphi (1517)=\varphi (37)\varphi (41)=36\cdot 40=1440$$

挑选了 $e=13$ （ $13$ 和 $1440$ 互质没问题）

4. 计算 $e$ 对 $\varphi (n)$ 的模反元素 $d$

即满足

$$ed\equiv 1(\mathrm{mod}\varphi (n))$$

等价于 $ed+k\varphi (n)=1$ 的整数解，其中已知 $e=13，\varphi (n)=1440$

也就是二元一次方程 $13d+1440k=1$ 的整数解，这里扩展欧几里得算法可以证明一定存在整数解，省略过程我们算出了一组解 $d=997,k=-9$ ，也就得到了模反元素 $d=997$

5. 封装公私钥

$n=1517,e=13$ 封装成公钥

$n=1517,d=997$ 封装成私钥

实际情况中，公私钥的内容会按照 ASN.1 规范来编码。

公钥加密

假设有信息$m$，需要用上面的公钥 $n,e$ 进行加密，这里对信息$m$有两点限制：

1. 必须是整数，字符串可以取 ascii 值等方法转换出数字表达
2. 值必须小于$n$，虽然正式场合下的$n$确实很大，但还是限制了加密的内容长度不能太长。

加密，实际上就是计算出满足下面式子的 $c$

带入我们上面的例子：公钥$n=1517,e=13$，假设我们要加密 $m=12$:

也就是 ${12}^{13}\equiv c(\mathrm{mod}1517)$

>>> 12**13 % 1517
423

这里直接用 python 算出来 $c=423$

私钥解密

加密使用私钥 $n,d$ 加上需要解密的密文 $c$， 计算满足下式的 $m$ 就是原文

带入上面例子里的：私钥 $n=1517,d=997$，密文 $c=423$:

也就是 ${423}^{997}\equiv m(\mathrm{mod}1517)$

>>> 423**997%1517
12L

解除原文 $m=12$

可以看出想要解密就需要知道 $d$ ，也就是上面说的大质数分解保护的安全性。

实际应用：

实际情况中因为只能加密小于 $n$ 的整数 $m$，对加密数据的长度提出了限制。所以可以

1. 把待加密消息分成若干段分别加密发送。
2. 或者使用对称加密（比如AES）来加密原消息，使用 RSA 来加密 对称加密 的密钥

证明过程

证明：

$$c^d\equiv m(\mathrm{mod}n)$$

$$\because m^e\equiv c(\mathrm{mod}n)$$

$$\Rightarrow c=m^e-kn$$

带入证明式子

$$\Leftarrow ((m^e-kn{)}^d\equiv m(\mathrm{mod}n))$$ $$\Leftarrow m^{ed}\equiv m(\mathrm{mod}n)$$

分类讨论:

① 当 $m$ 和 $n$ 互质时， $$\because ed\equiv 1(\mathrm{mod}\varphi (n))$$ $$\therefore ed=h\varphi (n)+1$$

带入上述待证明式： $$\Leftarrow m^{ed}\equiv m(\mathrm{mod}n)$$ $$\Leftarrow m^{h\varphi (n)+1}\equiv m(\mathrm{mod}n)$$

$\because m,n$ 互质，根据欧拉定理有： $$\Rightarrow m^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$ $$\Rightarrow (m^{\varphi (n)}{)}^h\cdot m\equiv m(\mathrm{mod}n)$$ $$\Rightarrow m^{h\varphi (n)+1}\equiv m(\mathrm{mod}n)$$ 原式得证。

② 当 $m$ 和 $n$ 不互质时， $$\because n=pq,m<n$$ $$\therefore m=kp$$ 或者 $m=kq$

以 $m=kp$ 为例，此时 $kp,q$ 必互质

根据欧拉定理有 $(kp{)}^{\varphi (q)}\equiv 1(\mathrm{mod}q)$ $$\Rightarrow (kp{)}^{q-1}\equiv 1(\mathrm{mod}q)$$ $$\Rightarrow [(kp{)}^{q-1}{]}^{h(p-1)}\cdot kp\equiv kp(\mathrm{mod}q)$$ $$\Rightarrow (kp{)}^{h(p-1)(q-1)+1}\equiv kp(\mathrm{mod}q)$$ $$\Rightarrow (kp{)}^{ed}\equiv kp(\mathrm{mod}q)$$ $$\Rightarrow (kp{)}^{ed}=tq+kp$$

$\because p,q、k,q$ 互质， $\therefore$ $t$ 必能被 $p$ 整除， $$\Rightarrow (kp{)}^{ed}=t^{\prime }pq+kq$$

带入 $m=kp,n=pq$ $$\Rightarrow m^{ed}=t^{\prime }n+m$$ $$\Rightarrow m^{ed}\equiv m(\mathrm{mod}n)$$

原式得证。