非对称加密与RSA算法
非对称加密与RSA算法
概述
非对称加密（公钥密码学）是现代密码学中最具革命性的发明之一，由 Diffie 和 Hellman 在 1976 年首次提出概念，随后 Rivest、Shamir 和 Adleman 于 1977 年提出了著名的 RSA 算法。与对称加密不同，非对称加密使用一对数学上相关的密钥——公钥可以公开分发，私钥必须严格保密，从根本上解决了密钥分发的难题。
RSA 算法至今仍是应用最广泛的非对称加密算法，它的安全性基于大整数分解问题的计算困难性。除了加密功能外，RSA 还广泛用于数字签名和密钥交换。然而，随着量子计算的发展，RSA 面临着潜在的威胁，这也推动了后量子密码学的研究。
在 CTF 竞赛中，RSA 是 Crypto 类题目中最常出现的算法之一，理解其数学原理和常见攻击方式是解决此类题目的关键。
核心概念
公钥密码体制原理
公钥密码体制的核心思想是利用数学上的单向陷门函数——正向计算容易，反向计算在没有陷门信息的情况下极其困难。在 RSA 中，将两个大素数相乘很容易，但将乘积分解回原来的两个素数却非常困难。公钥用于加密（或验签），私钥用于解密（或签名），二者在数学上相关但无法从公钥推导出私钥。
公钥密码体制的三个核心应用是：加密（用接收方的公钥加密，只有接收方的私钥能解密）、数字签名（用发送方的私钥签名，任何人可用公钥验证）和密钥交换（双方各自使用对方的公钥协商出共享密钥）。
RSA 密钥生成
RSA 密钥生成的过程如下：首先选择两个大素数 p 和 q，计算 n = p * q 作为模数；然后计算欧拉函数 φ(n) = (p-1)(q-1)；接着选择一个与 φ(n) 互质的整数 e 作为公钥指数（常用 e = 65537）；最后计算 e 模 φ(n) 的乘法逆元 d 作为私钥指数，即满足 e * d ≡ 1 (mod φ(n))。公钥为 (n, e)，私钥为 (n, d)。
加密过程为 C = M^e mod n，解密过程为 M = C^d mod n，其中 M 为明文，C 为密文。RSA 的安全性依赖于从 n 和 e 计算出 d 的困难性，这等价于对 n 进行大整数分解。
常见攻击方式
CTF 中 RSA 题目常见的攻击场景包括：小公钥指数攻击——当 e 很小（如 e=3）且明文也较小时，M^e 可能小于 n，直接对密文开 e 次方根即可得到明文；共模攻击——对同一明文使用相同模数 n 但不同公钥指数加密，可通过扩展欧几里得算法恢复明文；Wiener 攻击——当私钥 d 较小时（d < n^(1/4)/3），可通过连分数展开高效恢复 d。
因数分解攻击——当 n 的某个因子较小时（如 p 或 q 少于 512 位），可以使用工具（如 yafu、msieve、factordb.com）进行分解；Pollard p-1 攻击——当 p-1 或 q-1 只有小素因子时有效；Fermat 分解——当 p 和 q 相近时有效。此外还有 Coppersmith 攻击、Hastad 广播攻击等高级方法。
RSA 的填充方案
原始的 RSA（教科书 RSA）存在多种安全问题，因此实际应用中必须使用填充方案。PKCS#1 v1.5 是早期广泛使用的填充标准，但存在 Bleichenbacher 攻击的风险。OAEP（Optimal Asymmetric Encryption Padding）是更安全的填充方案，通过引入随机性来抵抗选择密文攻击。在签名方面，PSS（Probabilistic Signature Scheme）是推荐的填充方式。
实战要点
- 检查公钥参数：在 CTF 中拿到 RSA 题目后，首先提取 n 和 e 的值，检查 n 的大小、e 的大小以及是否使用了相同的 n。
- 使用工具辅助：RsaCtfTool、yafu、sage 等工具可以自动化许多常见攻击，熟练使用这些工具能大幅提高解题效率。
- 关注密钥长度：小于 1024 位的 RSA 密钥被认为不再安全，2048 位是当前的最低推荐长度，3072 位提供长期安全性。
- 理解数学基础：掌握模运算、欧拉定理、扩展欧几里得算法等数学知识，是深入理解 RSA 和解决复杂题目的前提。
- 注意实现漏洞：侧信道攻击（如时序攻击、能量分析攻击）可以针对 RSA 的具体实现进行攻击，而非算法本身。
总结
RSA 算法是现代公钥密码学的基石，其优雅的数学原理将大整数分解的困难性转化为实际的安全保障。理解 RSA 的密钥生成、加解密过程和各种攻击手段，对于密码学学习和 CTF 解题都具有重要意义。
随着计算能力的提升和量子计算的发展，RSA 的密钥长度需要不断增长才能维持安全性。未来，基于格的密码学等后量子密码算法可能会逐步取代 RSA，但在相当长的过渡期内，RSA 仍将是密码学领域的核心研究对象。