题目回顾

该题目提供了一组 RSA 加密的参数，包括公钥指数 e、两个大素数 p 和 q，以及密文 c。要求我们解密出原始明文 m。

已知参数

公钥指数 (e):
```
e = 15
```

素数 (p):

p = 5787222305777209512262474249244794237065756326718637677563926399912102998238238932691915883680852764360339657453541520126740501334731391462921270092825561

素数 (q):

q = 10111241397646344099231145262379017618139453896281400953386716762942327959742747939245765751686811392320346902374279922240577945339761221088737443752162629

密文 (c):

c = 32966311998568049751620491316882873597067466204334745472749990770205777075918461832930873069801888997659326011373601710520150688126730186357963781365253139365104376745890253761612763280897233928482429448491903090758335034298212464171556884740072764043302348824188102589373055730702026853687688157030795220298

借助了群友的神力

import gmpy2
import libnum

e= 15
p=5787222305777209512262474249244794237065756326718637677563926399912102998238238932691915883680852764360339657453541520126740501334731391462921270092825561 
q=10111241397646344099231145262379017618139453896281400953386716762942327959742747939245765751686811392320346902374279922240577945339761221088737443752162629
c=32966311998568049751620491316882873597067466204334745472749990770205777075918461832930873069801888997659326011373601710520150688126730186357963781365253139365104376745890253761612763280897233928482429448491903090758335034298212464171556884740072764043302348824188102589373055730702026853687688157030795220298
n=p*q

gcd_q = gmpy2.gcd(e, q - 1)  # 1
d = gmpy2.invert(e, q - 1)
m = pow(c, d, q)
print(libnum.n2s(int(m)))

解题思路

1. 发现问题

标准的 RSA 解密流程需要计算私钥 d，其中 d 是 e 模 φ(n) 的乘法逆元，即 d = e⁻¹ mod φ(n)，而 φ(n) = (p-1)(q-1)。计算该逆元的前提是 e 和 φ(n) 必须互素，即 gcd(e, φ(n)) = 1。

我们来检查这个条件：

e = 15 = 3 * 5
p - 1 的末尾是 0，因此 p-1 是 5 的倍数。
这意味着 φ(n) = (p-1)(q-1) 也是 5 的倍数。
所以 gcd(e, φ(n)) 至少为 5，不等于 1。

结论： 无法通过标准方式计算私钥 d 来直接对模 n 解密。

2. 柳暗花明

虽然 e 和 φ(n) 不互素，但解密仍有可能。我们可以尝试利用中国剩余定理的思想，分别在模 p 和模 q 的意义下进行解密。这需要 e 与 p-1 或 q-1 互素。

我们来检查 e 与 p-1 和 q-1 的最大公约数：

gcd(e, p - 1): 因为 p-1 是 5 的倍数，所以 gcd(15, p - 1) = 5。我们无法在模 p 的意义下直接求逆。
gcd(e, q - 1): 经过计算，gcd(15, q - 1) = 1。

结论： 我们可以计算 e 在模 q-1 下的逆元，从而在模 q 的意义下恢复明文。

3. 解密原理

既然 gcd(e, q - 1) = 1，我们可以计算出 d_q 满足：
d_q ≡ e⁻¹ (mod q - 1)

根据 RSA 的加密过程，我们有：
c ≡ m^e (mod n)

这也意味着：
c ≡ m^e (mod q)

两边同时取 d_q 次方：
c^d_q ≡ (m^e)^d_q ≡ m^(e*d_q) (mod q)

由于 e*d_q ≡ 1 (mod q - 1)，我们可以将其写成 e*d_q = k*(q-1) + 1 的形式（其中 k 是某个整数）。代入上式：
c^d_q ≡ m^(k*(q-1) + 1) ≡ m * (m^(q-1))^k (mod q)

根据费马小定理，m^(q-1) ≡ 1 (mod q)。因此：
c^d_q ≡ m * 1^k ≡ m (mod q)

这样，我们就得到了 m' = m mod q。在 CTF 竞赛中，如果明文本身不是一个非常大的数字（即 m < q），那么我们计算出的 m' 就等于原始明文 m。

小技巧总结

条件	能否解密	解密方式
`gcd(e, φ(n)) == 1`	✅	标准 RSA 解密，`d = inverse(e, φ(n))`
`gcd(e, p−1) == 1`	✅	可在 `mod p` 意义下解密，得到 `m mod p`
`gcd(e, q−1) == 1`	✅	可在 `mod q` 意义下解密，得到 `m mod q`
`gcd(e, p−1) > 1`	❌	无法直接求 `e` 模 `p-1` 的逆元
`gcd(e, q−1) > 1`	❌	无法直接求 `e` 模 `q-1` 的逆元

最终结果

运行上述代码后，我们成功得到明文：

next_time_make_sure_to_choose_the_appropriate_e_788403071518

Challenge 090