RSA 算法原理

RSA 算法是一种非对称加密算法，它的名字来源于三位发明者 Rivest、Shamir 和 Adleman 的姓氏首字母。与对称加密不同，非对称加密使用一对密钥：公钥和私钥。公钥可以公开给任何人，用于加密数据；而私钥必须由用户自己保管，用于解密数据。RSA 的核心在于利用了两个数学难题：大整数质因数分解和欧拉函数

密钥生成过程

密钥生成是 RSA 算法的基础，这个过程决定了公钥和私钥的值

1. 选择大质数：随机选择两个非常大的质数 p 和 q。为了确保安全性，这两个质数必须足够大且不能太接近

2. 计算模数：计算它们的乘积 n=p×q。这个 n 就是 RSA 的模数，它既是公钥的一部分，也是私钥的一部分

3. 计算欧拉函数：计算欧拉函数 ϕ(n)=(p−1)(q−1)。欧拉函数 ϕ(n) 表示小于或等于 n 且与 n 互质的正整数的个数

4. 选择公钥指数：选择一个整数 e，它必须满足以下条件：

   • 1<e<ϕ(n)

   • e 与 ϕ(n) 互质（即最大公约数为 1）

     通常，为了计算效率，会选择一些常见的质数，比如 65537。这个 e 就是公钥的指数

5. 计算私钥指数：计算一个整数 d，它必须满足以下条件：

   • d × e ≡ 1 (mod ϕ(n))

     这个等式意味着 d × e 除以 ϕ(n) 的余数为 1。我们可以使用扩展欧几里得算法来高效地找到这个 d。这个 d 就是私钥的指数

至此，密钥生成完成。公钥为 (n,e)，可以公开；私钥为 (n,d)，必须严格保密

加密和解密过程

有了公钥和私钥，就可以进行数据的加密和解密了

加密

假设发送方想向你发送一条消息 M

1. 发送方获取你的公钥 (n,e)

2. 将明文消息 M 转换为一个整数（通常通过 ASCII 或其他编码方式）

3. 使用公钥进行加密，计算密文 C：

   C = Me (mod n)

解密

当接收方收到密文 C 后，就可以使用自己的私钥进行解密

1. 接收方使用自己的私钥 (n,d)

2. 使用私钥进行解密，计算出原始明文 M：

   M = C^d (mod n)

这里看起来很简单，但其背后的数学原理是：

(M^e)^d ≡ M^ed ≡ M (mod n)

这正是欧拉定理在起作用，它保证了加密和解密的可逆性