A Quiet Change to RSA
7 months ago
- #Cryptography
- #RSA
- #Euler's totient function
- RSA公钥由一对(e, n)组成，其中e是指数，n是两个大素数p和q的乘积。
- 最初RSA方案是先选择私钥d再计算e，但现在改为先选择e（通常为65537）再计算d。
- 原始RSA论文使用欧拉函数φ(n) = (p−1)(q−1)来建立e和d之间的关系。
- RSA的安全性依赖于在不知道p和q的情况下难以计算φ(n)。
- 卡迈克尔函数λ(n)后来取代了欧拉函数φ(n)用于计算d，这使得私钥更小且解密更快。
- λ(n)被定义为能满足欧拉定理且能整除φ(n)的最小正整数。
- 改用卡迈克尔函数后，λ(n)会比φ(n)小gcd(p−1, q−1)倍。
- 实验数据显示：在100次测试样本中，(p−1)和(q−1)的最大公约数通常较小（中位数2，平均数35.44，最大值2370）。
- 相比加纳算法等其他优化手段，使用卡迈克尔函数带来的效率提升较为有限。