[!info] related notes 密码学 算法面试题型 MOC

RSA算法

1. 简介

RSA 是 1977 年由 Rivest、Shamir 和 Adleman 三人提出的，是目前应用最广泛的公钥密码体制。 它的安全性基于大整数分解的困难性。

2. 密钥生成步骤

RSA 的密钥生成依赖于数论中的欧拉函数。步骤如下：

Related: 非对称密码学（Asymmetric-Encryption）

1. 选择素数：选取两个足够大的素数 $p$ 和 $q$。
2. 计算模数：计算 $n = p \times q$。($n$ 的长度就是密钥长度，如 2048 位)。
3. 计算欧拉函数：$\phi(n) = (p-1)(q-1)$。
4. 选择公钥指数：选择一个整数 $e$，满足 $1 < e < \phi(n)$ 且 $gcd(e, \phi(n)) = 1$ ($e$ 与 $\phi(n)$ 互质)。
5. 计算私钥指数：计算 $d$，使得 $e \times d \equiv 1 \pmod{\phi(n)}$ (即 $d$ 是 $e$ 的模逆元)。

• 公钥 (PK)：${e, n}$
• 私钥 (SK)：${d, n}$ (实际应用中通常包含 $p, q$ 以加速计算)

3. 加密与解密

假设明文为 $M$，密文为 $C$ (且 $M < n$)：

• 加密过程：

  $$

C = M^e \pmod n

$$

• 解密过程：

$$

M = C^d \pmod n

$$

4. 安全性分析

• 攻击 RSA 的核心在于从公钥 $n$ 分解出 $p$ 和 $q$。一旦 $n$ 被分解，就能计算出 $\phi(n)$，进而通过公钥 $e$ 计算出私钥 $d$。
• 推荐长度：为了安全，目前建议 $n$ 至少为 2048 位。

---

相关链接：

• 非对称密码学（Asymmetric-Encryption）
• 数字签名