# RSA

* [1. 教科书式的 RSA 算法的基本流程](#1-教科书式的-rsa-算法的基本流程)
  * [1.1. 生成密钥对](#11-生成密钥对)
  * [1.2. 加密过程](#12-加密过程)
  * [1.3. 解密过程](#13-解密过程)
  * [1.4. 签名和验证](#14-签名和验证)
  * [1.5. 总结](#15-总结)
* [2. 推导 RSA 加密与解密过程](#2-推导-rsa-加密与解密过程)
  * [2.1. 问题描述](#21-问题描述)
  * [2.2. 选择公钥和私钥的关系](#22-选择公钥和私钥的关系)
  * [2.3. 加密过程](#23-加密过程)
  * [2.4. 解密过程的推导](#24-解密过程的推导)
  * [2.5. 使用模幂运算的推导](#25-使用模幂运算的推导)
  * [2.6. 应用欧拉定理](#26-应用欧拉定理)
  * [2.7. 特殊情况处理](#27-特殊情况处理)
  * [2.8. 小结](#28-小结)
* [3. 如何保证 RSA 中模逆元存在](#3-如何保证-rsa-中模逆元存在)
  * [3.1. 模逆元的定义与条件](#31-模逆元的定义与条件)
  * [3.2. 在 RSA 中的应用](#32-在-rsa-中的应用)
  * [3.3. 保证模逆元存在的条件](#33-保证模逆元存在的条件)
    * [3.3.1. 原因](#331-原因)
  * [3.4. 选择合适的 e](#34-选择合适的-e)
  * [3.5. 总结](#35-总结)
    * [3.5.1. 模逆元存在的条件](#351-模逆元存在的条件)
* [4. 使用拓展欧几里德算法求解模逆元 d（私钥）](#4-使用拓展欧几里德算法求解模逆元-d私钥)
  * [4.1. 问题描述](#41-问题描述)
  * [4.2. 欧几里德算法的基本思路](#42-欧几里德算法的基本思路)
  * [4.3. 拓展欧几里德算法求解模逆元](#43-拓展欧几里德算法求解模逆元)
    * [4.3.1. 贝祖等式](#431-贝祖等式)
  * [4.4. 用拓展欧几里德算法求 RSA 私钥指数](#44-用拓展欧几里德算法求-rsa-私钥指数)
    * [4.4.1. 第一步：使用欧几里德算法求 gcd(7, 40)](#441-第一步使用欧几里德算法求-gcd7-40)
    * [4.4.2. 第二步：回溯求解模逆元](#442-第二步回溯求解模逆元)
  * [4.5. 总结](#45-总结)
  * [4.6. 完整代码片段](#46-完整代码片段)
* [5. RSA 算法流程示例](#5-rsa-算法流程示例)
  * [5.1. 生成公钥和私钥](#51-生成公钥和私钥)
    * [5.1.1. 计算模数 n](#511-计算模数-n)
    * [5.1.2. 计算欧拉函数 φ(n)](#512-计算欧拉函数-φn)
    * [5.1.3. 检查 gcd(e, φ(n))](#513-检查-gcde-φn)
    * [5.1.4. 计算私钥指数 $d$](#514-计算私钥指数-d)
  * [5.2. 加密过程](#52-加密过程)
    * [5.2.1. 加密公式](#521-加密公式)
    * [5.2.2. 计算](#522-计算)
  * [5.3. 解密过程](#53-解密过程)
    * [5.3.1. 解密公式](#531-解密公式)
    * [5.3.2. 计算](#532-计算)
  * [5.4. 验证结果](#54-验证结果)
  * [5.5. 总结](#55-总结)
* [6. RSA 公钥算法 FAQ](#6-rsa-公钥算法-faq)
  * [6.1. RSA 算法用到的数论理论](#61-rsa-算法用到的数论理论)
  * [6.2. RSA 的缺陷](#62-rsa-的缺陷)
  * [6.3. 如果 rsa 算法中组成 n 的 p 和 q 泄漏了，敌手如何算出私钥 d ？](#63-如果-rsa-算法中组成-n-的-p-和-q-泄漏了敌手如何算出私钥-d-)
    * [6.3.1. 问题分析](#631-问题分析)
    * [6.3.2. 计算过程](#632-计算过程)
    * [6.3.3. 示例](#633-示例)
    * [6.3.4. 为什么 p 和 q 的泄露如此致命？](#634-为什么-p-和-q-的泄露如此致命)
    * [6.3.5. 如何防止p和q泄露？](#635-如何防止p和q泄露)

## 1. 教科书式的 RSA 算法的基本流程

> 教科书式的 RSA 算法不能直接使用，有安全隐患。

### 1.1. 生成密钥对

* **选择两个大素数** $p$ 和 $q$ 。
* **计算模数** $n$：

$$
n = p \times q
$$

* **计算欧拉函数** $\varphi(n)$：

$$
\varphi(n) = (p - 1) \times (q - 1)
$$

* **选择公钥指数** $e$（满足 $1 < e < \varphi(n)$ 且 $\gcd(e, \varphi(n)) = 1$）。
* **计算私钥指数** $d$（满足 $e \times d \equiv 1 \pmod{\varphi(n)}$）：

$$
d = e^{-1} \bmod \varphi(n)
$$

生成的密钥对为：

* **公钥**： $(e, n)$
* **私钥**： $(d, n)$

### 1.2. 加密过程

假设消息为整数 $M$ 且 $0 \leq M < n$ 。

**加密公式**：

$$
C = M^e \bmod n
$$

其中， $C$ 是密文。

### 1.3. 解密过程

使用私钥 $(d, n)$ 对密文 $C$ 进行解密。

**解密公式**：

$$
M = C^d \bmod n
$$

### 1.4. 签名和验证

* **签名**：使用私钥 $d$ 对消息 $M$ 生成签名 $S$：

$$
S = M^d \bmod n
$$

* **验证**：接收方使用公钥 $e$ 验证签名：

$$
M = S^e \bmod n
$$

### 1.5. 总结

RSA 的核心是利用大素数分解的困难性。其加密与解密过程通过模幂运算进行，公钥和私钥相互配合，一个加密的消息只能通过相应的私钥解密，保证了通信的安全性。

## 2. 推导 RSA 加密与解密过程

### 2.1. 问题描述

假设消息为整数 $M$ ，且满足 $0 \leq M < n$ 。加密后的密文记为 $C$ ，我们希望确保：

* 使用公钥 $(e, n)$ 加密得到：

$$
C = M^e \bmod n
$$

* 使用私钥 $(d, n)$ 解密，恢复出原始消息：

$$
M = C^d \bmod n
$$

### 2.2. 选择公钥和私钥的关系

在 RSA 算法中，我们需要选择私钥指数 $d$ 使得：

$$
e \times d \equiv 1 \pmod{\varphi(n)}
$$

这意味着：

$$
e \times d = k \cdot \varphi(n) + 1
$$

其中 $k$ 是某个整数。

### 2.3. 加密过程

加密时，使用公钥 $(e, n)$ 将明文 $M$ 转换为密文 $C$ ：

$$
C = M^e \bmod n
$$

### 2.4. 解密过程的推导

解密时，使用私钥 $(d, n)$ 对密文 $C$ 进行解密：

$$
M' = C^d \bmod n
$$

我们希望证明：

$$
M' = M
$$

### 2.5. 使用模幂运算的推导

将密文 $C = M^e \bmod n$ 代入解密公式：

$$
M' = (M^e)^d \bmod n = M^{e \cdot d} \bmod n
$$

根据关系 $e \times d = k \cdot \varphi(n) + 1$：

$$
M' = M^{k \cdot \varphi(n) + 1} \bmod n
$$

利用幂的性质：

$$
M' = M^{k \cdot \varphi(n)} \cdot M \bmod n
$$

### 2.6. 应用欧拉定理

根据 **欧拉定理**：若 $\gcd(M, n) = 1$ ，则：

$$
M^{\varphi(n)} \equiv 1 \pmod{n}
$$

因此：

$$
M^{k \cdot \varphi(n)} \equiv 1 \pmod{n}
$$

将其代入解密公式：

$$
M' = 1 \cdot M \bmod n = M
$$

### 2.7. 特殊情况处理

若 $\gcd(M, n) \neq 1$ ，则 $M$ 可能与 $p$ 或 $q$ 有公因数。实际应用中，选择足够大的素数 $p$ 和 $q$ 可避免这种情况。

为了解决这个问题，可以使用填充（padding）技术将消息转换为与 $n$ 互质的形式。

### 2.8. 小结

RSA 的加密和解密过程依赖于：

1. **模运算**。
2. **欧拉定理**： $M^{\varphi(n)} \equiv 1 \pmod{n}$ 。
3. **欧拉定理**：证明加密和解密过程的正确性。
4. **模逆元**：公钥和私钥之间的关系。

最终通过推导得到：

$$
M' = C^d \bmod n = M
$$

## 3. 如何保证 RSA 中模逆元存在

在 **RSA 算法**中，保证**模逆元 $d$** 存在的关键在于：\
选择的公钥指数 $e$ 必须与 $\varphi(n)$ 互质，即满足：

$$
\gcd(e, \varphi(n)) = 1
$$

这是必要的数学条件。下面从**数论原理**出发，解释为何这个条件能保证模逆元存在。

### 3.1. 模逆元的定义与条件

对于一个整数 $a$ 和模数 $m$ ，模逆元 $x$ 是满足：

$$
a \cdot x \equiv 1 \pmod{m}
$$

的整数 $x$ 。**模逆元存在的充要条件**是 $a$ 与 $m$ 互质，即：

$$
\gcd(a, m) = 1
$$

### 3.2. 在 RSA 中的应用

在 RSA 中：

* **公钥指数** $e$ 是公开选择的值。
* **模数** $n = p \times q$ ，其中 $p$ 和 $q$ 是两个大素数。
* **欧拉函数** $\varphi(n) = (p - 1)(q - 1)$ 。

为了保证解密有效，我们需要找到**私钥指数 $d$**，使得：

$$
e \cdot d \equiv 1 \pmod{\varphi(n)}
$$

即， $d$ 是 $e$ 在模 $\varphi(n)$ 下的模逆元。

### 3.3. 保证模逆元存在的条件

为了确保 $d$ 存在，我们要求：

$$
\gcd(e, \varphi(n)) = 1
$$

#### 3.3.1. 原因

* 如果 $\gcd(e, \varphi(n)) = 1$ ，根据**贝祖等式**：

$$
e \cdot x + \varphi(n) \cdot y = 1
$$

其中 $x$ 和 $y$ 是整数。

* 这表明 $x$ 是 $e$ 在模 $\varphi(n)$ 下的模逆元：

$$
e \cdot x \equiv 1 \pmod{\varphi(n)}
$$

### 3.4. 选择合适的 e

为了确保 $\gcd(e, \varphi(n)) = 1$ ，**通常选择较小的素数** $e$ ，如：

* $e = 3$
* $e = 5$
* $e = 65537$（常见且安全）

这些值不仅计算高效，而且容易满足与 $\varphi(n)$ 互质的条件。

### 3.5. 总结

#### 3.5.1. 模逆元存在的条件

在 **RSA 算法**中，保证模逆元 $d$ 存在的关键条件是：

$$
\gcd(e, \varphi(n)) = 1
$$

只要满足这个条件，就可以使用**拓展欧几里德算法**求得模逆元 $d$ ，从而保证加密和解密过程的正确性。

## 4. 使用拓展欧几里德算法求解模逆元 d（私钥）

### 4.1. 问题描述

RSA 加密过程为：

$$
C = M^e \bmod n
$$

解密过程为：

$$
M' = C^d \bmod n
$$

其中：

* $M$ 是明文， $C$ 是密文；
* $e$ 是公钥指数， $d$ 是私钥指数，且满足 $e \cdot d \equiv 1 \pmod{\varphi(n)}$ 。

我们的目标是通过 **拓展欧几里德算法** 来计算 $d$ ，使得：

$$
e \cdot d \equiv 1 \pmod{\varphi(n)}
$$

### 4.2. 欧几里德算法的基本思路

欧几里德算法用于计算两个整数的最大公因数 $\gcd(a, b)$ ，其过程是：

$$
a = b \cdot q + r
$$

不断更新 $a \leftarrow b$ 和 $b \leftarrow r$ 直到 $r = 0$ 。最后剩下的非零数就是 $\gcd(a, b)$ 。

### 4.3. 拓展欧几里德算法求解模逆元

#### 4.3.1. 贝祖等式

拓展欧几里德算法能够找到整数 $x$ 和 $y$ ，使得：

$$
a \cdot x + b \cdot y = \gcd(a, b)
$$

如果 $\gcd(a, b) = 1$ ，则：

$$
a \cdot x \equiv 1 \pmod{b}
$$

这表明 $x$ 是 $a$ 的模 $b$ 下的 **模逆元**。

### 4.4. 用拓展欧几里德算法求 RSA 私钥指数

假设公钥指数 $e = 7$ ，且 $\varphi(n) = 40$ 。我们需要找到私钥指数 $d$ ，使得：

$$
7 \cdot d \equiv 1 \pmod{40}
$$

#### 4.4.1. 第一步：使用欧几里德算法求 gcd(7, 40)

我们按照如下步骤求解：

$$
40 = 7 \times 5 + 5
$$

$$
7 = 5 \times 1 + 2
$$

$$
5 = 2 \times 2 + 1
$$

$$
2 = 1 \times 2 + 0
$$

因此：

$$
\gcd(7, 40) = 1
$$

这表明 $7$ 和 $40$ 互质，因此模逆元 $d$ 存在。

#### 4.4.2. 第二步：回溯求解模逆元

从最后一步回溯，整理出 **贝祖等式**：

* $1 = 5 - 2 \times 2$
* 代入 $2 = 7 - 5 \times 1$：

$$
1 = 5 - (7 - 5 \times 1) \times 2 = 5 \times 3 - 7 \times 2
$$

* 再代入 $5 = 40 - 7 \times 5$：

$$
1 = (40 - 7 \times 5) \times 3 - 7 \times 2 = 40 \times 3 - 7 \times 17
$$

所以我们得到了：

$$
1 = 40 \times 3 - 7 \times 17
$$

这意味着：

$$
-17 \equiv 23 \pmod{40}
$$

因此， $d = 23$ 是 $e = 7$ 在模 $40$ 下的模逆元。

### 4.5. 总结

通过拓展欧几里德算法，我们求得了私钥指数 $d = 23$ 。\
验证加密和解密过程：

* **加密**：

$$C = M^e \bmod n$$

* **解密**：

$$M' = C^d \bmod n$$

通过数论原理可证明解密结果 $M'$ 与明文 $M$ 相同。

### 4.6. 完整代码片段

```python
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

# 示例：计算 7 在模 40 下的模逆元
e = 7
phi_n = 40
gcd, d, _ = extended_gcd(e, phi_n)

# 确保 gcd 为 1
if gcd == 1:
    d = d % phi_n
    print(f"模逆元 d = {d}")
else:
    print("模逆元不存在")
```

## 5. RSA 算法流程示例

本示例将详细展示 RSA 加密和解密的全过程，使用具体参数：

* 两个素数： $p = 5, q = 11$
* 公钥指数： $e = 3$
* 明文： $m = 2$

### 5.1. 生成公钥和私钥

#### 5.1.1. 计算模数 n

模数 $n$ 是两个素数 $p$ 和 $q$ 的乘积：

$$
n = p \cdot q = 5 \cdot 11 = 55
$$

#### 5.1.2. 计算欧拉函数 φ(n)

欧拉函数 $\varphi(n)$ 是：

$$
\varphi(n) = (p - 1) \cdot (q - 1) = (5 - 1) \cdot (11 - 1) = 4 \cdot 10 = 40
$$

#### 5.1.3. 检查 gcd(e, φ(n))

公钥指数 $e$ 必须与 $\varphi(n)$ 互质：

$$
\gcd(3, 40) = 1
$$

由于 $\gcd(e, \varphi(n)) = 1$ ， $e = 3$ 是有效的选择。

**因此公钥为 $(3, 55)$ 。**

#### 5.1.4. 计算私钥指数 $d$

私钥指数 $d$ 是 $e$ 在模 $\varphi(n)$ 下的**模逆元**，满足：

$$
e \cdot d \equiv 1 \pmod{\varphi(n)}
$$

求解 $d$：

$$
3 \cdot d \equiv 1 \pmod{40}
$$

使用**拓展欧几里德算法**求出 $d = 27$。

**因此私钥为 $(27, 55)$ 。**

### 5.2. 加密过程

#### 5.2.1. 加密公式

密文 $c$ 通过如下公式计算：

$$
c = m^e \bmod n
$$

#### 5.2.2. 计算

将明文 $m = 2$ 带入公式：

$$
c = 2^3 \bmod 55 = 8 \bmod 55 = 8
$$

因此，密文为 $c = 8$。

### 5.3. 解密过程

#### 5.3.1. 解密公式

解密时，通过如下公式计算明文：

$$
m' = c^d \bmod n
$$

#### 5.3.2. 计算

将密文 $c = 8$ 和私钥指数 $d = 27$ 带入公式：

$$
m' = 8^{27} \bmod 55
$$

为了简化计算，我们使用模幂运算：

1. $8^2 \equiv 64 \equiv 9 \pmod{55}$
2. $8^4 \equiv 9^2 = 81 \equiv 26 \pmod{55}$
3. $8^8 \equiv 26^2 = 676 \equiv 16 \pmod{55}$
4. $8^{16} \equiv 16^2 = 256 \equiv 36 \pmod{55}$
5. $8^{24} \equiv 36 \cdot 16 = 576 \equiv 26 \pmod{55}$

下面再计算 $8^3 \bmod 55$ :

$$
8^3 \bmod 55 = (8^2 \cdot 8) \bmod 55
$$

代入已知的 $8^2 \equiv 9 \pmod{55}$：

$$
8^3 \equiv 9 \cdot 8 \pmod{55}
$$

计算乘积：

$$
9 \cdot 8 = 72
$$

然后取模 $55$：

$$
72 \bmod 55 = 17
$$

因此：

$$
8^{27} = 8^{24} \cdot 8^3 \equiv 26 \cdot 17 = 442 \equiv 2 \pmod{55}
$$

最终解密得到的明文为：

$$
m' = 2
$$

这种**逐步累乘**的方法，也称为**重复平方法**，是计算大整数模幂的标准技巧。它通过不断使用之前的结果来减少计算量，非常适合用于实现高效的模运算。

### 5.4. 验证结果

解密后的明文 $m' = 2$ 与原始明文 $m = 2$ 一致。

### 5.5. 总结

在本例中，我们演示了 RSA 算法的完整流程：

1. **公钥**： $(e, n) = (3, 55)$
2. **私钥**： $d = 27$
3. **加密**：明文 $m = 2$ 加密为密文 $c = 8$
4. **解密**：密文 $c = 8$ 解密为明文 $m' = 2$

通过数论中的模逆元和模幂运算，RSA 算法成功实现了安全的加密和解密。

## 6. RSA 公钥算法 FAQ

### 6.1. RSA 算法用到的数论理论

* 伪随机数生成
* 素数检测
* 群论（在有限循环乘法群中执行运算）
* 欧拉公式
* 欧拉定理
* 贝祖等式
* 扩展欧几里德算法（计算私钥 d 时用到）
* 中国剩余定理 (m 和 n 不互质时用到)
* 费马小定理 (m 和 n 不互质时用到)

### 6.2. RSA 的缺陷

TBD

### 6.3. 如果 rsa 算法中组成 n 的 p 和 q 泄漏了，敌手如何算出私钥 d ？

非常好的问题！ 这个问题直击了RSA算法的安全性核心。

#### 6.3.1. 问题分析

如果攻击者获得了组成模数 $n$ 的两个大素数 $p$ 和 $q$ ，那么他们就可以很容易地计算出私钥 $d$ 。这是因为 RSA 算法的安全性正是建立在大整数分解的困难性之上的。一旦 $n$ 被分解，整个加密体系就会变得脆弱。

#### 6.3.2. 计算过程

**计算欧拉函数 $\varphi(n)$** :

如果已知 $p$ 和 $q$ ，那么欧拉函数 $\varphi(n)$ 可以很容易地计算出来：

$$
\varphi(n) = (p-1)(q-1)
$$

**求解解密指数 $d$** :

根据 RSA 算法的定义，解密指数 $d$ 满足以下同余式：

$$
e \ast d \equiv 1 \pmod{\varphi(n)}
$$

其中， $e$ 是公钥中的加密指数。 我们可以使用扩展欧几里得算法来高效地求解这个线性同余方程，从而得到 $d$ 的值。

#### 6.3.3. 示例

假设：

* $p = 11, q = 13$
* $n = p \* q = 143$
* ${\varphi(n)} = (p-1)(q-1) = 120$
* 公钥 $e = 7$

求解 $d$ ： 我们需要找到一个整数 $d$ ，使得：

$$
7d \equiv 1 \pmod{120}
$$

使用**扩展欧几里得算法**，可以得到 $d = 103$ 。

因此，私钥为 $(103, 143)$ 。

#### 6.3.4. 为什么 p 和 q 的泄露如此致命？

* **欧拉函数直接计算**： 一旦知道 $p$ 和 $q$ ， ${\varphi(n)}$ 的计算变得非常简单。
* **扩展欧几里得算法高效**： 求解线性同余方程是计算机科学中的一个基本问题，扩展欧几里得算法能够在多项式时间内给出解。

#### 6.3.5. 如何防止p和q泄露？

* 选择足够大的素数： $p$ 和 $q$ 的位数越大，分解 $n$ 的难度就越大。实际应用中， $p$ 和 $q$ 的位数通常非常大，例如 $2048$ 位或更高。
* 安全地生成密钥： 使用高质量的随机数生成器来产生 $p$ 和 $q$ 。
* 保护私钥： 私钥必须妥善保管，避免泄露。