从CTF实战剖析RSA攻击：共模、小指数与Coppersmith方法

1. 从一道CTF题看RSA攻击的实战演变那天在BUUCTF平台上刷每日打卡碰上了2021年5月18日那道RSA题目。题目本身没有给太多花哨的描述就是一组看似标准的RSA参数但解题过程却像一次对RSA攻击方法的经典巡礼。很多刚接触密码学挑战的朋友一看到RSA就觉得是数学难题下意识想避开。其实这类题目往往是理解现代公钥密码体系脆弱点和攻击者思维的最佳入口。它考察的不是让你从头发明一种攻击而是看你能否像攻击者一样识别出参数设置中那些“不合常理”的细节并运用已知的“武器库”快速破解。这道题就巧妙地串联了RSA中几个常见的攻击场景共模攻击、小公钥指数攻击以及Coppersmith相关攻击的初步思想。我们今天不把它当作一道单纯的CTF题解而是作为一个引子深入聊聊在这些攻击背后参数选择到底是如何深刻影响系统安全的以及我们在实际应用RSA时应该避开哪些“坑”。RSA算法自1977年诞生以来已成为互联网安全的基石之一从HTTPS的握手到SSH的登录无处不在。它的安全性基于大整数分解的困难性但这有一个至关重要的前提所有参数都必须按照密码学意义上的“强”方式来选择和生成。在实际的CTF竞赛或者安全评估中出题人往往会故意违背一两条安全准则从而制造漏洞。解题的过程就是逆向找出这些违背准则之处并实施相应攻击的过程。理解这些攻击不仅能帮你解题更能让你在真正部署或审查一个使用RSA的系统时一眼看出潜在的风险点。接下来我们就以解题的视角层层剥开这道题可能涉及的攻击面。2. 题目环境构建与初步观察面对任何一道RSA题目第一步永远不是埋头计算而是像法医勘察现场一样进行系统的信息收集和初步观察。题目通常会给你几个关键元素模数n、公钥指数e、密文c。有时会有多个密文或多组密钥。对于“每日打卡”这类题目目标很明确从密文c和公钥(n, e)中还原出明文m。首先我们需要搭建一个本地的分析环境。Python的gmpy2库是处理大数运算的利器pycryptodome或Crypto库则提供了完整的RSA原语支持。我通常的起手式是这样的from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 # 假设题目给出的参数这里用示例值实际需替换 n 123456789... # 非常大的整数 e 65537 # 常见的公钥指数 c 987654321... # 密文整数 # 查看n的位数比特长度 print(“模数n的比特长度:”, n.bit_length())比特长度是第一个重要线索。如今安全的RSA要求n的长度至少为2048比特对应617位十进制数。如果题目给出的n只有256或512比特那很可能暗示它不够大也许能被直接分解。我们可以尝试用一些在线分解数据库如factordb或者本地工具如yafu进行分解尝试。如果n可以被分解为两个素数p和q那么整个RSA体系就被攻破了因为私钥d可以通过计算e模φ(n)(p-1)(q-1)的模逆元得到。然而在2021年的CTF题中直接给出一个可分解的小n的情况已经比较少了出题人更喜欢在参数关系上做文章。所以当直接分解行不通时我们就要转向第二步分析参数之间的关系。这里有几个关键检查点检查公钥指数e的值e通常取655370x10001因为它是一个素数二进制表示中只有两个1计算模幂运算速度快且安全性好。如果e非常小比如3、17等就要立即警惕“小公钥指数攻击”。如果e很大甚至和φ(n)的量级接近则可能与私钥d过小有关需考虑维纳攻击等。检查是否有多个密文对应同一个n如果发现两组或更多组密文它们是用相同的模数n但不同的公钥指数e1, e2,...加密的那么“共模攻击”的警报就应该拉响。检查密文c和n的关系有时由于填充不当或明文过小可能导致m^e n。在这种情况下直接对密文c开e次方根就能得到明文m。这被称为“低加密指数广播攻击”的一种特例或者更直接地就是加密过程未产生模约简。对于BUUCTF 2021-5-18的题目根据相关热词推测它很可能涉及了共模攻击和小公钥指数攻击的组合或选择。我们的初步观察就要围绕这些点展开。假设题目给出了两组密文c1, c2以及对应的公钥(n, e1)和(n, e2)并且e1和e2是互素的通常都是。这就是共模攻击的经典场景。3. 共模攻击的原理与详细推导共模攻击是RSA系统误用中最经典的案例之一。它的核心思想是绝对不要用同一个模数n为多个用户生成密钥对。但在实际中有时为了省事或者在不了解风险的情况下可能会用一个固定的n只给不同用户分配不同的e和d。这道题很可能就是模拟了这种危险场景。攻击之所以成立依赖一个简单的数学事实如果两个互素的整数e1和e2满足gcd(e1, e2) 1那么根据扩展欧几里得算法贝祖定理一定存在两个整数s1和s2使得e1 * s1 e2 * s2 1注意这里的s1和s2很可能一正一负。现在假设同一个明文m用相同的模数n但不同的公钥指数加密得到两个密文c1 ≡ m^e1 (mod n)c2 ≡ m^e2 (mod n)攻击者手上有c1,c2,e1,e2,n。他的目标是恢复m。将上面找到的贝祖等式进行巧妙的变换 因为e1*s1 e2*s2 1那么对明文m进行如下运算m^(e1*s1 e2*s2) m^1 m而根据模运算的性质m^(e1*s1) ≡ (m^e1)^s1 ≡ c1^s1 (mod n)m^(e2*s2) ≡ (m^e2)^s2 ≡ c2^s2 (mod n)因此m ≡ m^(e1*s1 e2*s2) ≡ c1^s1 * c2^s2 (mod n)这里有一个关键点s1或s2可能是负数。如果s1是负数那么c1^s1在模n下的计算需要先求c1的模逆元。因为对于负指数c1^s1 ≡ (c1^{-1})^{-s1} (mod n)前提是c1与n互质在RSA中由于c1是密文且n是两个大素数的乘积c1与n互质的概率极高几乎总是成立。所以攻击步骤非常清晰验证gcd(e1, e2) 1。如果不互素攻击不成立。使用扩展欧几里得算法求出满足e1*s1 e2*s2 1的整数s1和s2。如果s1为负则计算c1_inv gmpy2.invert(c1, n)然后计算part1 pow(c1_inv, -s1, n)。如果s1为正则直接计算part1 pow(c1, s1, n)。对s2和c2进行类似处理。计算m (part1 * part2) % n。将得到的整数m转换为字节字符串即可得到明文。注意在实际计算中由于s1和s2可能非常大直接计算幂运算会导致中间结果巨大。务必使用Python的pow(c, s, n)函数进行模幂运算它采用了快速幂算法并且中间结果始终对n取模效率极高且不会内存溢出。这里有一个我踩过的坑早期我用的是pow(c1, s1) % n当指数很大时pow(c1, s1)会先计算一个天文数字般的整数导致内存爆掉。一定要用三参数的pow(a, b, c)。共模攻击的破坏力在于它完全不需要分解模数n也不需要获取私钥d。它仅仅利用了“同一明文用相同模数加密多次”这一错误实践。这给我们的实际安全启示是在任何RSA应用中每个用户、每个会话都应该使用独立生成的密钥对确保模数n的唯一性。4. 小公钥指数攻击与Coppersmith方法初探在初步观察中如果公钥指数e非常小比如3、5、17而明文m也不是很大那么可能会触发另一种攻击。RSA加密过程是c ≡ m^e (mod n)。如果m^e的值小于模数n那么取模运算实际上没有发生作用即c m^e在整数域中而非模n域。这样一来攻击者只需要对密文c开e次方根就能直接得到明文mm c^(1/e)。这种攻击成立的条件非常苛刻m^e n。因为n通常非常大比如2048比特m作为明文比如一个字符串或一个对称密钥其长度有限所以当e很小时这个不等式有可能成立。例如如果e3m是一个ASCII字符串那么m的比特长度大约是其字节数的8倍。要使m^3 n大致要求m的长度小于n的比特长度的三分之一。对于1024比特的nm需要小于约341比特即大约42个字节。这在实际中是有可能发生的尤其是当m是一个短的随机数或密钥时。但是现代RSA实践都会使用填充方案如OAEP将明文m扩展成与模数长度相近的、结构化的“经填充的消息”。这使得m^e几乎总是大于n从而封堵了这种最简单的攻击。在CTF中出题人有时会故意不使用填充或者使用自定义的、不安全的编码方式来构造满足m^e n的场景。如果m^e只是略大于n导致c m^e - k*n中的k是一个很小的整数比如123...那么问题就演变成了一个“小根”问题寻找一个整数m使得m^e - c是n的倍数。这类问题正是Coppersmith方法大显身手的地方。Coppersmith方法是密码学中一个非常强大的工具它用于在模数n下寻找满足特定多项式方程的小根。对于RSA如果我们知道明文m的某些部分比如高位或低位比特或者知道m满足某个上界比如m n^(1/e)那么Coppersmith方法可以在多项式时间内恢复出完整的m。它基于LLL格基约化算法能够求解模方程的小整数解。在CTF中Coppersmith相关的题目通常不会要求选手自己实现复杂的LLL算法而是使用现成的工具库最著名的就是SageMath。Sage内置了强大的small_roots()方法。一个典型的攻击场景是“已知明文高位攻击”假设明文m由两部分组成m known_part x其中known_part是已知的高位部分x是未知的低位部分且x相对较小。那么加密方程可以写为c ≡ (known_part x)^e (mod n)这是一个关于未知数x的多项式方程。我们可以构造多项式f(x) (known_part x)^e - c它在模n下等于0。如果x足够小小于n的1/e次方量级那么x就是这个多项式在整数域上的一个小根。使用Coppersmith方法我们就可以解出x从而恢复完整的m。对于BUUCTF这道题如果它涉及Coppersmith可能会是这种形式给出一个e3或e5密文c并提示明文m的格式是flag{开头后面接一串未知字符。那么known_part就是bytes_to_long(b‘flag{’)左移若干比特后的值。我们可以在Sage中这样求解# SageMath 代码示例 n ... # 模数 e 3 # 小公钥指数 c ... # 密文 known_prefix b‘flag{’ known_part bytes_to_long(known_prefix) # 假设未知部分x的长度不超过k比特 k 64 # 构造多项式环 P.x PolynomialRing(Zmod(n)) # 已知部分需要左移 (未知部分比特数) 位这里假设未知部分是字节所以左移8*未知字节数。但更精确的是用比特。 # 我们假设未知部分长度不超过k比特那么已知部分需要左移k比特。 f ( (known_part k) x )^e - c # 寻找小根beta参数可以设为0.5或1X是根的上界估计2^k roots f.small_roots(X2^k, beta0.5) if roots: x roots[0] m (known_part k) int(x) print(long_to_bytes(m))实操心得使用Coppersmith方法时对根的上界X的估计非常关键。如果X估计得过大计算会非常慢甚至失败估计得过小则可能找不到根。通常需要根据题目上下文如flag格式、可能的字符集来合理估计未知部分的比特长度。beta参数通常取0.5或1代表了我们对解的大小的先验知识比例在不知道p, q的情况下一般用0.5。小公钥指数攻击和Coppersmith方法告诉我们即使使用了填充如果指数e过小并且明文或填充结构存在某些弱点系统依然可能是不安全的。因此选择e65537不仅是效率上的优化更是安全上的最佳实践它极大地增加了这类攻击的难度。5. 综合攻击路径与实战脚本编写回到BUUCTF这道题我们如何确定使用哪种攻击方法呢这需要根据题目给出的具体参数来决定。一个稳健的解题流程应该是尝试性的、分层次的。下面我给出一个综合性的Python脚本框架它按照攻击的复杂度和常见性依次尝试多种方法。这个框架具有很强的通用性可以作为你日后解RSA题目的一个模板。import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime import sys def rsa_attack(n, e, c, **kwargs): 综合RSA攻击函数 :param n: 模数 :param e: 公钥指数可以是单个int也可以是list :param c: 密文可以是单个int也可以是list与e对应 :param kwargs: 其他参数如已知的p, q, d, 明文高位等 :return: 解密后的明文bytes或None # 攻击1: 直接分解n (适用于小n) print(“[*] 尝试攻击1: 直接分解模数n...”) # 这里可以集成yafu调用或factordb查询示例中我们假设无法分解 # 如果知道p和q可以直接计算私钥 if ‘p‘ in kwargs and ’q‘ in kwargs: p, q kwargs[’p‘], kwargs[’q‘] phi (p-1)*(q-1) d gmpy2.invert(e, phi) m pow(c, d, n) return long_to_bytes(m) # 攻击2: 共模攻击 (当e和c都是列表且长度1n相同时) print(“[*] 尝试攻击2: 共模攻击...”) if isinstance(e, list) and isinstance(c, list) and len(e) len(c) and len(e) 1: # 检查所有n是否相同这里假设只有一个n实际题目可能给出多组n,e,c # 我们假设传入的n是相同的 e1, e2 e[0], e[1] c1, c2 c[0], c[1] # 检查e1, e2是否互素 gcd_val, s1, s2 gmpy2.gcdext(e1, e2) # 扩展欧几里得返回(gcd, s, t) if gcd_val 1: # s1, s2可能为负 if s1 0: c1_inv gmpy2.invert(c1, n) part1 pow(c1_inv, -s1, n) else: part1 pow(c1, s1, n) if s2 0: c2_inv gmpy2.invert(c2, n) part2 pow(c2_inv, -s2, n) else: part2 pow(c2, s2, n) m (part1 * part2) % n return long_to_bytes(m) # 攻击3: 小公钥指数攻击 (低加密指数广播攻击或直接开方) print(“[*] 尝试攻击3: 小公钥指数攻击...”) if isinstance(e, int) and e 100: # e较小 # 情况3.1: 可能 m^e n直接开方 # 注意gmpy2.iroot返回 (根, 是否精确) root, is_exact gmpy2.iroot(c, e) if is_exact: return long_to_bytes(root) # 情况3.2: 低加密指数广播攻击 (需要多组n, c相同的e和m) # 这里需要多组(n, c)本函数框架暂不展开需额外实现CRT # 攻击4: 维纳攻击 (当d较小e较大时) # 需要连分数展开代码略复杂此处省略实现 # 攻击5: 已知明文高位攻击 (Coppersmith) print(“[*] 尝试攻击5: Coppersmith已知高位攻击...”) if ‘known_prefix‘ in kwargs: # 此部分最好在SageMath中运行这里仅展示逻辑 # 需要将已知前缀转换为整数并估计未知部分比特长度 pass print(“[*] 所有常规攻击尝试失败。”) return None # 主函数根据题目数据调用 if __name__ “__main__”: # 示例假设题目数据是共模攻击 n 0xabcdef... # 替换为实际n e_list [0x10001, 0x10003] # 两个不同的e c_list [0x123456..., 0x789abc...] # 对应的两个密文 result rsa_attack(n, e_list, c_list) if result: print(“[] 攻击成功明文为:”, result) # 检查是否是flag格式 if result.startswith(b‘flag{’) or result.startswith(b‘FLAG{’): print(“[] 成功获取flag!”) else: print(“[-] 攻击失败可能需要更特殊的攻击或题目数据有误。”)这个脚本提供了一个自动化的尝试流程。在实际解题时你需要将n,e,c的具体值替换进去。对于共模攻击确保e和c以列表形式传入。对于小指数攻击脚本会先尝试直接开方。更复杂的Coppersmith攻击由于依赖SageMath的强大会更高效通常我会在Jupyter Notebook或单独的Sage脚本中进行。重要提示在CTF中得到的明文m转换为字节后可能不是直接的ASCII字符串。它可能是某种编码如Base64、Hex或者包含了填充字节。因此解密后一定要仔细检查输出。常见的做法是打印result同时打印result.hex()甚至尝试base64.b64decode(result)。有时候flag可能藏在解码后的数据里。6. 从CTF到实战RSA参数的安全准则通过解这道CTF题我们实际上重温了RSA安全应用的几条铁律。这些准则不仅仅是解题技巧更是工程实践中必须遵守的规范模数n必须唯一且足够大每个密钥对应唯一的n绝对禁止复用。2024年的今天n的长度至少应为2048比特对于长期使用的密钥建议3072或4096比特。共用模数会直接导致共模攻击彻底破坏所有相关密钥的安全性。公钥指数e应选用65537选择e655370x10001是行业最佳实践。它避免了小公钥指数攻击计算效率高二进制只有两个1并且与φ(n)互素的概率极高。避免使用e3或e17等小素数尽管它们计算更快但安全性已无法满足现代要求。必须使用标准的填充方案原始RSA教科书RSA是确定性的并且不具备语义安全性。在实际加密或签名中必须使用如OAEP最优非对称加密填充或PSS概率签名方案等填充方案。填充方案引入了随机性可以抵御共模攻击、低指数攻击等多种密码学攻击并防止基于明文结构的攻击。私钥指数d不能过小在生成私钥时要确保私钥指数d不能太小。如果d (1/3) * n^(1/4)则可能遭受维纳攻击或Boneh-Durfee攻击攻击者可以从公钥(n, e)中恢复出私钥d。安全的密钥生成库如OpenSSL都会避免生成过小的d。素数p和q需要强素数生成p和q时应确保它们是强素数即(p-1)/2和(q-1)/2也是素数或至少有大的素因子并且p和q的差值不能太小。这可以抵御费马分解法等特殊分解算法。同时p和q的比特长度应大致相等。定期更换密钥即使遵循了所有准则随着计算能力的提升和密码分析学的进步今天安全的密钥长度未来也可能变得脆弱。对于重要系统应制定密钥轮换策略。在CTF中出题人正是通过故意违反上述一条或几条准则来构造题目。因此解题的过程本质上就是进行安全审计的过程检查参数是否够大、是否唯一、指数是否合适、填充是否存在缺陷。这种思维训练对于从事安全开发或渗透测试工作至关重要。7. 进阶思考当Coppersmith遇到更复杂的情况Coppersmith方法的能力远不止于恢复明文高位。它是一系列基于格约化的强大攻击技术的总称在RSA攻击中还有诸多变种已知私钥低位攻击如果私钥d的低位比特泄露结合公钥(n, e)有可能恢复出完整的d。部分密钥泄露攻击如果素数p或q的高位或低位部分已知有可能利用Coppersmith方法从这些片段中恢复出完整的p或q从而分解n。短填充攻击当同一个明文用相同的公钥但不同的随机填充进行多次加密时如果填充长度过短也可能受到攻击。这些攻击通常出现在更难的CTF题目或学术研究中。它们的共同点是将密码学问题转化为在模数n下寻找某个多项式的小根问题。实现这些攻击通常需要更深入地理解LLL算法和格基构造并熟练使用SageMath的small_roots函数并精心设置参数beta和根的上界X。对于有志于深入密码学领域的朋友我建议从理解Coppersmith攻击的基本论文和经典CTF题目入手。例如PlaidCTF、Google CTF、SECCON等大赛中常有高质量的RSA题目其中会用到这些进阶技巧。解题时不要只满足于跑通脚本要多问为什么为什么这样构造格为什么这个多项式的小根就是我们要的解参数X和beta的数学含义是什么通过这样的追问你才能真正掌握这项武器。最后分享一个我在处理Coppersmith题目时的调试技巧当small_roots()函数返回空列表时不要轻易放弃。首先双重检查你的多项式方程是否构造正确确保它在模n下确实以目标小根为零点。其次尝试调整根的上界X稍微放大一点比如从2^64调到2^70或者调整beta参数尝试0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0。有时Sage默认的算法参数可能需要微调。可以尝试指定small_roots(X..., beta..., epsilon...)中的epsilon为一个较小的值如0.05这有时能帮助找到根。记住密码学攻击很多时候也是一门实验科学。