RSA 加解密原理与大整数分解
哪些公司问过
答案要点
- 密钥生成:n=pq,φ(n)=(p−1)(q−1),选 e 与 φ(n) 互素,d=e⁻¹ mod φ(n)
- 加密 c = m^e mod n,解密 m = c^d mod n,正确性来自欧拉定理
- 分解出 p、q 即可求 φ(n) 和 d,分解 n 足以攻破 RSA
- 安全性基于大整数分解困难;RSA 问题与分解是否等价尚未被证明
- 实践:使用 OAEP、PSS 填充,密钥至少 2048 位,解密可用中国剩余定理加速
易错点
- 把加密和解密用的密钥说反
- 说 RSA 安全性已被证明等价于大整数分解
- 忽略填充,认为教科书式 RSA 可直接使用
面试官常见追问
- RSA 为什么需要填充?
- CRT 怎么加速 RSA 解密?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。