2026.8.13（3）【Crypto】big e

📌 题目信息

🛠️ 使用工具

• Python 3：编写解密脚本，使用 pow 求模逆元。

📝 解题思路

这道题是一个典型的 RSA 共模攻击。题目中使用了同一个模数 n 和两个不同的公钥指数 e_1 和 e_2 对同一条明文分别加密，生成了两个密文 ct_1 和 ct_2。攻击者虽然不知道私钥 d，但可以通过数学方法直接恢复出明文。

第 1 步：识别攻击特征

观察题目给的参数：

• n 只有一个，两个加密过程共用。
• e_1 和 e_2 是两个不同的 16 位素数（互质）。
• 密文 ct_1 和 ct_2 分别对应两次加密。

这些特征完全符合 RSA 共模攻击 的条件：同一模数 n、不同公钥指数、同一明文。

第 2 步：理解共模攻击的数学原理（为什么能破解？）

① RSA加密公式回顾

题目的两次加密分别是：

c1 = m^e1 mod n
c2 = m^e2 mod n

其中 m 是明文（就是我们要的 Flag），n 是模数。

② 贝祖定理与扩展欧几里得算法

因为 e1 和 e2 互质，根据贝祖定理（Bézout's identity），一定存在整数 s 和 t，使得：

s * e1 + t * e2 = 1

那么，如何找到这个 s 和 t 呢？ 答案就是扩展欧几里得算法。
举个简单例子：对于 a=3, b=5，扩展欧几里得可以算出：

3 * 2 + 5 * (-1) = 1
所以 x=2, y=-1 就是一组解。

具体做法如下：
1. 先做“普通欧几里得”（辗转相除法）：
就是不断拿“大的除以小的”，直到余数为 0。

• 5 ÷ 3 = 1 余 2
• 3 ÷ 2 = 1 余 1
• 2 ÷ 1 = 2 余 0（结束）
  所以 GCD(3, 5) = 1。这个过程我们只是在“往下除”。

2. 再看“扩展欧几里得”（逆推回去）：
我们已知最后的余数是 1，现在要逆着把每一步的余数“拼回去”，凑出 3 和 5 的倍数。

• 从最后一步（第 2 步）看：1 = 3 – 1 × 2
• 把第 1 步的余数 2 = 5 – 1 × 3 代入上式：
  1 = 3 – 1 × (5 – 1 × 3)
  1 = 3 – 5 + 3
  1 = 2 × 3 + (-1) × 5
• 所以得到 s=2，t=-1。验证：2×3 + (-1)×5 = 6 – 5 = 1，完美成立！
  这就是扩展欧几里得算法的“灵魂”：正向不断求余，反向一步步回代。

⚠️ 注意：s 和 t 必然一正一负（因为 e1 和 e2 都是正数，如果同号，结果不可能等于 1）。

③ 组合密文，消除指数

现在我们把两个密文做如下运算：

c1^s * c2^t mod n

代入 c1 = m^e1 mod n 和 c2 = m^e2 mod n：

= (m^e1)^s * (m^e2)^t mod n
= m^(s*e1 + t*e2) mod n
= m^1 mod n
= m

注意题目已经给了公钥指数e1和e2，所以这里根据贝祖定理，一定可以计算出整数 s 和 t，使得s*e1 + t*e2 = 1 ，于是我们成功绕过了私钥，直接得到明文（关键！！）。

④ 负数指数的处理

由于 s 和 t 中有一个是负数，而模运算中负指数没有直接定义。但我们知道：

a^(-k) ≡ (a^(-1))^k (mod n)

即：先求底数 a 在模 n 下的模逆元（记作 a^{-1}），再将其乘方 k 次。

所以在代码中：

if s < 0:
s = -s
ct_1 = pow(ct_1, -1, n) # 求逆元

同理处理 t。

第 3 步：编写解密脚本

编写一个通用的共模攻击脚本，步骤如下：

from Crypto.Util.number import long_to_bytes

# 扩展欧几里得算法，返回 (g, x, y) 满足 ax + by = g
def egcd(a, b):
if a == 0:
return b, 0, 1
else:
g, y, x = egcd(b % a, a)
return g, x – (b // a) * y, y

# 题目给出的参数
n = 20041933763448357190627850343717972264528582967835527546142957190548605428270610029367862231281895787713359644234851479710776535385541439755032309687483077090218979985453754364407030590831392946785171723586209911295724249654470575605442111447225710502302358942926274605617178895040432859429896967144420329616663507781993472314294836911728767905434642257924102824396656593460442406211312774327070056184991640489525243074951726793316964397447506279491375765341749074988401265888189321863750941333198393830420513963816131832584076574157616777287739971033307821046386250151071559472869001815834079430740105662029229636911
e_1 = 38393
e_2 = 33179
ct_1 = 5649565335684829166994703709424227526893862676464227714220335589276704152604924324114025311155729514770870986954236504564704555535527067819510001985630888010489410355084498786686405391985307787813163409887408873131599860500818287249474949435981248525429437566989511739623645812030127508754237307712031275069780710099525638162980612740682033778940586593666680892993610688520294640884980062959079158405843270214715267881440440339150600253703915746065480485251932360881192748881417272231086499695809894156350146444967947730629173024309214554705882003920254677073584631736742572109190599880801473561959319027076441953445
ct_2 = 18057738004521442202581208706347939725140669900210781627129228864852861993001064574996038998190758020094241377866589024516040225406530219251533264723200285643625227689027372929065070061403841600339743979018711778484342112384547861311017571072207706363341501151970830224052331515660939863240931224477883263629549854691715424922845010950429159326308647808310970838674468530257927010981568201656330319135247562919603753523391148946139453657084433473736518140826834607288043167145971704069967785291825113657089124890698730576640845997643271760048177660480776933178966895624625446578014520381072642845438343988815282525599

# 1. 计算贝祖系数
_, s, t = egcd(e_1, e_2)

# 2. 处理负数指数
if s < 0:
s = -s
ct_1 = pow(ct_1, -1, n) # 求 ct_1 在模 n 下的逆元
if t < 0:
t = -t
ct_2 = pow(ct_2, -1, n)

# 3. 计算明文整数
m = (pow(ct_1, s, n) * pow(ct_2, t, n)) % n

# 4. 转为字节并打印
flag = long_to_bytes(m).decode()
print(flag)

⚠️ 注意：pow(ct_1, -1, n) 是 Python 3.8+ 的语法，用于计算模逆元。

第 4 步：运行脚本获取 Flag

运行上述脚本，输出结果为：

🏁 最终 Flag

qsnctf{ba1073db090b3090c111339b0a7ffce5}