物理

[TINY NSD] RSA 加密法

RSA 加密法与常见的加密法不同。

因为它是一种非对称加密法，即加密和解密的过程不同。

它的原理基于欧拉定理：若 $a,n$ 互质，则 $a^{\varphi\left(n\right)}\equiv1\pmod{n}$。

$\huge{\text{1：RSA 的加密/解密过程}}$

假设 Alice 想用 RSA 向 Bob 发送一条消息，应该怎么做呢？

$\LARGE{\text{1.1：密钥生成}}$

首先 Bob 需要生成一组密钥。

$\Large{\text{1.1.1：选择素数}}$

Bob 需要选择两个大质数 $p,q$，显然素数越大越好，但不能太大，只需要几千位就够了，否则接下来计算会比较慢。

$\Large{\text{1.1.2：计算模数}}$

模数 $n=pq$，直接把 $pq$ 相乘就可以了。

$\Large{\text{1.1.3：计算欧拉函数}}$

这时 $\varphi\left(n\right)=\left(p-1\right)\left(q-1\right)$，同样非常简单。

$\Large{\text{1.1.4：计算公钥}}$

你需要在 $1\sim\varphi\left(n\right)$ 中选择一个与 $\varphi\left(n\right)$ 互质的整数 $e$。

为了计算更快，$e$ 应该为较小的，二进制表示中含较少 $1$ 的质数，例如 $3,5,17,257,65537$ 等。

$\Large{\text{1.1.5：计算私钥}}$

计算 $d=e^{-1}$，即找到使 $de\equiv1\pmod{\varphi\left(n\right)}$ 成立的最小正整数 $d$。

$\Large{\text{1.1.6：发送公钥}}$

这时，Bob 得到了公钥 $\left(n,e\right)$ 和私钥 $\left(n,d\right)$。Bob 需要妥善的保存私钥，然后把公钥发送给 Alice。注意，即使别人知道了公钥没事，但别人知道私钥就有事了。

$\LARGE{\text{1.2：加密}}$

当 Alice 接收到 Bob 发送的公钥之后，就可以开始加密数据了。

$\Large{\text{1.2.1：准备明文}}$

你需要把想发送的信息转换为一个整数。

设这个整数为 $M$。

注意，要求 $M\lt n$，因为欧拉定理只能保证同余。

$\Large{\text{1.2.2：计算密文}}$

Alice 知道公钥 $\left(n,e\right)$，所以可以计算密文 $C=M^e\bmod n$。然后把密文 $C$ 发送给 Bob。

$\LARGE{\text{1.3：解密}}$

当 Bob 接收到 Alice 发送的密钥 $C$ 后，就可以开始解密数据了。

$\Large{\text{1.3.1：计算明文}}$

Bob 利用自己保存的公钥 $\left(n,d\right)$，计算明文 $M'=C^d\bmod n$，根据欧拉定理，$M\equiv M'\pmod{n}$，所以 Bob 成功的计算出了明文。

$\Large{\text{1.3.2：恢复原文}}$

按照约定的方式，把整数 $M$ 转换为原文。

于是一次加密和解密就完成了。

$\huge{\text{2：RSA 的加密/解密过程的优点}}$

$\LARGE{\text{2.1：机密性}}$

假设我不是 Bob，但我想要知道 Alice 发送了什么内容，应该怎么做？

我们可以轻易的获得 $n,e,C$ 三个数，因为它们都曾在网络中传输。但由于 HTTPS 协议的出现，这个步骤变难了。

现在只需要知道私钥就能获得密文。

私钥 $d$ 是在模 $\varphi\left(n\right)$ 意义下 $e$ 的逆。所以我们只需要知道 $\varphi\left(n\right)$ 的值，就可以求出 $d$，从而解密信息。

可以得到 $\varphi\left(n\right)=pq-p-q+1=n-p-q+1$。不幸的是，我们只能通过分解 $pq$ 来获得 $p+q$。但此时面对几千位的 $pq$，没有合适的（适用于普通计算机的）算法算出 $p$ 和 $q$（在量子计算机普及之前）。

所以我们得到，通过 RSA 加密的数据不会被别人看到。

但要是有人修改数据呢？

$\huge{\text{3：RSA 的数字签名/验证过程}}$

假设 Alice 想向 Bob 发送一条消息，并附上数字签名，以确保数据没有被篡改，应该怎么做？

$\LARGE{\text{3.1：密钥生成}}$

Alice 需要生成公钥和私钥，过程与前文相同。把公钥 $\left(n,d\right)$ 公开，并自己妥善保存私钥。

$\LARGE{\text{3.2：签名生成}}$

$\Large{\text{3.2.1：计算摘要}}$

选择一个哈希函数（如 SHA-256），计算信息摘要 $H$，要求 $H\lt n$。

$\Large{\text{3.2.2：使用私钥签名}}$

计算签名 $S=H^d\bmod n$，然后把签名 $S$ 和发送的信息 $M$ 发送给 Bob。

$\LARGE{\text{3.3：验证签名}}$

Bob 收到 $S$ 和 $M$ 之后，需要验证信息是否被篡改。

$\Large{\text{3.3.1：计算摘要}}$

Bob 使用与 Alice 约定好的哈希函数计算 $M$ 的摘要 $H$。

$\Large{\text{3.3.2：恢复摘要}}$

Bob 通过签名恢复摘要 $H'=S^e\bmod n$。

$\Large{\text{3.3.3：比较摘要}}$

Bob 比较 $H$ 和 $H'$。

如果 $H=H'$，说明信息和签名是正确的。

如果 $H\neq H'$，说明消息被篡改或签名不正确或公钥不正确，应该请求 Alice 重新发送签名和消息。

$\huge{\text{4：RSA 的数字签名/验证过程的优点}}$

$\LARGE{\text{4.1：真实性}}$

签名 $S$ 只能由 Alice 的私钥 $d$ 生成，因为其他人不知道私钥 $d$，这保证了信息一定是 Alice 发出的。

$\LARGE{\text{4.2：完整性}}$

因为 $H=H'$，说明 Bob 接收到的信息 $M$ 与 Alice 发送的信息一致。

$\LARGE{\text{4.3：不可否认性}}$

Alice 无法否认自己发送了签名，因为只有 Alice 有私钥 $d$。

$\huge{\text{5：RSA 中需要的算法}}$

$\LARGE{\text{5.1：密钥生成阶段}}$

$\Large{\text{5.1.1：FFT 乘法}}$

这个算法能快速计算乘法，运用在计算 $n=pq$ 和 $\varphi\left(n\right)=\left(p-1\right)\left(q-1\right)$ 时。

$\Large{\text{5.1.2：扩展欧几里德算法}}$

这个算法能快速求逆，以获得私钥 $d=e^{-1}$。这就是辗转相除法的扩展形式。自己去查阅相关资料。

$\LARGE{\text{5.2：加密/解密/签名生成/签名验证阶段}}$

$\Large{\text{5.2.1：Hash 函数}}$

Hash 函数能把一段数据映射到一段固定长度的数。在签名时用到。

它应该满足以下性质：

如果你知道 $\operatorname{Hash}{\left(n\right)}$，你难以计算出 $n$。

如果有一个数 $n$，很难找到 $m$，使得 $\operatorname{Hash}{\left(n\right)}=\operatorname{Hash}{\left(m\right)}$。

$\Large{\text{5.2.2：快速幂算法}}$

生成密文、解密密文、生成签名、验证签名时都要用。

（全文完）