前言

今天在分析网易云音乐的加密参数的时候发现其用到了 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 算法目前为止是安全的。