CTF 密码学 RSA 共模攻击3 种 Python 实现方案对比与效率分析在CTF竞赛中RSA共模攻击是一种常见的密码学攻击手段。当两个不同的公钥使用相同的模数n时攻击者可以利用扩展欧几里得算法恢复出明文。本文将深入探讨三种Python实现方案并分析它们在处理2048位大数时的计算效率差异。1. 共模攻击原理与数学基础RSA共模攻击的核心数学原理基于以下条件相同模数n两个互质的加密指数e₁和e₂对应的密文c₁和c₂根据扩展欧几里得算法我们可以找到整数s₁和s₂满足e₁*s₁ e₂*s₂ 1然后通过以下公式恢复明文m (c₁^s₁ mod n) * (c₂^s₂ mod n) mod n关键数学运算模反元素计算当s₁或s₂为负数时大数模幂运算扩展欧几里得算法实现2. 三种Python实现方案2.1 标准扩展欧几里得实现def common_modulus_attack_standard(n, c1, c2, e1, e2): def extended_gcd(a, b): if b 0: return a, 1, 0 else: gcd, x, y extended_gcd(b, a % b) return gcd, y, x - (a // b) * y _, s1, s2 extended_gcd(e1, e2) if s1 0: c1 pow(c1, -1, n) s1 -s1 if s2 0: c2 pow(c2, -1, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m特点纯Python实现无外部依赖使用递归实现扩展欧几里得需要手动处理负指数情况2.2 gmpy2优化版本import gmpy2 def common_modulus_attack_gmpy2(n, c1, c2, e1, e2): gcd, s1, s2 gmpy2.gcdext(e1, e2) if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return int(m)优化点使用gmpy2的gcdext函数计算扩展GCDgmpy2.invert比Python内置pow求逆更快大数运算效率显著提升2.3 Crypto.Util.number实现from Crypto.Util.number import inverse def common_modulus_attack_crypto(n, c1, c2, e1, e2): def extended_gcd(a, b): if b 0: return a, 1, 0 else: gcd, x, y extended_gcd(b, a % b) return gcd, y, x - (a // b) * y _, s1, s2 extended_gcd(e1, e2) if s1 0: c1 inverse(c1, n) s1 -s1 if s2 0: c2 inverse(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m特点使用Crypto库的inverse函数求模逆保持标准算法的结构比纯Python实现稍快但不及gmpy23. 性能对比测试我们在2048位RSA参数下测试三种实现的性能实现方案平均执行时间(ms)内存占用(MB)依赖项标准实现12.455.2无gmpy23.214.1gmpy2Crypto8.765.0pycryptodome测试环境Python 3.8Intel i7-10750H 2.60GHz16GB RAM注意实际性能会因具体输入参数和硬件环境有所不同。gmpy2在连续大数运算中优势明显。4. 无gmpy2环境的替代方案当目标环境无法安装gmpy2时可以考虑以下优化4.1 预计算优化def optimized_attack(n, c1, c2, e1, e2): # 预计算所有可能的模逆 inv_cache {} def get_inv(x): if x not in inv_cache: inv_cache[x] pow(x, -1, n) return inv_cache[x] # 其余代码与标准实现相同 ...4.2 并行计算from concurrent.futures import ThreadPoolExecutor def parallel_pow(bases, exps, mod): with ThreadPoolExecutor() as executor: results list(executor.map(pow, bases, exps, [mod]*len(bases))) return results[0] * results[1] % mod5. 实战案例分析以BUUCTF的RSA3题目为例我们演示攻击流程n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 e1 11187289 e2 9647291 # 使用gmpy2版本解密 m common_modulus_attack_gmpy2(n, c1, c2, e1, e2) print(bytes.fromhex(hex(m)[2:]))输出结果bflag{49d91077a1abcb14f1a9d546c80be9ef}6. 效率优化建议缓存计算结果对于固定模数n的多次计算缓存模逆结果并行计算独立的大数模幂运算可以并行处理算法选择竞赛环境优先使用gmpy2受限环境使用Crypto库优化算法输入验证添加对n、e、c的合法性检查def validate_input(n, c1, c2, e1, e2): assert n 1 and c1 0 and c2 0 assert e1 1 and e2 1 assert math.gcd(e1, e2) 17. 不同场景下的方案选择根据实际需求选择最佳实现场景推荐方案理由CTF竞赛gmpy2版本执行速度最快教学演示标准实现代码最透明受限环境Crypto版本依赖较少批量处理并行优化版吞吐量最高在实际CTF比赛中遇到共模攻击题目时建议优先尝试gmpy2方案特别是在时间紧张的竞赛环境下。而对于需要代码审计或教学的情况标准实现更能清晰展示算法原理。