RSA秘钥生成
公钥与私钥的产生¶
RSA 密钥由**公钥（n, e）**和**私钥 d**组成。
步骤 1：选择素数¶
选择两个**大且互异的素数** \(p\) 和 \(q\)：
- 在现代系统中，通常选择**每个约 1024 比特**的素数；
- 这使得 \(n = pq\) 约为 2048 比特（2048 位 RSA）；
- \(p\) 和 \(q\) 必须**随机且独立**地从极大的素数空间中选取；
- \(p\) 和 \(q\) 必须严格保密。
步骤 2：计算模数 \(n\)¶
\[
n = p \cdot q
\]
- \(n\) 是**公钥和私钥的共同模数**；
- \(n\) 的比特长度通常被称为“RSA 密钥长度”；
- \(n\) 会公开发布。
步骤 3：计算卡迈克尔函数 \(\lambda(n)\)¶
令： $$ \lambda(n) = \operatorname{lcm}(p-1,\, q-1) $$ 因为：
- \(p, q\) 为素数；
- \(\lambda(p)=p-1,\ \lambda(q)=q-1\)；
所以： $$ \lambda(n)=\operatorname{lcm}(p-1,q-1) $$ 可通过欧几里得算法计算，因为： $$ \operatorname{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)} $$ \(\lambda(n)\) 必须保密。
步骤 4：选择公钥指数 \(e\)¶
选择整数 \(e\)，满足： $$ 1 < e < \lambda(n),\quad \gcd(e,\lambda(n)) = 1 $$ 常见选择：
- 最常用： \(e = 2^{16}+1 = 65537\)
- 优点：运算快、结构简单、安全性良好
- 理论上最小可选值是 \(e=3\)，但在不安全填充下可能导致攻击，因此**很少使用**。
\(e\) 会作为公钥的一部分公开。
步骤 5：计算私钥指数 \(d\)¶
计算： $$ d \equiv e^{-1} \pmod{\lambda(n)} $$ 即求解： $$ de \equiv 1 \pmod{\lambda(n)} $$ 这等价于求解**贝祖等式**，可用**扩展欧几里得算法**高效计算。
- \(d\) 必须严格保密。
- 一旦计算出 \(d\)，在理论上可以丢弃 \(p,q,\lambda(n)\)，但在高性能实现中通常保留它们。
关于欧拉函数与卡迈克尔函数的区别¶
原始 RSA 论文使用的是： $$ \varphi(n) = (p-1)(q-1) $$ 而现代实现更倾向使用： $$ \lambda(n)=\operatorname{lcm}(p-1,q-1) $$ 原因：
- \(\lambda(n) \mid \varphi(n)\)，因此两者都能工作；
- 但用 \(\varphi(n)\) 计算的 \(d\) 可能比必要的大；
- 一些标准（如 FIPS 186-4）要求 \(d < \lambda(n)\)。
若得到过大的 \(d\)，可简单取： $$ d := d \bmod \lambda(n) $$ 即可修正。
密钥生成方向的历史变化¶
- 原始 RSA（1977）： 先选 \(d\)，再计算 \(e\)。
- 现代实现（如 PKCS#1）： 先选固定小 \(e\)，再计算 \(d\)。
原因：
- 小而固定的 \(e\) 让**公钥运算更快**；
- \(d\) 仍足够大，不损害安全性。