什么是共模攻击当同一个明文 m被用相同的模数 n、不同的公钥指数 e1 和 e2加密两次得到两个密文 c1 和 c2 时攻击者可以在不知道私钥的情况下恢复出明文 m。加密原理假设我们有模数 n 15p3, q5公钥指数 e1 3e2 5gcd(3,5) 1同一个明文 m 2 被加密两次加密第一次c1 me1mod n 23mod 15 8加密第二次c2 me2mod n 25mod 15 2解密原理现在我们只知道 n15, e13, e25, c18, c22要恢复 m。第一步检查 gcd(e1, e2)gcd(3, 5) 1 ✓ 互质可以攻击代码importmath gmath.gcd(e1,e2)第二步找 a, b 使得 a×e1 b×e2 1即找 a, b 使得 3a 5b 1a 和 b 叫什么在数学上a 和 b 称为贝祖系数Bezout Coefficients因为它们是贝祖定理的产物对于任意两个整数 e1 和 e2一定存在整数 a、b 使得 a×e1 b×e2 gcd(e1, e2)当 e1 和 e2 互质gcd1时a×e1 b×e2 1a 和 b 是随便选的吗不是随便选的它们必须严格满足 a×e1 b×e2 1。但满足条件的 a、b 不是唯一的如果 (a, b) 是一组解那么 (ak×e2, b-k×e1) 也是一组解k 为任意整数。不过无论选哪组解最终 m c1a× c2bmod n 的结果都是一样的。怎么求 a 和 b方法一扩展欧几里得算法通用方法defexgcd(a,b):扩展欧几里得算法迭代版返回 (gcd, x, y) 使得 a*x b*y gcdold_r,ra,b old_s,s1,0old_t,t0,1whiler!0:quotientold_r//r old_r,rr,old_r-quotient*r old_s,ss,old_s-quotient*s old_t,tt,old_t-quotient*treturnold_r,old_s,old_t g,a,bexgcd(e1,e2)方法二当 gcd(e1, e2) 1 时可以用 pow() 快速求fromsympyimportmod_inverse# 方法二用 sympy.mod_inverse 快速求仅当 gcd1 时可用amod_inverse(e1,e2)# a e1^(-1) mod e2b(1-a2*e1)//e2# 由 a*e1 b*e2 1 推出print(f方法二 sympy:{a2}*{e1}{b2}*{e2}{a2*e1b2*e2})方法三手算逐一尝试比赛过程不可能的3×1 5×0 3 ≠ 13×2 5×(-1) 6 - 5 1✓所以 a 2b -1第三步带入m ( c 1 a ⋅ c 2 b ) m o d n m \big(c_1^a \cdot c_2^b\big)\bmod nm(c1a⋅c2b)modn分别计算A c 1 a ( m o d n ) A c_1^a \pmod nAc1a(modn)分别计算B c 2 b ( m o d n ) B c_2^b \pmod nBc2b(modn)KaTeX parse error: Cant use function \( in math mode at position 1: \̲(̲b0\)→ 先求逆元结果m ( A × B ) ( m o d n ) m(A\times B)\pmod nm(A×B)(modn)代码实现part1pow(c1,b,n)part2pow(c2,b,n)m(part1*part2)%n第四步处理负数指数在模运算里不能直接当成普通实数分数1 c 2 k \dfrac{1}{c_2^k}c2k1一定要区分普通除法 ≠ 模逆元。只有互质条件满足“模意义下的除法”才有意义。b -1 为负数c2(-1)就是 c2 在模 n 下的逆元。c2 2求 inv(2) mod 152 × ? ≡ 1 (mod 15)2 × 8 16 ≡ 1 (mod 15)所以 inv(2) 8代码fromsympyimportmod_inverseifb0:inv_c2mod_inverse(c2,n)part2pow(inv_c2,-b,n)第五步计算 mm c12× inv(c2) mod 15m 82× 8 mod 15m 64 × 8 mod 15m 512 mod 15m 2✓ 恢复出明文作业题目https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tabchallengeschallenge922c513e-e335-4f3c-b8a8-abc66773bb89c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 e1 11187289 c2 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 e2 9647291解题过程第一步检查 gcd(e1, e2)gcd(11187289, 9647291) 1互质可以攻击第二步用扩展欧几里得算法求 a, b找到 a -3421980, b 3968231使得-3421980 × 11187289 3968231 × 9647291 1第三步计算 m c1^a × c2^b mod na 为负数所以 c1^a 需要先求逆元c1(-1)mod n pow(c1, -1, n)c1(-3421980)mod n pow(inv_c1, 3421980, n)最终m c1(-3421980)× c23968231mod n第四步将明文整数转为字节串明文整数13040004482819947212936436796507286940525898188874967465457845309271472287032383337801279101转为字节串flag{49d91077a1abcb14f1a9d546c80be9ef}具体实现代码importmathfromsympyimportmod_inverse# ---- 迭代版扩展欧几里得算法 ----defexgcd(a,b):old_r,ra,b old_s,s1,0old_t,t0,1whiler!0:qold_r//r old_r,rr,old_r-q*r old_s,ss,old_s-q*s old_t,tt,old_t-q*treturnold_r,old_s,old_t# ---- 题目参数 ----c122322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361n22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801e111187289c218702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397e29647291# ---- 检查 gcd ----gmath.gcd(e1,e2)print(fgcd(e1, e2) math.gcd({e1},{e2}) {g})# ---- 扩展欧几里得算法求贝祖系数 a, b----# 注意Python 标准库没有 exgcd()需要自己实现# 当 gcd1 时也可以用 sympy.mod_inverse 快速替代g,a,bexgcd(e1,e2)print(f{a}*{e1}{b}*{e2}{g})# ---- 计算 m^g mod n ----ifa0:inv_c1mod_inverse(c1,n)part1pow(inv_c1,-a,n)else:part1pow(c1,a,n)ifb0:inv_c2mod_inverse(c2,n)part2pow(inv_c2,-b,n)else:part2pow(c2,b,n)m(part1*part2)%n# ---- 转换为字节串 ----m_bytesm.to_bytes((m.bit_length()7)//8,big)print(f明文:{m_bytes.decode(utf-8)})运行结果gcd(e1, e2) 1 -3421980*11187289 3968231*9647291 1 明文: flag{49d91077a1abcb14f1a9d546c80be9ef}答案flag{49d91077a1abcb14f1a9d546c80be9ef}