RSA 加密算法的流程
1️⃣ 密钥生成
你的步骤是标准的 RSA：
-
选大质数 (p, q)
- 通常 1024 位以上（现代安全要求 2048 位以上）
- 确保无法被高效分解
-
计算模数 $ (n = p \times q)$
- 用于公钥和私钥
- 明文和密文都需小于 (n)
-
计算欧拉函数 \((\phi(n) = (p-1)(q-1))\)
- 保证后续公私钥关系成立
-
选择公钥 (e)
- \((1 < e < \phi(n))\)，且 \((\gcd(e, \phi(n)) = 1)\)
- 常用 \((e=65537)\)，兼顾安全与效率
-
计算私钥 (d)
- 模逆元：\(((d \times e) \mod \phi(n) = 1)\)
- 确保解密可逆
最终公钥 \(((e, n))\)，私钥 \(((d, n))\)。
💡 补充：p, q, φ(n) 一旦生成私钥后应该立即销毁，防止泄露导致私钥被推导。
2️⃣ 加密解密流程
- 加密：\((c = m^e \mod n)\)
- 解密：\((m = c^d \mod n)\)
注意：明文 (m) 必须小于 (n)，实际应用中通常会先做 分块或填充（Padding），如 PKCS#1 或 OAEP，否则大消息无法直接加密。
3️⃣ 为什么能解密
基于 欧拉定理：
\(
[
m^{\phi(n)} \equiv 1 \pmod{n} \quad (\text{如果 } \gcd(m,n)=1)
]
\)
因为 (d) 是 (e) 的模逆元：
\(
[
e \cdot d = k \cdot \phi(n) + 1
]
\)
所以解密：
\(
[
c^d = (m^e)^d = m^{ed} = m^{k \phi(n) + 1} = (m^{\phi(n)})^k \cdot m \equiv 1^k \cdot m \equiv m \pmod{n}
]
\)
这解释了为什么公钥加密后，私钥能解密还原明文。
4. 关键特性
-
非对称性：公钥可公开，私钥必须保密
-
安全性基础：依赖大整数因式分解困难性
-
注意事项：
- 明文不能直接大于 n
- 实际系统加密时通常使用 混合加密：先对数据用对称加密（AES），再用 RSA 加密对称密钥
- 需要做填充，防止简单明文攻击