1. 从一道CTF题看RSA的“非常规”攻击最近在复盘一些经典的CTF密码学题目特别是RSA相关的发现很多题目的考点早已超出了教科书上“大数分解”的范畴。今天想和大家深入聊聊一道来自RoarCTF 2019的RSA题目。这道题本身可能没有公开完整的writeup但结合“共模RSA原理”这个热词以及常见的CTF RSA出题套路我们可以还原并剖析一类典型的、考察对RSA算法深刻理解的“非分解”攻击场景。很多刚接触密码学的朋友一提到RSA破解就只想到分解N但实际上在参数设置不当或存在信息泄露的情况下有太多方法可以在不分解N的前提下恢复明文。这道题就是一个绝佳的引子让我们看看出题人可能设置了哪些“陷阱”。RSA的安全性基于大整数分解的困难性这没错。但在CTF竞赛中直接给你一个1024位或2048位的N让你分解在比赛时限内几乎是不可能的除非有极其特殊的弱质数。因此高水平的赛题往往会从其他角度切入比如共模攻击、低加密指数攻击、低解密指数攻击、选择密文攻击或是利用加密过程的确定性如对同一明文多次加密等。这些攻击之所以能成立根源都在于参数的使用违反了RSA在实践中的安全准则。通过解这道题我们不仅能掌握一种攻击方法更能反向理解如何安全地使用RSA。2. 场景构建共模攻击的典型条件与原理我们先来构建RoarCTF这道题最可能考察的模型——共模攻击。这也是网络热词中明确提到的“共模rsa原理”。想象这样一个场景一个不够安全的系统需要向两个不同的实体发送同一份机密消息M。系统管理者决定使用RSA加密但他犯了一个致命的错误他生成了两对不同的RSA密钥但这两对密钥使用了同一个模数N。也就是说公钥分别是(N, e1)和(N, e2)对应的私钥是d1和d2。然后他用这两把公钥分别加密了同一个消息M得到了两个密文C1 M^e1 mod NC2 M^e2 mod N现在攻击者通过某种方式比如在CTF题中直接给出获取了N, e1, e2, C1, C2。他的目标是求出M。请注意他并不知道私钥d1或d2也没有分解N。为什么这样是危险的这涉及到数论中的一个基本定理——贝祖定理Bézout‘s Identity。该定理指出对于两个整数e1和e2如果它们的最大公约数gcd(e1, e2) 1即它们互质那么一定存在两个整数s和t使得e1 * s e2 * t 1这里的s和t可以通过扩展欧几里得算法高效地计算出来即使e1和e2很大。现在让我们把目光转回密文。我们有C1^s ≡ (M^e1)^s ≡ M^(e1*s) (mod N)C2^t ≡ (M^e2)^t ≡ M^(e2*t) (mod N)将这两个式子相乘C1^s * C2^t ≡ M^(e1*s) * M^(e2*t) ≡ M^(e1*s e2*t) (mod N)还记得贝祖等式吗e1*s e2*t 1。因此上式右边就变成了M^(e1*s e2*t) ≡ M^1 ≡ M (mod N)于是我们得到了一个惊人的结果M ≡ C1^s * C2^t (mod N)攻击者只需要计算(C1^s * C2^t) mod N就能直接得到明文M全程不需要私钥也不需要分解N。这就是共模攻击的核心原理。注意这里有一个关键前提即s和t中很可能有一个是负数。在模运算中一个数的负指数次幂需要计算其模逆元。例如若s为负数则C1^s mod N的实际计算应为(C1^(-1))^(-s) mod N即先计算C1关于模N的逆元再求其(-s)次幂。在实际的脚本编写中扩展欧几里得算法求解出的s和t很可能一正一负需要正确处理。3. 实战推演还原RoarCTF 2019 RSA解题过程基于共模攻击的原理我们可以合理还原这道CTF题的解题步骤。通常题目会提供一个包含以下数据的文件比如output.txt或脚本中的变量N 123456789... (一个很大的整数) e1 65537 e2 10001 C1 密文1的整数形式 C2 密文2的整数形式有时N、e、C也会以十六进制字符串的形式给出需要先转换为整数。步骤1数据读取与预处理首先我们需要从题目附件中提取这些关键参数。如果数据是十进制的直接用Python的int类型读取即可。如果是十六进制则使用int(hex_string, 16)进行转换。确保所有变量都正确转换为Python的大整数。步骤2验证攻击条件计算gcd(e1, e2)确保其结果为1即e1和e2互质。这是共模攻击能够成立的必要条件。在CTF题中这通常是成立的。如果不互质则需要考虑其他攻击方式比如计算gcd(e1, e2) g然后可能对M^g进行开方等但情况会复杂很多。步骤3应用扩展欧几里得算法调用扩展欧几里得算法求解满足e1*s e2*t 1的整数s和t。Python的gmpy2库中的gcdext()函数可以完美完成这个任务。如果没有安装gmpy2也可以使用纯Python实现扩展欧几里得算法但对于大整数gmpy2效率更高。import gmpy2 # 假设 e1, e2 已经定义 gcd, s, t gmpy2.gcdext(e1, e2) # 验证 gcd(e1, e2) 1 assert gcd 1运行后我们会得到s和t。它们通常一正一负。步骤4处理负指数计算明文根据s和t的正负情况分别计算C1^s mod N和C2^t mod N。如果指数为负需要先计算模逆元。if s 0: # 计算 C1 关于模 N 的逆元 C1_inv gmpy2.invert(C1, N) part1 gmpy2.powmod(C1_inv, -s, N) else: part1 gmpy2.powmod(C1, s, N) if t 0: # 计算 C2 关于模 N 的逆元 C2_inv gmpy2.invert(C2, N) part2 gmpy2.powmod(C2_inv, -t, N) else: part2 gmpy2.powmod(C2, t, N)最后计算明文M (part1 * part2) % N。步骤5明解码得到的M是一个大整数需要将其转换为可读的字符串。通常CTF的flag是文本所以我们需要将M的字节表示解码。常见的编码是ASCII或UTF-8。但有时M可能包含非文本数据或者flag被进一步编码如Base64、Hex。因此转换后需要肉眼判断或尝试常见解码方式。# 将整数M转换为字节串 plaintext_bytes int(M).to_bytes((M.bit_length() 7) // 8, big) # 尝试解码为UTF-8 try: flag plaintext_bytes.decode(utf-8) print(flag) except UnicodeDecodeError: # 如果不是UTF-8直接输出十六进制或尝试其他解码 print(plaintext_bytes.hex()) # 或者尝试是否有‘flag{’、‘CTF{’等特征子串的字节形式一个完整的解题脚本示例import gmpy2 from Crypto.Util.number import long_to_bytes # 题目数据此处为示例实际需替换 N 0x726639... # 替换为实际的N e1 65537 e2 10001 C1 0x3aeb... # 替换为实际的C1 C2 0x8c1d... # 替换为实际的C2 # 步骤2 3验证并求解s, t gcd, s, t gmpy2.gcdext(e1, e2) print(fgcd(e1, e2) {gcd}, s {s}, t {t}) assert gcd 1 # 步骤4计算明文 def compute_part(c, exp, n): if exp 0: c_inv gmpy2.invert(c, n) return gmpy2.powmod(c_inv, -exp, n) else: return gmpy2.powmod(c, exp, n) part1 compute_part(C1, s, N) part2 compute_part(C2, t, N) M (part1 * part2) % N # 步骤5解码 print(fRecovered M (int): {M}) flag_bytes long_to_bytes(M) print(fRecovered bytes: {flag_bytes}) # 尝试打印 try: print(flag_bytes.decode()) except: print(Cannot decode as UTF-8, raw bytes above.)通过以上步骤我们就能在不分解N、不知道私钥的情况下成功恢复出明文flag。这就是共模攻击在CTF中的典型应用。4. 深度拓展从共模攻击看RSA的安全实践解完一道题我们更应该思考其背后的安全启示。共模攻击之所以能成功根本原因在于密钥管理的严重失误。1. 模数N必须唯一RSA的模数N是由两个大素数p和q相乘得到的。私钥d的计算依赖于p和q或者其欧拉函数φ(N)。一旦同一个N被用于多对密钥那么任何一对密钥的泄露或者像共模攻击这样无需私钥的攻击都会危及所有用此N加密的消息。在实践包括PKI公钥基础设施中每一个RSA密钥对都必须使用独立生成的、随机的p和q确保模数N全局唯一。绝对禁止复用模数。2. 加密的随机化——OAEP填充教科书式RSA即直接计算M^e mod N是确定性的。对同一个明文加密永远得到同一个密文。这不仅会导致共模攻击还会面临其他选择明文攻击。因此在实际应用如TLS、PGP中从不直接使用教科书RSA加密消息。而是采用RSA-OAEP最优非对称加密填充等填充方案。OAEP在加密前会将明文与随机数混合填充使得每次加密同一明文产生的密文都不同从而有效抵御共模攻击等多种攻击。CTF题中常给出教科书式RSA正是为了凸显这些攻击。3. 指数e的选择题目中e165537e210001都是常见的公钥指数。655370x10001因其在安全性和计算效率上的平衡成为最普遍的选择。它二进制表示中只有两个1使得模幂运算很快且作为一个素数与φ(N)互质的概率极高。选择e的原则是与φ(N)互质、不宜过小防低加密指数攻击、不宜过大防低解密指数攻击。共模攻击并不要求e小只要求两个e互质。4. CTF中的其他“非分解”攻击思路除了共模攻击RoarCTF这类题目还可能结合其他考点已知高位攻击如果私钥d的一部分比特位泄露可能利用Coppersmith方法恢复完整的d。侧信道攻击题目可能给出加密过程中的某些错误信息如解密错误返回从而实施选择密文攻击。因数碰撞如果题目给出了多组N可能其中两个N共享了一个质因子可以通过计算gcd(N1, N2)来快速分解这两个N。这属于密钥生成随机性不足的问题。理解这些攻击能帮助我们在实际开发中规避陷阱。例如确保使用密码学库如Python的cryptography、Go的crypto/rsa提供的标准接口进行加密解密而不是自己实现教科书RSA确保密钥对的生成是真正随机的。5. 工具与技巧CTF密码学解题环境搭建工欲善其事必先利其器。高效地求解RSA类题目离不开顺手的工具和环境。这里分享一些我个人常用的配置和技巧。1. Python环境与核心库Python 3.x这是基础。建议使用较新的版本如3.8。gmpy2处理大整数运算的利器速度远超Python原生整数运算提供了powmod,invert,gcdext,gcd等关键函数。安装它通常是第一步在Linux/macOS上可能需要先安装GMP库开发文件。# Ubuntu/Debian sudo apt-get install libmpc-dev pip install gmpy2PyCryptodome或Crypto这个库提供了Crypto.Util.number模块其中的long_to_bytes和bytes_to_long函数在整数和字节串转换时非常方便。此外它还包含其他密码学原语可能在其他题目中用到。pip install pycryptodome2. SageMath更强大的数学武器对于更复杂的攻击如Coppersmith方法、基于格的攻击SageMath是几乎不可或缺的工具。它是一个集成了众多数学软件如NumPy、SymPy的Python发行版内置了强大的数论和代数运算能力。你可以编写.sage脚本也可以在Jupyter Notebook中使用。对于本地安装复杂的问题可以使用CoCalc或SageCell在线服务。3. 解题通用脚本结构养成一个好的脚本编写习惯能事半功倍。我通常这样组织一个RSA解题脚本#!/usr/bin/env python3 import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long def read_data(): 从文件或剪贴板读取题目数据 # 方式1从文件读取 # with open(output.txt, r) as f: # data f.read() # 解析N, e, c... # 方式2硬编码调试用 N 0x1234... e 65537 c 0xabcd... return N, e, c def common_modulus_attack(N, e1, c1, e2, c2): 共模攻击实现 gcd, s, t gmpy2.gcdext(e1, e2) assert gcd 1 # ... 计算过程 ... return M def main(): # 1. 读取数据 # 2. 根据数据特征判断攻击方式例如检查是否有两个N相同e是否很小 # 3. 调用对应的攻击函数 # 4. 输出并尝试解码flag pass if __name__ __main__: main()4. 在线工具与资源factordb.com这是一个神奇的网站。当你拿到一个N可以首先尝试在这里查询它是否已经被分解过。很多CTF题目的N是故意选用可分解的弱质数或者来自已知的RSA挑战数。如果能在factordb找到分解结果题目就直接解决了。RsaCtfTool一个功能强大的RSA攻击工具集用Python编写集成了数十种攻击方法。当你没有思路时可以尝试用它自动攻击。但作为学习者我更推荐先理解原理再使用工具验证。git clone https://github.com/RsaCtfTool/RsaCtfTool.git cd RsaCtfTool python3 RsaCtfTool.py --publickey key.pub --uncipherfile cipher.txtWolfram Alpha对于中小整数的分解或模逆计算直接在Wolfram Alpha网站输入算式有时更快。5. 调试与验证技巧小参数测试在编写攻击脚本时先用自己生成的、参数很小如p17, q19的RSA密钥进行测试。确保脚本能正确解密再应用到题目的大参数上。打印中间变量在计算s, t以及part1,part2时打印它们的值和正负确保计算逻辑符合预期。检查编码解密出的整数M在转换为字节后如果开头不是可读字符可以尝试反转字节序plaintext_bytes[::-1]检查是否包含flag{或CTF{的字节模式。尝试Base64解码、Hex解码等。6. 举一反三当共模攻击条件不满足时我们讨论了最理想的共模攻击场景同一N两个互质的e加密同一消息M。但在实际CTF或现实场景中条件可能不会这么完美。我们需要学会变通。情况一gcd(e1, e2) ! 1如果两个公钥指数不互质比如gcd(e1, e2) g 1。那么贝祖等式变为e1*s e2*t g。此时我们有C1^s * C2^t ≡ M^g (mod N)我们得到了M^g mod N而不是M。这时我们需要对M^g开g次方根来求M。当g很小比如2或3且M^g没有超过模数N时即M^g N在整数域内直接开方我们可以直接计算。如果是在模N下求解x^g ≡ C (mod N)是一个更难的问题通常需要g非常小或者有其他特殊条件。情况二加密的不是完全相同消息但有线性关系假设用同一对密钥(N, e)加密了两个有线性关系的消息例如M1和M2 a * M1 ba, b已知。那么我们有C1 ≡ M1^e (mod N)C2 ≡ (a*M1 b)^e (mod N)这构成了一个关于M1的多项式方程。当e很小时比如3我们可以利用Coppersmith方法在整数域或模数下求解小根。这就是所谓的相关消息攻击。情况三多次加密与广播攻击如果一个消息M用相同的小公钥e如e3加密但发送给多个不同的接收者即不同的N1, N2, N3...。这被称为广播攻击或Håstad广播攻击。利用中国剩余定理CRT我们可以从多个密文中恢复出M^e在更大整数域上的值。由于e很小且M^e很可能小于所有N的乘积我们可以直接在整数域对M^e开e次方得到M。情况四部分密钥泄露攻击这是更高级的考点。如果题目不仅给出了公钥(N, e)还泄露了私钥d的一部分比特比如已知d的高位或低位或者泄露了素数p/q的部分比特。我们可以利用Coppersmith定理来构造方程恢复出完整的私钥或素数。这类题目通常需要用到SageMath及其small_roots方法。面对一道RSA题我的常规分析路径是观察参数看有几个N几个e几个c。它们之间有什么关系相同N相同e尝试简单攻击如果N不大 512bit先上factordb或本地用yafu尝试分解。如果e很小如3且只有一个c考虑小公钥指数攻击直接开方。如果同一个N对应多个e和c优先考虑共模攻击。如果同一个e对应多个N和c考虑广播攻击。深入分析如果以上都不行再考虑是否存在泄露d, p, q的部分信息、选择密文攻击、或需要用到格攻击LLL算法等更复杂的场景。7. 从CTF到实战安全使用RSA的黄金法则最后让我们跳出CTF看看在真实的软件开发和系统设计中应该如何正确使用RSA避免成为“靶子”。法则一永远不要自己实现密码学原语这是最重要的一条。除非你是专业的密码学家并且正在进行学术研究或设计新的算法否则绝对不要尝试自己编写RSA加密、解密、密钥生成的代码。使用经过广泛审计和长期实战检验的成熟密码学库如Python:cryptography(推荐),PyCryptodomeJava:javax.crypto, Bouncy CastleGo:crypto/rsa,crypto/randC/C: OpenSSL, libsodium 这些库已经正确处理了填充、随机化、密钥生成等所有细节。法则二使用正确的填充方案对于加密使用OAEP(RSAES-OAEP) 填充。在Python的cryptography库中默认就是OAEP。from cryptography.hazmat.primitives.asymmetric import rsa, padding from cryptography.hazmat.primitives import hashes # 加密 ciphertext public_key.encrypt( message, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) )对于签名使用PSS(RSASSA-PSS) 填充。避免使用旧的、不安全的PKCS#1 v1.5填充除非需要与老旧系统兼容。法则三确保密钥生成的随机性密钥对必须在密码学安全的随机数生成器CSPRNG上生成。绝对不要使用固定的种子或伪随机数。在代码中这意味着使用库提供的标准密钥生成函数而不是自己指定p和q。法则四密钥长度要足够随着计算能力的提升RSA密钥的最小安全长度也在增加。目前2048位是公认的最低要求对于需要长期保密的数据建议使用3072位或4096位。1024位的RSA在当今已不再安全。法则五理解“加密”与“签名”的区别RSA既可以用于加密用公钥加密私钥解密也可以用于签名用私钥“签名”公钥“验签”。这是两个不同的操作不能混用。加密是为了保密签名是为了认证和完整性。使用的填充方案和API也不同。法则六关注算法演进与迁移RSA并非永恒。量子计算的威胁虽然遥远但确实存在。学术界和工业界正在积极推动后量子密码学PQC的标准化。作为开发者应保持关注并在未来必要时规划向抗量子算法如基于格的CRYSTALS-Kyber的迁移。目前保持RSA密钥足够长并配合前向安全协议如TLS 1.3仍是安全实践。回过头看RoarCTF这道题它像是一个精巧的“反面教材”用最直白的方式展示了违反安全法则复用模数的后果。通过解构它我们不仅学会了一种攻击技巧更重要的是在心中刻下了这些安全准则。在CTF中我们寻找漏洞在实战中我们修补漏洞。这种思维的转换正是安全竞赛带给从业者最宝贵的财富。下次当你设计或评审一个用到RSA的系统时不妨问问自己我们的模数生成是真正随机的吗我们用的是OAEP填充吗我们的密钥长度够吗多问一句也许就能避免一个潜在的重大风险。