本文数学证明部分转自阮一峰大神的博客

顺便贴出 RSA 的 RFC 文档链接。顺便感慨一下,我有时候总会钻在细节的牛角尖出不来,例如 RSA 签名我总有一个细节问题不是很清楚,可能有些过于贴近细节导致网上容易搜到的信息都不能解答我的疑惑,我的半吊子网络安全老师肯定也是靠不上的,一筹莫展之际忽然想起了 RFC ,不得不感慨真是太详细了,虽然数学原理可能不会涉及太多,但具体的步骤真是非常详细,刚好解答了我的疑惑。

关于 RSA 是什么以及整个非对称密钥加密体系的介绍在上一篇博客

1. RSA 的数学基础

1.1. 欧拉函数

互素(互质):两个整数的最大公约数为1,则称这两个数互素。

欧拉函数 $\varphi(n)$ :$\varphi(n)$ 表示在小于或等于 $n$ 的正整数中,与 $n$ 互素的数的个数。

欧拉函数性质

  1. 假如 $n$ 为素数,则 $\varphi(n)$ 为 $n-1$ ,因为一个素数和任何一个小于它的数都互素。
  2. 假如 $m$ 和 $n$ 互素,则 $\varphi(mn) = \varphi(m) * \varphi(n)$ 。

1.2. 费马小定理

费马小定理: $$ 假设 a 为一个整数,p 为一个素数,且a不是p的倍数。则 a^{p-1}-1=kp,其中 k 为一个正整数。 $$ 将上式稍作变换: $$ \frac{a^{p-1}}{p} - \frac{1}{p} = k $$ 由上式可以推得 $a^{p-1} \div p$ 和 $1 \div p$ 的余数相同,即 $a^{p-1}$ 和 $1$ 对于 $p$ 同余。数学上记作: $$ a^{p-1} \equiv 1 (mod p) $$ 同余有一个性质我们后面要用到,即 $$ 假如 a - b = kn,其中k为一个整数。则 a \equiv b (mod n) $$ 这个很好想,两数之差为 $n$ 的倍数,则两数除 $n$ 的时候余数肯定一样。

1.3. 欧拉定理

欧拉在 1736 年在费马小定理的基础上推导出了更一般化的欧拉定理: $$ 假设a为一个整数,n也为一个整数,且a与n互素。则 a^{\varphi(n)} - 1 = kn,其中k为一个正整数。 $$ 写成同余形式: $$ a^{\varphi(n)} \equiv 1 (mod n) $$ 可知,当 $n$ 为素数时,$\varphi(n) = n - 1$ ,上式可变为 $a^{n-1} \equiv 1(mod n)$ ,即费马小定理。

2. RSA 算法

2.1. RSA 算法的过程

首先直接来说一下 RSA 算法的过程,该过程可以分为四步,分别是 密钥生成密钥分发加密解密

现在 Alice 和 Bob 要用 RSA 进行通信。为了让 Bob 能加密他发送的信息,Alice 首先要生成自己的公钥和私钥:

  1. 首先随机选取两个不相等的大质数 $p$ 和 $q$ 。然后计算出乘积 $N$ ,$N = p * q$ 。$N$ 的二进制长度一定就是 RSA 公钥的二进制长度。(实际应用中,RSA密钥一般是1024位,重要场合则为2048位)
  2. 然后计算 $N$ 的欧拉函数值 $\varphi(N)$ 。$\varphi(N) = \varphi(p) * \varphi(q) = (p - 1)(q - 1)$ 。
  3. 随机选取一个整数 $e$ 。满足 $e < \varphi(N)$ 且 $e$ 与 $\varphi(N)$ 互素。此时得到了 RSA 加密的公钥,即 $(N, e)$ 。(现实中 $e$ 常取 65537)
  4. 计算出一个数 $d$ 。满足 $ed - 1 = k\varphi(N)$ ,其中 $k$ 为一个正整数。即 $ed \div \varphi(N)$ 的余数为 $1$ 。这个 $d$ 称作 $e$ 关于 $\varphi(N)$ 的模逆元。写成同余的形式就是 $ed \equiv 1 (mod \varphi(N))$ 。可以看到这个式子中有两个变量分别是 $d$ 和 $k$ ,这就相当于求一个二元方程的解,这里可以用 扩展欧几里得算法 快速求出一组整数解。此时得到了 RSA 加密的私钥,即 $(N, d)$ 。

然后 Alice 将公钥直接发给 Bob,则 Bob 发送消息之前先用公钥将要发送的信息加密:

  1. Bob 要把发送的消息先转换成数字的形式,最简单的当然是使用 ASCII 编码。然后单次要加密的数字形式的消息 $m$ 必须满足 $m < N$ 。
  2. Bob 算出一个数 $c$ ,满足 $m^e - c = kN$ ,其中 $k$ 为一个正整数 。写成同余的形式就是 $m^e \equiv c (mod N)$ 。由同余的定义可知可以确定唯一一个小于 $N$ 的 $c$ ,此时 $c$ 就是加密后的密文。同样由于要求的 $c$ 小于 $N$ ,所以可以将求 $c$ 公式改写为这样:$c = m^e mod N$ 。

然后 Bob 把密文 $c$ 传给 Alice ,Alice 收到 $c$ 后要将其解密:

  1. Alice 算出一个数 $m$ ,满足 $c^d - m = kN$ ,其中 $k$ 是一个正整数 。写成同余的形式就是 $c^d \equiv m (modN)$,这个 $m$ 在小于 $N$ 的范围内只能找到一个,则这个 $m$ 就是原文。同样由于要求的 $m$ 小于 $N$ ,所以求 $m$ 的公式可以改写成这样:$m = c^d mod N$ 。

2.2. RSA 有了公钥也无法算出私钥

公钥用于加密,明文在网络中传输。私钥用于解密,只有 Alice 才有。就算攻击者截获到了公钥,也无法因此算出私钥。

公钥是 $(N, e)$ ,私钥是 $(N, d)$ 。根据私钥生成规则 $ed - 1 = k\varphi(N)$ ,攻击者想要破解出私钥必须像生成私钥的时候那样计算出一个 $d$,而想算出 $d$ 必须有 $e$ 和 $\varphi(N)$ 。而想知道 $\varphi(N)$ 必须知道 $N$ 的两个素因数 $p$ 和 $q$ ,也就是攻击者必须对大整数 $N$ 进行因数分解。

所以结论就是如果 $N$ 可以被因数分解,$d$ 就可以被算出,也就意味着私钥被破解。

可是,大整数的因数分解,是一件非常困难的事。目前,除了暴力破解,还没有发现别的有效的办法。维基百科这样写道:

  "对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA 算法愈可靠。

  假如有人找到一种快速因数分解的算法,那么 RSA 的可靠性就会急速下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击 RSA 算法的方式。

  只要密钥长度足够长,用 RSA 加密的信息实际上是不能被解破的。"

当然,这是 2008 年的老旧信息了。没有哪一个算法可以永远不被破解。一个名叫 Shor 算法的量子算法(在量子计算机上面运作的算法)被证明在大整数因数分解问题上具有很高的效率,所以等到量子计算机更成熟的时候,可能也就是 RSA 要被替换之日了。

2.3. 为什么公钥和私钥可以用来加密和解密

现在我们就来证明一下为什么将原文 $m$ 通过加密公式 $m^e \equiv c (mod N)$ 加密成 $c$ 后,能通过解密公式 $c^d \equiv m (modN)$ 重新算回 $m$ 。

首先,加密公式 $m^e - c = k_1N$ 稍作变换,得到加密后的密文 $c$ : $$ c = m^e - k_1N $$ 将上式代入要证明的解密公式: $$ (m^e - k_1N)^d \equiv m(modN) $$ 它等同于求证: $$ m^{ed} \equiv m(modn) $$ 简要证明一下上一步。$(m^e - k_1N)^d$ 分解成多项式后,可知第一项是 $m^{ed}$ ,而后的每一项一定都包含 $N$ 的次幂,可知这些项做 $modN$ 运算的时候不影响总的结果,所以等同于求证上式。

根据私钥生成规则 $ed \equiv 1(mod\varphi(N))$ 可得: $$ ed = k_2\varphi(N) + 1 $$ 将上式代入上上式得: $$ m^{k_2\varphi(N) + 1} \equiv m(modN) $$
接下来分两种情况证明上式。

m 与 N 互质

首先同余有如下幂运算法则: $$ 如果 a \equiv b(modm),则 a^n \equiv b^n(modm) $$ 和如下乘法运算法则: $$ 如果 a \equiv b(modm) ,则 a*n \equiv b*n (modm) $$ 因为 $m$ 和 $N$ 互质,所以根据欧拉定理: $$ m^{\varphi(N)} \equiv 1(modN) $$ 将上边的同余表达式进行幂运算和乘法运算,可以得到 $$ (m^{\varphi(N)})^{k_2} * m \equiv m(modN) $$ 即 $m^{k_2\varphi(N) + 1} \equiv m(modN)$ 得证。

m 与 N 不互质

首先,$m$ 与 $N$ 不互质,说明 $m$ 与 $N$ 必定有非1公因子。而 $N$ 又等于 $p * q$ ,加上加密时候的限制条件 $m < N$ ,可以知道这个公因子要么是 $p$ 要么是 $q$ 。从而说明 $m$ 要么可以表示为 $kp$ 要么可以表示为 $kq$ 。

以 $m = kp$ 为例,由加密时的限制条件 $m < N$ 以及 $m = p * k$ ,$N = p * q$ 可知 $k < q$ ,而 $q$ 又是一个素数,所以 $k$ 必定与 $q$ 互素。既然 $k$ 和 $p$ 都与 $q$ 互素,可知 $kp$ 不可能和 $q$ 有非1公因子,所以 $m = kp$ 也和 $q$ 互素。套用欧拉定理可以得到 $$ (kp)^{\varphi(q)} \equiv 1(mod q) $$ $\varphi(q) = q - 1$ ,所以 $$ (kp)^{q-1} \equiv 1 (mod q) $$ 根据同余的幂运算法则和乘法法则可以得到 $$ [(kp)^{q-1}]^{h(p-1)} * kp \equiv kp(mod q) $$ 简化为 $$ (kp)^{h(q-1)(p-1) + 1} \equiv kp(modq) $$ 根据私钥计算公式 $ed = 1+ k\varphi(N)$ 可将上式简化 $$ (kp)^{ed} \equiv kp(mod q) $$ 由同余的定义可知,对 $q$ 同余的 $(kp)^{ed}$ 和 $kp$ 一定相差 $q$ 的倍数,所以上式可以写成 $$ (kp)^{ed} = tq + kp $$ 其中 $t$ 为一个整数。等式两边同时除以 $p$ ,得 $$ k^{ed}p^{ed-1} = \frac{tq}{p} + k $$ 可知等式左边一定是一个整数,所以右边也必须是一个整数,由于 $q$ 和 $p$ 互质,则 $t$ 必须满足 $t = t_1p$ 才能是一个整数。所以上上式可以变为 $$ (kp)^{ed} = t_1pq+kp $$ 由 $m = kp$ 和 $N = pq$ 可得 $$ m^{ed} = m + t_1N $$ 即 $$ m^{ed} \equiv m(mod N) $$
原式得到证明。

2.4. 一个小例子

来个小例子把。

第一步,随机选取两个不相等的质数 $p$ 和 $q$ 。

Alice 选择了 61 和 53 。(由上面的讨论可知,此处的 $p$ 和 $q$ 越大,就越难对他们的乘积 $N$ 因式分解)

第二步,计算乘积 $N$ 。

$N = 61 * 53 = 3233$

$N$ 的二进制长度就是最终的密钥长度。3233 写成二进制就是 110010100001 ,一共 12 位,所以密钥就是 12 位。实际应用中,RSA 密钥一般是 1024 位,在安全性要求高的场合可能是 2048 位。

第三步,计算欧拉函数 $\varphi(N)$ 。

$\varphi(N) = \varphi(p) * \varphi(q) = (p-1) * (q-1) = 3120$

第四步,随机选择一个整数 $e$ ,条件是 $1 < e < \varphi(N)$ ,且 $e$ 与 $\varphi(N)$ 互质。

Alice 在 1 到 3120 中选择了 17 。(实际应用中常选择 65537)

此时得到了公钥 $(N, e)$ ,即 $(3233, 17)$ 。

第五步,计算 $e$ 对于 $\varphi(N)$ 的模逆元 $d$ 。

即满足 $ed - 1 = k\varphi(N))$ 。将数值代入得 $17d - 1 = 3120k$ ,可以使用扩展欧几里得算法对这个二元方程求解,Alice 最终求出了一组整数解 $d = 2753$ ,$k = -15$ 。

此时得到了私钥 $(N, d)$ ,即 $(3233, 2753)$ 。

实际应用中,公钥和私钥的数据都采用ASN.1格式表达。

第六步,加密。

Alice 将算出的公钥交给 Bob 。假设 Bob 要发送的原文 $m$ 是 65,则根据加密公式 $m^e \equiv c (mod N)$ ,代入数值后为 $65^{17} \equiv c(mod 3233)$ ,可求出唯一一个大于 0 小于 3233 的 $c$ 为 2790 。于是 Bob 将 2790 传输给 Alice 。

第七步,解密。

Alice 根据解密公式 $c^d \equiv m (modN)$ ,带入数值得 $2790^{2753} \equiv m(mod 3233)$ ,可求出唯一一个大于 0 小于 3233 的 $m$ 为 65 ,于是解密成功。

ps. 别看 $2790^{2753}$ 好像很大的样子,但我用 windows 自带的计算器算上面的式子根本没用多长时间,完全没有停顿的就得出了结果。不过这也是建立在我们的 $p$ 和 $q$ 很小的前提下,正如上面所说,实际的 RSA 的 $N$ 大概在 1024 个二进制位朝上,这就不是一个小数目了,所以这也引出了一个 RSA 的缺点,就是

2.5. 思考

https://www.zhihu.com/question/25912483

走到这里,我们可以开始思考一个问题了。 在上面 RSA 加密的推导中,公钥是 $(N, e)$ 用于加密,私钥是 $(N, d)$ 用于解密。那么,用 $(N, d)$ 加密而用 $(N, e)$ 解密可不可以呢?

也就是说,用 $(N, d)$ 加密原文 $m$ ,则此时加密公式变为 $m^d \equiv c(modN)$ 。而用 $(N, e)$ 解密密文 $c$ ,则此时解密公式变为 $c^e \equiv m(modN)$ 。这样是否可行呢?答案是肯定的,或者说在数学上是肯定的。想要证明很简单,只需要像证明 RSA 那样证明被加密后的 $c$ 能被再解密成 $m$ 就行,这里就不再证明一遍了,因为如果你去看那个证明过程,你就会发现虽然 $e$ 和 $d$ 互换了,但证明过程以及结果还是一样的。

这说明了一个问题,RSA 算法计算出来的 $e$ 和 $d$ 在数学上其实是对等的,谁用来加密谁用来解密其实都行,不影响结果。但其实这只是在理论上可行,首先 RSA 生成 $e$ 和 $d$ 的方法都不一样,这其实也是有各自的考量的,总而言之 $e$ 更适合做公钥加密,$d$ 更适合做私钥解密。

那说了这么多,$(N, d)$ 用来加密 $(N, e)$ 用来解密还不是没啥用了?其实还是有用,只不过此时不叫加密和解密了,这就是下一篇博客要介绍的 RSA 数字签名!RSA 不仅可以用来加密,还能用来做认证(certificate)。在 RSA 数字签名技术中,$(N, d)$ 还是私钥,但此时它被用来加密(签名)而不是解密,$(N, e)$ 还是公钥,但此时它被用来解密(验证)而不是加密。

数字签名技术在下一篇博客 https://laihaodong.cn/2318.html

Last modification:March 14th, 2020 at 11:50 pm