RSA

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

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

1.1. 生成密钥对

  • 选择两个大素数 $p$ 和 $q$ 。

  • 计算模数 $n$：

n=p×qn = p \times q

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

φ(n)=(p−1)×(q−1)\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 mod φ(n)d = e^{-1} \bmod \varphi(n)

生成的密钥对为：

  • 公钥： $(e, n)$

  • 私钥： $(d, n)$

1.2. 加密过程

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

加密公式：

C=Me mod nC = M^e \bmod n

其中， $C$ 是密文。

1.3. 解密过程

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

解密公式：

M=Cd mod nM = C^d \bmod n

1.4. 签名和验证

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

S=Md mod nS = M^d \bmod n

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

M=Se mod nM = S^e \bmod n

1.5. 总结

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

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

2.1. 问题描述

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

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

C=Me mod nC = M^e \bmod n

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

M=Cd mod nM = C^d \bmod n

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

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

e×d≡1(modφ(n))e \times d \equiv 1 \pmod{\varphi(n)}

这意味着：

e×d=k⋅φ(n)+1e \times d = k \cdot \varphi(n) + 1

其中 $k$ 是某个整数。

2.3. 加密过程

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

C=Me mod nC = M^e \bmod n

2.4. 解密过程的推导

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

M′=Cd mod nM' = C^d \bmod n

我们希望证明：

M′=MM' = M

2.5. 使用模幂运算的推导

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

M′=(Me)d mod n=Me⋅d mod nM' = (M^e)^d \bmod n = M^{e \cdot d} \bmod n

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

M′=Mk⋅φ(n)+1 mod nM' = M^{k \cdot \varphi(n) + 1} \bmod n

利用幂的性质：

M′=Mk⋅φ(n)⋅M mod nM' = M^{k \cdot \varphi(n)} \cdot M \bmod n

2.6. 应用欧拉定理

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

Mφ(n)≡1(modn)M^{\varphi(n)} \equiv 1 \pmod{n}

因此：

Mk⋅φ(n)≡1(modn)M^{k \cdot \varphi(n)} \equiv 1 \pmod{n}

将其代入解密公式：

M′=1⋅M mod n=MM' = 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′=Cd mod n=MM' = C^d \bmod n = M

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

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

gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1

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

3.1. 模逆元的定义与条件

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

a⋅x≡1(modm)a \cdot x \equiv 1 \pmod{m}

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

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

3.2. 在 RSA 中的应用

在 RSA 中：

  • 公钥指数 $e$ 是公开选择的值。

  • 模数 $n = p \times q$ ，其中 $p$ 和 $q$ 是两个大素数。

  • 欧拉函数 $\varphi(n) = (p - 1)(q - 1)$ 。

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

e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}

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

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

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

gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1

3.3.1. 原因

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

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

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

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

e⋅x≡1(modφ(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,φ(n))=1\gcd(e, \varphi(n)) = 1

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

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

4.1. 问题描述

RSA 加密过程为：

C=Me mod nC = M^e \bmod n

解密过程为：

M′=Cd mod nM' = C^d \bmod n

其中：

  • $M$ 是明文， $C$ 是密文；

  • $e$ 是公钥指数， $d$ 是私钥指数，且满足 $e \cdot d \equiv 1 \pmod{\varphi(n)}$ 。

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

e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}

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

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

a=b⋅q+ra = b \cdot q + r

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

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

4.3.1. 贝祖等式

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

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

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

a⋅x≡1(modb)a \cdot x \equiv 1 \pmod{b}

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

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

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

7⋅d≡1(mod40)7 \cdot d \equiv 1 \pmod{40}

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

我们按照如下步骤求解：

40=7×5+540 = 7 \times 5 + 5
7=5×1+27 = 5 \times 1 + 2
5=2×2+15 = 2 \times 2 + 1
2=1×2+02 = 1 \times 2 + 0

因此：

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

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

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

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

  • $1 = 5 - 2 \times 2$

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

1=5−(7−5×1)×2=5×3−7×21 = 5 - (7 - 5 \times 1) \times 2 = 5 \times 3 - 7 \times 2

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

1=(40−7×5)×3−7×2=40×3−7×171 = (40 - 7 \times 5) \times 3 - 7 \times 2 = 40 \times 3 - 7 \times 17

所以我们得到了：

1=40×3−7×171 = 40 \times 3 - 7 \times 17

这意味着：

−17≡23(mod40)-17 \equiv 23 \pmod{40}

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

4.5. 总结

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

  • 加密：

C=Me mod nC = M^e \bmod n

  • 解密：

M′=Cd mod nM' = C^d \bmod n

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

4.6. 完整代码片段

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⋅q=5⋅11=55n = p \cdot q = 5 \cdot 11 = 55

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

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

φ(n)=(p−1)⋅(q−1)=(5−1)⋅(11−1)=4⋅10=40\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(3, 40) = 1

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

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

5.1.4. 计算私钥指数 $d$

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

e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}

求解 $d$：

3⋅d≡1(mod40)3 \cdot d \equiv 1 \pmod{40}

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

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

5.2. 加密过程

5.2.1. 加密公式

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

c=me mod nc = m^e \bmod n

5.2.2. 计算

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

c=23 mod 55=8 mod 55=8c = 2^3 \bmod 55 = 8 \bmod 55 = 8

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

5.3. 解密过程

5.3.1. 解密公式

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

m′=cd mod nm' = c^d \bmod n

5.3.2. 计算

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

m′=827 mod 55m' = 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$ :

83 mod 55=(82⋅8) mod 558^3 \bmod 55 = (8^2 \cdot 8) \bmod 55

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

83≡9⋅8(mod55)8^3 \equiv 9 \cdot 8 \pmod{55}

计算乘积：

9⋅8=729 \cdot 8 = 72

然后取模 $55$：

72 mod 55=1772 \bmod 55 = 17

因此：

827=824⋅83≡26⋅17=442≡2(mod55)8^{27} = 8^{24} \cdot 8^3 \equiv 26 \cdot 17 = 442 \equiv 2 \pmod{55}

最终解密得到的明文为：

m′=2m' = 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)$ 可以很容易地计算出来：

φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1)

求解解密指数 $d$ :

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

e∗d≡1(modφ(n))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≡1(mod120)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$ 。

  • 保护私钥： 私钥必须妥善保管，避免泄露。

Previous数论进阶NextFAQ

Last updated

Was this helpful?