物理

[TINY NSD] RSA 加密法

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

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

它的原理基于欧拉定理：若 $a,m$ 互质，则 $p^{\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$。

$\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$。

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

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

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

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

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

$\LARGE{\text{2.1：获取密文和公钥}}$

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

$\LARGE{\text{2.2：计算私钥}}$

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

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

$\LARGE{\text{2.3：计算两个质数}}$

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

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

但要是有人修改数据呢？

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

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

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