二元 Coppersmith 小根:两个未知数联立二次多项式恢复 RSA 明文
crypto/rsa · verified
一句话结论
当 RSA 相关方程中有两个都小于 2^k 的未知量(例如两次模逆的高 k 位泄露、低 k 位未知)时,先消去公共明文得到二元多项式 f(x,y),再用自实现的二元 Coppersmith small_roots 在 (2^k, 2^k) 范围内同时求出两个小根,即可恢复明文。
原理
- 典型题目:明文
s,素数p已知;对两个随机t_i计算inv_i = (s+t_i)^{-1} mod p,只公开h_i = (inv_i >> k) << k,即模逆的高位、低k位被清零。于是inv_i = h_i + r_i,0 ≤ r_i < 2^k。 - 由
(h_i+r_i)(s+t_i) ≡ 1 (mod p)得(h_i+r_i)s ≡ 1 - (h_i+r_i)t_i (mod p)。令A_i=h_i、B_i=1-h_i·t_i,则(A_i+r_i)s ≡ B_i - r_i·t_i (mod p)。 - 两个方程都含同一个
s;把第一式乘(A_2+r_2)、第二式乘(A_1+r_1)后相减,消去s,得到只含r_1,r_2的二元多项式:f(r1,r2) = B1·A2 - B2·A1 + r2·(B1 + A1·t2) - r1·(B2 + A2·t1) + r1·r2·(t2 - t1) ≡ 0 (mod p)。 r1,r2都小于2^k,相对p很小;这是模已知素数p的二元小根问题。二元 Coppersmith 用f的幂与x^i y^j移位构造格,LLL 后取短向量,再求理想簇(variety)得到整数根。- 得到
r1后,inv1 = h1 + r1 mod p,由(inv1)(s+t1) ≡ 1解出s = (1 - inv1·t1)·inv1^{-1} mod p。 - Sage 9.3 自带的
small_roots不支持二元多项式,需要自实现多元版本;示例用m=5的移位参数。
触发条件
- 已知模数
p(或p是n的因子且满足相应beta条件)、两组(t_i, h_i)。 - 每个未知量
r_i都小于2^k,且k相对p足够小,使格方法可解。 - 两组方程共享同一个明文
s,可消元得到二元多项式。 - 能运行 Sage 的 LLL 与理想簇求解;Sage 版本需支持自定义多元
small_roots。
利用步骤
- 解析
p、(t1,h1)、(t2,h2),确认h_i是模逆去掉低k位后的值。 - 计算
A1=h1、A2=h2、B1=1-t1·A1、B2=1-t2·A2。 - 构造
f = B1*A2 - B2*A1 + y*(B1 + A1*t2) - x*(B2 + A2*t1) + x*y*(t2-t1),变量x=r1,y=r2。 - 调自定义
small_roots(f, (2^k, 2^k), m=5),得到(r1,r2)候选。 - 取
r1,计算inv1=(h1+r1) mod p,再算s=((1-inv1*t1)*inv1^{-1}) mod p。 - 转字节得到 flag;用
(h1+r1)(s+t1) mod p == 1校验。
PoC
from gmpy2 import *
from Crypto.Util.number import *
import itertools
p = ...
t1, h1 = ...
t2, h2 = ...
A1, A2 = h1, h2
B1, B2 = 1 - t1 * A1, 1 - t2 * A2
PR = PolynomialRing(Zmod(p), names=['x', 'y'])
x, y = PR.gens()
f = B1*A2 - B2*A1 + y*(B1 + A1*t2) - x*(B2 + A2*t1) + x*y*(t2 - t1)
k = 128
X = 2^k
Y = 2^k
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
roots = small_roots(f, (X, Y), m=5)
print(roots)
r1 = int(roots[0][0])
inv1 = (h1 + r1) % p
m = ((1 - inv1 * t1) * inverse_mod(inv1, p)) % p
print(long_to_bytes(m))
变体与关联
- 变体:样本数
d>2时,可两两消元或构造更多变量,用多元 Coppersmith/格方法求解。 - 变体:
p不是直接给出、而是n的未知因子时,需要引入beta参数,按p的规模选择界。 - 变体:未知量不是模逆的低位而是高位,可改设
inv = r·2^k + h_lo,重新推导消元式。 - 关联:[[crypto-rsa-partial-plaintext-high-bits-coppersmith]](一元小根)、[[crypto-rsa-partial-prime-high-bits-coppersmith]](因子小根)、[[crypto-rsa-multiprime-partial-key-coppersmith]](多元/多素数场景)。
检测与防御
- 防御:不要泄露模逆的高位/低位;需要公开校验值时使用随机化或哈希,而不是截断的模逆。
- 防御:使用标准 RSA-OAEP 等方案,避免把明文与随机数组合成可消元的代数关系。
- 检测:审计中出现
(inv >> k) << k、两次以上模逆截断、同一明文的多个相关值;CTF 中看到p与两组(t,h)即可按本卡尝试。 - 响应:确认模逆部分泄露后,相关明文与私钥材料应视为失陷,轮换密钥并排查历史数据。