RSA 算法原理
约 686 字大约 2 分钟
2025-11-02
RSA 算法原理
RSA 算法是一种非对称加密算法，它的名字来源于三位发明者 Rivest、Shamir 和 Adleman 的姓氏首字母。与对称加密不同，非对称加密使用一对密钥：公钥和私钥。公钥可以公开给任何人，用于加密数据；而私钥必须由用户自己保管，用于解密数据。RSA 的核心在于利用了两个数学难题：大整数质因数分解和欧拉函数
密钥生成过程
密钥生成是 RSA 算法的基础，这个过程决定了公钥和私钥的值
选择大质数：随机选择两个非常大的质数 p 和 q。为了确保安全性，这两个质数必须足够大且不能太接近
计算模数：计算它们的乘积
n=p×q。这个 n 就是 RSA 的模数，它既是公钥的一部分，也是私钥的一部分计算欧拉函数：计算欧拉函数
ϕ(n)=(p−1)(q−1)。欧拉函数 ϕ(n) 表示小于或等于 n 且与 n 互质的正整数的个数选择公钥指数：选择一个整数 e，它必须满足以下条件：
1<e<ϕ(n)e 与 ϕ(n) 互质（即最大公约数为 1）
通常，为了计算效率，会选择一些常见的质数，比如 65537。这个 e 就是公钥的指数
计算私钥指数：计算一个整数 d，它必须满足以下条件：
d × e ≡ 1 (mod ϕ(n))这个等式意味着
d × e除以 ϕ(n) 的余数为 1。我们可以使用扩展欧几里得算法来高效地找到这个 d。这个 d 就是私钥的指数
至此，密钥生成完成。公钥为 (n,e)，可以公开；私钥为 (n,d)，必须严格保密
加密和解密过程
有了公钥和私钥，就可以进行数据的加密和解密了
加密
假设发送方想向你发送一条消息 M
发送方获取你的公钥 (n,e)
将明文消息 M 转换为一个整数（通常通过 ASCII 或其他编码方式）
使用公钥进行加密，计算密文 C：
C = Me (mod n)
解密
当接收方收到密文 C 后，就可以使用自己的私钥进行解密
接收方使用自己的私钥 (n,d)
使用私钥进行解密，计算出原始明文 M：
M = C^d (mod n)
这里看起来很简单，但其背后的数学原理是：
(M^e)^d ≡ M^ed ≡ M (mod n)这正是欧拉定理在起作用，它保证了加密和解密的可逆性