RSA公钥与私钥的变化
RSA公钥通常是一对数字 (e, n),其中 e 是指数,n = p × q(p 和 q 是大素数)。在现代实践中,e 几乎总是被选择为 65537,因此公钥本质上简化为 n。私钥 d 的计算方式发生了从使用欧拉 totient 函数 φ(n) 到使用 Carmichael totient 函数 λ(n) 的悄然变化。
原始RSA论文中的私钥计算
在原始RSA论文中,私钥 d 满足 ed ≡ 1 mod φ(n),其中 φ(n) = (p-1)(q-1) 是欧拉 totient 函数。RSA的安全性基于假设:不知道 p 和 q 的情况下,计算 φ(n) 是不可行的。
变化到Carmichael's totient函数
私钥 d 的计算逐渐转变为满足 ed ≡ 1 mod λ(n),其中 λ(n) 是 Carmichael's totient 函数。λ(n) 被定义为最小的正整数,可以替代 φ(n) 在方程 a^{φ(n)} ≡ 1 mod n 中成立(当 a 与 n 互质时)。λ(n) 整除 φ(n),且对于 n = p × q(p 和 q 为奇素数),λ(n) = lcm(p-1, q-1) = (p-1)(q-1) / gcd(p-1, q-1)。
变化的原因
使用 λ(n) 替代 φ(n) 的主要动机是获得更小的私钥,从而加快解密速度。因为 λ(n) 比 φ(n) 小一个因子 gcd(p-1, q-1),理论上私钥 d 可以更小,提高计算效率。
效率提升的实证评估
然而,通过实验表明,这种效率提升微不足道。生成RSA公钥的实验显示,gcd(p-1, q-1) 通常很小:中位数为2,平均值为35.44,最大值为2370。这意味着 λ(n) 与 φ(n) 的差异通常不大,因此节省的计算资源有限。
更有效的替代方案
文章指出,如果追求更高的效率,使用 Garner's algorithm 可以带来更大的改进,而非依赖于 totient 函数的选择。
总之,RSA中从 φ(n) 到 λ(n) 的变化旨在优化私钥大小和解密速度,但实际效率增益较小,需考虑其他算法如 Garner's algorithm 来实现更显著的提升。