环卷积线性系统恢复稀疏向量:F_65537[x]/(x^70+1) 上的 NTRU 类方程
ctf/crypto · verified
一句话结论
当服务端在环 F_65537[x]/(x^70+1) 上给出 a 与 v=a·s,且 s 是 0/±1 的稀疏向量时,可以把每个 s[j] 对输出的贡献写成矩阵的一列,构造 A·s=v (mod 65537) 并解线性系统,从而恢复 s;本题再按分组取每组唯一非零项得到 path,派生密钥解密 flag。
原理
- 环乘法:卷积规则
k=i+j; if k>=N: k-=N, sign=-1; out[k]+=sign*a[i]*s[j]等价于在R=F_P[x]/(x^N+1)中计算v=a·s(x^N=-1)。 - 线性化:固定
a时,映射s ↦ a·s是线性的。对每个j,把s[j]=1时的输出向量作为矩阵A的第j列;则A·s=v mod P。s的每个分量是 0/±1,但线性系统不依赖稀疏性,直接解出唯一向量。 - 稀疏/分组约束:本题
s的取值只有 0、1、-1(P-1),且按shape=[groups,width]分组,每组恰好一个非零项;解出s后按组检查,得到path=[(index, sign)]。 - 派生密钥:
raw=",".join(f"{i}:{s}" for i,s in path),key=sha256(b"layer-02:"+raw),HMAC-SHA256 计数器流与box异或得到 flag。 - 为什么成立:环乘法的线性性 + 足够多的输出分量(70 个方程、70 个未知数)使
A可逆或列满秩;s的稀疏性只是用来校验/分组,不是求解必需。 - 边界:如果
a与x^N+1不互素,A可能奇异;需要更多样本/不同a。本题a随机,矩阵通常可逆。
触发条件
- 已知环参数
N、模数P、a与v=a·s;s维度为N。 A列满秩(或至少解唯一);P为素数,元素可求逆。s的取值/分组约束已知(本题 0/±1、每组一个非零),用于校验和恢复path。- 能实现 GF(P) 高斯消元/矩阵求逆。
利用步骤
- 读取
u(即a)、v、shape=[groups,width],确认N=len(a)=70、P=65537。 - 构造
A:对每个j,模拟s[j]=1、其余为 0 的卷积,得到列向量;注意k>=N时减N且符号取负。 - 解
A·s=v mod P(高斯消元/矩阵求逆);检查每个分量是否为 0/1/P-1。 - 按
groups/width分组,每组应恰好一个非零;记录(index, +1/-1)组成path。 - 用
sha256(b"layer-02:"+raw)派生 HMAC-SHA256 流,异或box得到 flag。 - 用
flag{前缀/可打印性验证。
PoC
P = 65537
N = 70
def conv_matrix(a):
A = [[0] * N for _ in range(N)]
for j in range(N):
for i, x in enumerate(a):
k = i + j
sign = 1
if k >= N:
k -= N
sign = -1
A[k][j] = (sign * x) % P
return A
def solve_linear_mod(A, b, p=P):
n = len(b)
M = [[A[i][j] % p for j in range(n)] + [b[i] % p] for i in range(n)]
row, pivots = 0, []
for col in range(n):
pivot = next((r for r in range(row, n) if M[r][col] % p), None)
if pivot is None:
continue
M[row], M[pivot] = M[pivot], M[row]
inv = pow(M[row][col], -1, p)
M[row] = [(x * inv) % p for x in M[row]]
for r in range(n):
if r != row and M[r][col] % p:
f = M[r][col] % p
M[r] = [(M[r][c] - f * M[row][c]) % p for c in range(n + 1)]
pivots.append(col)
row += 1
if row == n:
break
if len(pivots) != n:
raise RuntimeError("singular matrix")
x = [0] * n
for r, col in enumerate(pivots):
x[col] = M[r][-1] % p
return x
s = solve_linear_mod(conv_matrix(u), v)
path = []
_, groups, width = shape
for g in range(groups):
picked = []
for i in range(g * width, (g + 1) * width):
if s[i] == 1:
picked.append((i, 1))
elif s[i] == P - 1:
picked.append((i, -1))
assert len(picked) == 1
path.append(picked[0])
变体与关联
- 变体(NTRU 真实参数):大
N/大q时矩阵求逆不可行,需要格攻击/理想格结构;本题是玩具参数。 - 变体(稀疏性利用):若
N很大但s极稀疏,可用压缩感知/格方法而不是满矩阵。 - 变体(多组 a,v):多个样本可联立提高秩/恢复不同密钥。
- 关联卡片:[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](格方法解 LWE)、[[ctf-crypto-sparse-error-linear-system-nullspace-enumeration]](稀疏错误线性系统)、[[crypto-implementation-dirichlet-convolution-parameter-inversion]](卷积参数反演)。
- 边界:
A奇异、P非素数、s分量超出 0/±1 时需调整;大参数下高斯消元复杂度O(N^3)。
检测与防御
- CTF 识别:看到
x^N+1、卷积规则、a与a*s、稀疏 0/±1 向量,优先线性化求逆。 - 密码设计:NTRU 类方案的安全依赖大维数/格困难性;玩具参数(N=70, q=65537)可被线性代数直接攻破。
- 实现:卷积矩阵构造注意
x^N=-1的符号;高斯消元要处理奇异与模逆。