企业官网建设流程全解析

什么是共模攻击？

当同一个明文 m被用相同的模数 n、不同的公钥指数 e1 和 e2加密两次，得到两个密文 c1 和 c2 时，攻击者可以在不知道私钥的情况下恢复出明文 m。

加密原理

假设我们有：

• 模数 n = 15（p=3, q=5）
• 公钥指数 e1 = 3，e2 = 5（gcd(3,5) = 1）
• 同一个明文 m = 2 被加密两次

加密第一次：c1 = m^e1mod n = 2³mod 15 = 8
加密第二次：c2 = m^e2mod n = 2⁵mod 15 = 2

解密原理

现在我们只知道 n=15, e1=3, e2=5, c1=8, c2=2，要恢复 m。

第一步：检查 gcd(e1, e2)

gcd(3, 5) = 1 ✓ 互质，可以攻击！

代码：

importmath g=math.gcd(e1,e2)

第二步：找 a, b 使得 a×e1 + b×e2 = 1

即找 a, b 使得 3a + 5b = 1

a 和 b 叫什么？

在数学上，a 和 b 称为贝祖系数（Bezout Coefficients），因为它们是贝祖定理的产物：

• 对于任意两个整数 e1 和 e2，一定存在整数 a、b 使得 a×e1 + b×e2 = gcd(e1, e2)
• 当 e1 和 e2 互质（gcd=1）时，a×e1 + b×e2 = 1

a 和 b 是随便选的吗？

不是随便选的！它们必须严格满足 a×e1 + b×e2 = 1。

但满足条件的 a、b 不是唯一的：如果 (a, b) 是一组解，那么 (a+k×e2, b-k×e1) 也是一组解（k 为任意整数）。不过无论选哪组解，最终 m = c1^a× c2^bmod n 的结果都是一样的。

怎么求 a 和 b？

方法一：扩展欧几里得算法（通用方法）

defexgcd(a,b):"""扩展欧几里得算法（迭代版），返回 (gcd, x, y) 使得 a*x + b*y = gcd"""old_r,r=a,b old_s,s=1,0old_t,t=0,1whiler!=0:quotient=old_r//r old_r,r=r,old_r-quotient*r old_s,s=s,old_s-quotient*s old_t,t=t,old_t-quotient*treturnold_r,old_s,old_t g,a,b=exgcd(e1,e2)

方法二：当 gcd(e1, e2) = 1 时，可以用 pow() 快速求：

fromsympyimportmod_inverse# 方法二：用 sympy.mod_inverse 快速求（仅当 gcd=1 时可用）a=mod_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*e1+b2*e2}")

方法三：手算逐一尝试（比赛过程不可能的）

• 3×1 + 5×0 = 3 ≠ 1
• 3×2 + 5×(-1) = 6 - 5 =1✓

所以 a = 2，b = -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

1. 分别计算A = c 1 a ( m o d n ) A = c_1^a \pmod nA=c1a​(modn)
2. 分别计算B = c 2 b ( m o d n ) B = c_2^b \pmod nB=c2b​(modn)（KaTeX parse error: Can't use function '\(' in math mode at position 1: \̲(̲b<0\)→ 先求逆元）
3. 结果m = ( A × B ) ( m o d n ) m=(A\times B)\pmod nm=(A×B)(modn)

代码实现：

part1=pow(c1,b,n)part2=pow(c2,b,n)m=(part1*part2)%n

第四步：处理负数指数

在模运算里不能直接当成普通实数分数1 c 2 k \dfrac{1}{c_2^k}c2k​1​，一定要区分：普通除法 ≠ 模逆元。只有互质条件满足，“模意义下的除法”才有意义。

b = -1 为负数，c2^(-1)就是 c2 在模 n 下的逆元。

c2 = 2，求 inv(2) mod 15：

• 2 × ? ≡ 1 (mod 15)
• 2 × 8 = 16 ≡ 1 (mod 15)
• 所以 inv(2) = 8

代码：

fromsympyimportmod_inverseifb<0:inv_c2=mod_inverse(c2,n)part2=pow(inv_c2,-b,n)

第五步：计算 m

m = c1²× inv(c2) mod 15
m = 8²× 8 mod 15
m = 64 × 8 mod 15
m = 512 mod 15
m =2✓ 恢复出明文！

作业

题目

https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tab=challenges&challenge=922c513e-e335-4f3c-b8a8-abc66773bb89

c1 = 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 n

a 为负数，所以 c1^a 需要先求逆元：

• c1^(-1)mod n = pow(c1, -1, n)
• c1^(-3421980)mod n = pow(inv_c1, 3421980, n)

最终：m = c1^(-3421980)× c2^3968231mod n

第四步：将明文整数转为字节串

明文整数：13040004482819947212936436796507286940525898188874967465457845309271472287032383337801279101

转为字节串：flag{49d91077a1abcb14f1a9d546c80be9ef}

具体实现代码

importmathfromsympyimportmod_inverse# ---- 迭代版扩展欧几里得算法 ----defexgcd(a,b):old_r,r=a,b old_s,s=1,0old_t,t=0,1whiler!=0:q=old_r//r old_r,r=r,old_r-q*r old_s,s=s,old_s-q*s old_t,t=t,old_t-q*treturnold_r,old_s,old_t# ---- 题目参数 ----c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801e1=11187289c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397e2=9647291# ---- 检查 gcd ----g=math.gcd(e1,e2)print(f"gcd(e1, e2) = math.gcd({e1},{e2}) ={g}")# ---- 扩展欧几里得算法（求贝祖系数 a, b）----# 注意：Python 标准库没有 exgcd()，需要自己实现# 当 gcd=1 时也可以用 sympy.mod_inverse 快速替代g,a,b=exgcd(e1,e2)print(f"{a}*{e1}+{b}*{e2}={g}")# ---- 计算 m^g mod n ----ifa<0:inv_c1=mod_inverse(c1,n)part1=pow(inv_c1,-a,n)else:part1=pow(c1,a,n)ifb<0:inv_c2=mod_inverse(c2,n)part2=pow(inv_c2,-b,n)else:part2=pow(c2,b,n)m=(part1*part2)%n# ---- 转换为字节串 ----m_bytes=m.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}