前言

今天在分析网易云音乐的加密参数的时候发现其用到了 RSA 加密算法,就在这里写一下它的原理吧,还是比较有意思的。


首先 RSA 是一种非对称加密算法,也就是加密和解密需要使用不同的密钥,与之相对的是对称加密算法,使用相同的密钥就可以完成加密与解密。

前置知识点

要了解 RSA 加密算法,最好是能有一些数论的基础,理解以下几个内容。

欧拉函数

在数论中,对正整数n,欧拉函数 $ {\varphi (n)} $ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。

例如 ${\varphi (8)=4}$,因为 $1$, $3$, $5$, $7$ 均和 $8$ 互质。

而当 $n$ 为质数时,${\varphi (n)}=n-1$。

并且欧拉函数为积性函数,即是说若 $m$, $n$ 互质,${\varphi (mn)=\varphi (m)\varphi (n)}$。

例如:

$$ \begin{aligned} \varphi (72) &=\varphi (2^{3}\times 3^{2})\\ &=2^{3-1}(2-1)\times 3^{2-1}(3-1)\\ &=2^{2}\times 1\times 3\times 2\\ &=24 \end{aligned} $$

费马小定理

假如 $a$ 是一个整数,$p$ 是一个质数,那么 $a^p-a$ 是 $p$ 的倍数,可以表示为

$$ a^{p}\equiv a{\pmod {p}} $$

这个表达式的意思就是 $a^p ÷ p$ 与 $a ÷ p$ 的余数相同(同余)。

如果 $a$ 不是 $p$ 的倍数,这个定理也可以写成

$$ a^{{p-1}}\equiv 1{\pmod {p}} $$

这个书写方式更加常用。

模逆元

模逆元也称为模倒数,或者模逆元

一整数 $a$ 对同余 $n$ 之模逆元是指满足以下公式的整数 $b$

$$ {a^{-1}\equiv b{\pmod {n}}.} $$

也可以写成以下的式子

$$ {ab\equiv 1{\pmod {n}}.} $$

也就是说当 $b$ 满足 $ab ÷ n$ 的余数为 $1$,就可以说 $b$ 为 $a$ 关于 $n$ 的模逆元。

「$a$ 和 $n$ 互质」为「存在 $a$ 关于 $n$ 的模逆元」的充分必要条件。

RSA 加密算法

公钥与私钥

RSA 加密算法通过以下方式来生成公钥与私钥:

随意选择两个大的素数 $p$ 和 $q$,且 $p \neq q$,计算 $N = pq$。

这里的 $p$ 与 $q$,数字越大则越安全。

比如 $p=67$,$q=71$,$N=p×q=4757$,转换为二进制为 $1001010010101$,长度 13 位,则该加密算法即为 13 位。实际使用中,通常为 1024 和 2048 甚至更高位,位数越长越安全。
计算欧拉函数 ${\varphi (N)}$。

因为 $p$ 与 $q$ 均为质数,所以可以得到 ${\displaystyle r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)}$。

随机选择一个数 $e$,满足 $1 < e < r$ 且 $e$ 与 $r$ 互质。

现在,我们就得到了本次加密的公钥 $(N, e)$。

求 $e$ 关于 $r$ 的模逆元 $d$。

找到一个数 $d$,满足 $ed\equiv 1{\pmod {r}}$,也就是 $ed÷r$ 的余数为 $1$。

现在,本次加密的私钥也有了,就是 $(N, d)$。
加密完成,销毁 $p$ 与 $q$。

消息加密

假设我们有一个需要加密的消息 m,首先通过特定算法将其转化为一个小于 $N$ 的非负整数 $n$,如果消息长度超过 $N$,可以将消息进行分段处理。通过下面的公式可以将 $n$ 加密为密文 $c$:

$$ {c\equiv n^{e}{\pmod {N}}} $$

其中的 $N$ 和 $e$ 即为刚才获得的公钥,得到的密文 $c$ 就是 $n^e ÷ N$ 的余数,这样就完成了使用公钥 $(N, e)$ 对消息 m 的加密。

消息解密

现在我们有加密后的密文 $c$,要使用私钥 $(N, d)$ 进行解密,有以下公式:

$$ {n\equiv c^{d}{\pmod {N}}} $$

通过计算 $c^d ÷ N$,就可以得到其余数 $n$,也就是经过数字化处理的明文 m,可以很轻易地还原回来。

安全性

要想解密使用 RSA 加密的内容,就必须使用私钥进行解密,但是如果有人想暴力破解私钥呢?

由私钥的生成原理可知,$d$ 为 $e$ 关于 $r$ 的模逆元,所以要得到 $d$,就要计算 $r$,也就是 ${\varphi (n)}$。

而由 ${\varphi (n)}$ 的计算公式 ${\varphi (N)=(p-1)(q-1)}$,必须得到 $p$ 和 $q$ 两个数才能算出 ${\varphi (n)}$。

但是要通过计算得到 $p$ 和 $q$,就只能对 $N$ 进行质因分解,而 $N$ 是一个二进制上千位的数,要对这样的数进行分解是非常困难的,目前我们的个人计算机还远无法进行这样的运算,除非使用量子计算机,所以可以认为 RSA 算法目前为止是安全的。

If you think my article is useful to you, please feel free to appreciate