RSA¶
简介¶
RSA 是一种非对称加密算法，基于数论中的大数分解问题，计算步骤简单，不考虑量子计算机的情况下，安全性高，是目前最常用的非对称加密算法之一，也是学习非对称加密算法的入门算法。
所谓大数分解问题，就是有两个大素数，很容易计算它们的乘积，虽然这个乘积只可能来源于唯一一组素数相乘（不考虑1和本身那组），但如果只知道乘积，要想分解出这两个素数是非常困难的。 而 rsa 的公钥就是由这两个大素数的乘积和一个指数构成的，私钥则是由这两个大素数和另一个指数构成的，所以 RSA 的安全性通常与大整数分解问题密切相关。
RSA 算法流程¶
-
密钥生成
\[ \begin{aligned} n &= p \cdot q \\ \phi(n) &= (p - 1)(q - 1) \\ e &\in [1, \phi(n)), \quad \gcd(e, \phi(n)) = 1 \\ d &\equiv e^{-1} \pmod{\phi(n)} \end{aligned} \]其中 e 常用 65537
-
加密
\[ c \equiv m^e \mod n \] -
解密
\[ m \equiv c^d \mod n \]
RSA 算法原理¶
这里我不想写太多专业数学定理和证明，最简单的理解就是
e 和 d 是一对"互相抵消"的指数——做 e 次方再做 d 次方，等于什么都没做，数字回到了原点。
而为什么 e 和 d 能互相抵消呢？这来源于欧拉定理：
其中 a 是与 n 互质的整数，\(\phi(n)\) 是欧拉函数，表示小于 n 且与 n 互质的正整数的个数。 根据欧拉定理，我们可以推导出：
因此，e 和 d 互相抵消，使得加密和解密过程能够正确地恢复原文。
补充说明
严格来说，欧拉定理直接适用于 m 与 n 互质的情况；对于 m 与 n 不互质的情况，可以通过分别在模 p、模 q 下讨论并结合中国剩余定理证明，实际 RSA 解密仍然成立。
至于欧拉定理的证明和为什么密钥生成、加解密算法为什么是这样的，就不再展开。
RSA 工程实现¶
单纯的上述 RSA 流程还存在下面三个安全问题： 1. 确定性加密，直接导致暴力枚举 RSA 没有内置随机性，相同的 m 和公钥永远产生相同的 c 。如果明文空间很小，比如加密的是“是/否”、“同意/拒绝”，攻击者可以直接把所有可能的明文用公钥加密一遍，跟截获的密文比对破解。
-
数学同态性导致密文可篡改 RSA 的加密算法具有数学同态性，简单来说就是把两个密文相乘，解密后得到的就是两条明文的乘积，因此攻击者可以在不知道明文的情况下，对密文进行数学变形，使解密结果变成原明文的可控倍数。
-
协议层面可发起选择密文攻击（CCA） 在真实系统中，服务端往往会对解密结果做某种处理并返回响应（哪怕只是报错信息），攻击者利用上述同态性可以构造大量变形密文让服务端解密，从响应差异中逐步恢复明文。
因此，实际工程中 RSA 需要通过填充来防止上述攻击，常见的有 PKCS#1 v1.5 和 OAEP
-
PKCS#1 v1.5
在明文前面添加填充字符串，格式如下：
Text Only - 00（1字节）：固定前导零，保证填充后的整数小于模数 n。
- BT（1字节）：块类型。
- 02 用于加密（公钥操作），表示随机填充。
- 01 用于签名（私钥操作），表示全 FF 填充。
- PS（至少8字节）：
- 加密时（BT=02）：随机非零字节，每次加密都不一样。
- 签名时（BT=01）：全部填入 FF。
- 00（1字节）：分隔符，标记填充结束。
- Data：真正的消息。
这样填充后不仅避免了确定性加密，对于同态攻击，也会因为填充而导致相乘后格式不合法而被拒绝。 但是 PKCS#1 v1.5 存在一些已知漏洞，比如 Bleichenbacher 攻击，攻击者可以通过构造大量变形密文来判断解密结果是否符合 PKCS#1 v1.5 的格式，从而逐步恢复明文。 2. OAEP（Optimal Asymmetric Encryption Padding）
OAEP 全称最优非对称加密填充，为了消除上述所有攻击而设计，它的详细步骤比较复杂，主要思想是通过引入随机性和双重掩码来确保每次加密结果都不同，并且无法通过同态性质构造有效的变形密文。