跳到主要内容

7.5 公开密钥加密算法：RSA

RSA 是现代互联网中使用最广泛的非对称加密算法之一。

RSA 的安全性基于对大数分解的难度。

7.5.1 密钥生成​

RSA 密钥对的生成遵循以下步骤：

  1. 挑选两个非常大的质数 pp 和 qq。
  2. 计算 n=p×qn=p \times q。
  3. 计算 ϕ(n)=(p−1)(q−1)\phi(n)=(p-1)(q-1)。
  4. 挑选公钥指数 ee 满足 1<e<ϕ(n)1 < e < \phi(n) 且 ee 与 ϕ(n)\phi(n) 互质。常用值为 65537。
  5. 计算私钥指数 dd 满足 (d×e)mod  ϕ(n)=1(d \times e) \mod \phi(n)=1。
  6. 最终得出公钥为 (e,n)(e, n)，私钥为 (d,n)(d, n)。

其中：

  • 密钥长度例如 2048 位、4096 位，是指模数 nn 的位数。
  • ϕ(n)\phi(n) 为欧拉函数，指小于等于 nn 的正整数中与 nn 互质的个数。
  • RSA 利用私钥可计算出公钥。

7.5.2 加密和解密​

由于实践中 RSA 加密解密过程十分复杂，此处仅简要描述重点部分。

首先将待加密数据按规定的规则转为整数 mm，满足 0≤m<n0 \leq m < n：

  • 使用公钥加密时，将整数 mm 代入公式 c=memod  nc=m^e \mod n，cc 即为密文。使用私钥加密时只需要将 ee 替换为 dd。
  • 使用私钥解密时，将密文 cc 代入公式 m=cdmod  nm=c^d \mod n，即可还原明文 mm。使用公钥解密时只需要将 dd 替换为 ee。

从上可以看出，RSA 加密和解密计算量非常大，若所有消息均由 RSA 加密将对硬件造成很大的压力，因此常见做法是双方使用 RSA 加密交换一个对称加密的密钥，然后在此次会话的后续报文使用对称加密。HTTPS 使用的就是这种做法。