CTF中的RSA低位攻击：从理论到实战

在CTF密码学挑战中，常出现以下两类RSA低位泄露题型：

1. 私钥低位泄露：给出的末位 

2. 素数低位泄露：给出或的末位 

这类题目要求选手利用Coppersmith定理恢复完整密钥，以下是系统性解题方法。

已知：n,e,d_low = d mod 2^k

1. 由RSA定义：ed ≡ 1 mod ϕ(n)⇒ ed = 1 + kϕ(n)

2. 代入ϕ(n) = n − (p+q) + 1构造方程：ed = 1 +k (n − (p + q) + 1)

3. 通过已知的d_low建立方程，利用Coppersmith求解高位

def recover_d(n, e, d_low, k_bits):    P.<x> = PolynomialRing(Zmod(e*n))    f = e*x - 1 + e*d_low    roots = f.small_roots(X=2^(n.nbits()-k_bits), beta=0.3)if roots:return roots[0] << k_bits | d_low    return None# 示例参数n = 0xabcdef... e = 65537d_low = 0x12345...recovered_d = recover_d(n, e, d_low, k_bits=200)

场景1：已知p的低k位

1. 设完整素数 p=p_high⋅2^k+p_low

2. 构造方程 n ≡ 0 mod p ⇒ n ≡ 0 mod(p_high⋅2^k+p_low)

3. 用Coppersmith求解p的高位

def recover_p(n, p_low, k_bits):    P.<x> = PolynomialRing(Zmod(n))    f = x*2^k_bits + p_low    roots = f.monic().small_roots(X=2^(n.nbits()//2 - k_bits), beta=0.4)if roots:return roots[0]*2^k_bits + p_lowreturn None

场景2：已知p/q的高位（变形题）

# 已知p的高k位（如p = pHigh*2^m + x）f = (p_high << m) + x

1. X值选择：根据未知位数量设置上限，例如未知100位则X=2^100

2. beta参数：通常取0.4-0.49（需满足beta ≤ 未知位数/总位数）

3. 多解处理：遍历可能的根进行验证

• 使用defund/coppersmith等优化算法

• 尝试不同beta值组合

• 优先验证低位是否符合模运算特性

题目给出：

n = 124373462456753234876885220553527371514412189273708387803379740454747329757646714507732149997806416311212770832817567344597369013077503761564730637292822190898605501605620096233619021437529457696534197112644821519151834514614442850344611947221582810814021437512623722573900305582615607466805014405632112212089e = 65537p_low = 0x635f726d21645d1d # 已知p的最后64位ciphertext = 0x8af11...dac3 # 密文

1. 目标：通过已知p的低64位恢复完整p，进而分解n解密

2. 关键点：

• n是1024位RSA，即p/q各512位

• 已知p的低64位（占总长度的12.5%）

Step1：构造多项式

设完整素数 p=x⋅264+plowp=x⋅264+plo__w，其中x为未知高位建立方程：n≡0modp⇒n=p⋅q=(x⋅264+plow)⋅qn≡0modp⇒n=p⋅q=(x⋅264+plo__w)⋅q

Step2：SageMath求解

n = 124373...089p_low = 0x635f726d21645d1dk_bits = 64

# 构造模方程

P.<x> = PolynomialRing(Zmod(n))f = x*2^k_bits + p_lowroot = f.monic().small_roots(X=2^(512-k_bits), beta=0.4)  # X=2^(512-64)if root:    p = int(root[0])*2^k_bits + p_low    assert n % p == 0, "Recovery Failed!"    q = n // p

Step3：密钥生成与解密

phi = (p-1)*(q-1)d = inverse_mod(e, phi)flag = pow(ciphertext, d, n)print(bytes.fromhex(hex(flag)[2:]))

• X=2^(512-64)：x的取值范围上限（高位未知部分）

• beta=0.4：根据经验公式选择（需满足beta ≤ 未知位数/总位数）

• monic()：将多项式首系数归一化提升求解效率

1. 若未找到解，尝试：

• 调整beta值（0.3-0.49）

• 检查p_low是否正确（常见陷阱：题目可能给出十六进制但实际是十进制）

2. 多解验证：当small_roots返回多个解时，需逐个检查是否满足n%p==0

1. 密钥存储：使用HSM保护私钥完整位

2. 白盒加密：避免侧信道泄露

3. 参数检查：生成密钥后验证d>2^{n.bitlength()/2}

掌握Coppersmith攻击方法需要深入理解模方程构造技巧，建议通过CTF实战平台（如CryptoHack）进行专项训练。

记住：数学是密码学的灵魂，而自动化工具是解题的利剑。