自定义 pow 包装在指数为奇数时少乘一次,实际指数变成 e-1 且与 phi 不互素:分域开 e 次根再 CRT 组合
crypto/rsa · verified
一句话结论
题目用自定义 Mypow(b, e, mod) 代替 pow:e 为偶数时等于 pow(b,e,mod),为奇数时等于 pow(b,e-1,mod)。本例 e = next_prime(666) 必为奇数,实际指数变成 e' = e-1(偶数),而 gcd(e', φ(n)) = e' ≠ 1,于是 RSA 解密退化为「在 GF(p)、GF(q) 上分别开 e' 次根,再对多组根做 CRT 组合,最后按 flag 头筛选唯一明文」。
原理
- RSA 解密的必要条件是私钥指数存在,即
e与φ(n)互素。包装函数悄悄把指数减 1 后,e'为偶数,而φ(n) = (p-1)(q-1)也是偶数,gcd(e', φ(n))至少为 2,d = e'^{-1} mod φ不存在——不能走常规私钥解密。 - 但加密映射本身仍是「求
e'次幂模 n」。只要在GF(p)和GF(q)上分别求x^{e'} ≡ c的所有根(f(x) = x^{e'} - c的多项式求根),再用 CRT 把p侧根与q侧根两两组合,就能得到n上全部e'次根;真实明文必在其中。 - 根的数量等于
gcd(e', p-1) · gcd(e', q-1),本例因e'是小的偶数,根数有限(每侧通常 2~若干个),两两 CRT 的枚举量很小,用 flag 固定前缀(DASCTF/flag{)即可唯一定位。 - 之所以可复用:这是“实现层 bug 改变数学前提”的典型——审计到
pow被包装、指数被条件改写时,应先重算gcd(e, φ),而不是直接套脚本;一旦不互素就转向“求根 + CRT 筛选”而不是求逆。 - 前提是能分解
n:本例由hint与n的二次关系2x² + 7n - hint·x = 0直接解出p。
触发条件
- 加密/签名实现里指数被自定义函数改写(减 1、加 1、按奇偶分支、按 bit 长度处理),且改写后与
φ(n)不互素。 - 已知或可解出
n的分解(提示方程、弱素数、共模等)。 - 单条密文,明文较短且带已知前缀,可用于在多解中筛选。
利用步骤
- 读实现,确认
pow包装的分支条件,算出真实指数e'。 - 由
hint与n解二次方程得p,q = n // p,校验p*q == n。 - 确认
gcd(e', p-1)、gcd(e', q-1)均大于 1(不互素),放弃求逆。 - 在
Zmod(p)、Zmod(q)上分别对x^{e'} - ct求根。 - 枚举两根集合并 CRT,逐候选转字节,筛含已知前缀者。
PoC
# sage
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 36443283250594259606482132779262570582448178589602577809591307671554949253094255209079689901493052116793388954529442162972106210862341856282788030374324677114528044629385805693771773377070021111949953333360526159026822968061585876873187059674130307295006486032106471182393880915860569773206853864515489855553
hint = 57792516722001523643789088224096258172899052039145876393373730235406451592173971020702024058282699663364267742428240581839287357212741266617791207580236457
ct = 24482128269957355675512496312977308128712253968496848873519792376434347925427116612997489113223781321628516365811583310346553402215907938918891908853234881284620764982626375301219763593402089309909155204943747718536894186749932544428588048770663458669109073657836937287831725958017345747881678942488157429000
# 1) 由 hint 的二次关系解 p:2p^2 + 7n - hint*p = 0
R.<x> = Zmod()[]
f = 2*x^2 + 7*n - hint*x
p = int(f.roots()[0][0]); q = n // p
assert p * q == n
# 2) 真实指数是 next_prime(666) - 1(包装函数对奇数 e 少乘一次)
e = gmpy2.next_prime(666) - 1
# 3) 分域开 e 次根
R.<x> = Zmod(p)[]
r1 = (x^e - ct).monic().roots()
R.<x> = Zmod(q)[]
r2 = (x^e - ct).monic().roots()
# 4) CRT 组合 + 按 flag 头筛选
from sage.all import CRT_list
for i in r1:
for j in r2:
m = CRT_list([int(i[0]), int(j[0])], [p, q])
flag = long_to_bytes(int(m))
if b'DASCTF' in flag:
print(flag); break
变体与关联
- 变体:包装函数导致指数加 1(
e+1)时同样可能不互素,处理方式一致。 - 变体:
gcd(e',φ)很大(如e'含2^k)时根数指数级增长,此时改用p-1 = 2^a·m的分解逐层开方(Tonelli-Shanks 的推广 / AMM 算法),并在每一步用已知明文前缀剪枝。 - 变体:若
n无法分解,但gcd(e', φ)小且已知明文高位,可转向 Coppersmith 求小根。 - 关联:[[crypto-rsa-e3-small-plaintext-integer-cube-root]](同为“不开逆、改开根”的思路)、[[ctf-crypto-rsa-noncoprime-common-modulus-iroot-wiener-chain]](不互素指数的另一条恢复路径)、[[crypto-rsa-hint-difference-gcd-factorization]](用提示关系分解
n)。 - 边界:
e'为素数且与φ互素时不存在多解,开根退化为唯一解;p-1/q-1含大素因子时直接求根不可行。
检测与防御
- 本题为 CTF 题,工程侧教训:不要自己实现
pow的“优化”包装;任何对公钥指数的改写都必须重新验证gcd(e, φ(n)) = 1,并在初始化时断言。 - 实现层:加密/签名参数改动后跑自检(用已知明文验证
dec(enc(m)) == m),能第一时间暴露指数被改写。 - 协议层:私钥指数不存在时应直接报错而非退化处理,避免“多解”泄漏可区分信息。