NTRU 格攻击:构造 [[1,h],[0,p]] 用 LLL 恢复私钥 (f,g) 并解密密文
ctf/crypto · verified
一句话结论
当 NTRU 类加密给出公钥 h = g * f^{-1} mod p(g < f < p、gcd(f,g)=1)和密文 c = r*h + m mod p 时,由行向量 [1, h]、[0, p] 生成的二维格中包含短向量 (f, g)——因为 (f, -k) * [[1,h],[0,p]] = (f, f*h - k*p) = (f, g);只要私钥向量满足 Hermite 上界,用 LLL 格基规约即可直接恢复 (f,g),再由 a = c*f mod p = r*g + m*f(当 r*g + m*f < p 时等式在整数上成立)和 m ≡ a * f^{-1} mod g 解出明文。
原理
- 公私钥关系:
h ≡ g·f^{-1} (mod p),即h*f = g + k*p(k 为整数)。因此(f, -k)左乘基矩阵[[1, h], [0, p]]恰好得到(f, f*h - k*p) = (f, g),说明(f,g)是该格中的向量。 - 为什么它是短向量:NTRU 参数通常取
g < f < p,(f,g)的范数远小于一般格向量;LLL 近似求解 SVP,会把短向量规约到基的前几行,从而被提取出来。 - Hermite 条件:
||v|| ≤ sqrt(n) * det(L)^{1/n}。二维格n=2、det(L)=p,右侧约sqrt(2*p);若||(f,g)|| ≈ f小于该值(如f约 2^1024、p约 2^2048),LLL 可直接找到。 - 解密:
c = r*h + m (mod p),两边乘f得c*f ≡ r*g + m*f (mod p);参数设计保证r*g + m*f < p,所以取a = c*f mod p = r*g + m*f;再对g取模得a ≡ m*f (mod g),f在模g下可逆,m ≡ a * f^{-1} (mod g),转字节即明文。 - 范数不平衡时的缩放:若
f过大(例如 1536 位)而p只有 2048 位,||(f,g)|| ≈ f可能超过sqrt(2p);把第二列乘以T:[[1, T*h], [0, T*p]],则(f, -k)乘出(f, T*g),短向量范数约为sqrt(f^2 + (T*g)^2),右侧约sqrt(T*p*2);选取合适的T=2^e(原文遍历 e≈1000..1030)使不等式成立,LLL 恢复(f, T*g)后把g除以T即得正确私钥。 - 边界:LLL 是近似算法,恢复结果依赖参数与实现;同一组参数下可能需要调整
T/重复尝试;f在模g下不可逆、或rg+mf ≥ p时解密公式不成立。
触发条件
- 题目给出 NTRU 形式的
p, h, c,私钥f, g相对p是小量(或可通过缩放变成短向量)。 r*g + m*f < p(无模回绕)保证解密方程在整数上成立;gcd(f,g)=1保证f模g可逆。- 具备 LLL 实现(SageMath
matrix.LLL()、fpylll 等),并能承受二维/小维度格规约。
利用步骤
- 建立格基矩阵
M = [[1, h], [0, p]](必要时改成[[1, T*h], [0, T*p]]并遍历T=2^e)。 - 对
M做 LLL,取第一行作为最短向量;按需取绝对值/除以缩放因子T得到(f, g)。 - 计算
a = c * f % p。 - 计算
m = a * f^{-1} % g,把整数转回字节串。 - 检查输出是否为 flag/可读明文;失败则更换
T、重跑 LLL 或调整符号。
PoC
标准二维格(SageMath):
from sage.all import *
from Crypto.Util.number import long_to_bytes
M = matrix([[1, h], [0, p]])
L = M.LLL()
f, g = L[0]
if f < 0:
f, g = -f, -g
a = c * f % p
m = a * pow(f, -1, g) % g
print(long_to_bytes(int(m)))
范数不平衡时缩放遍历:
for e in range(1000, 1031):
T = 2**e
M = matrix([[1, T*h], [0, T*p]])
f, g = M.LLL()[0]
f, g = abs(f), abs(g) // T
try:
m = c * f % p * pow(f, -1, g) % g
pt = long_to_bytes(int(m))
if b"flag" in pt:
print(pt)
except Exception:
pass
变体与关联
- 变体:缩放因子可改为遍历范围更大/非 2 的幂,或对
h、p同时乘不同因子平衡范数;也可用 CVP/Kannan embedding 处理带噪声变体。 - 关联:同类 LLL 公钥/线性组合攻击见 [[ctf-crypto-lll-public-key-linear-combination-forge-private-key]]、[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]]、[[ctf-crypto-agcd-sda-lattice-small-error-recovery]]。
- 关联:格攻击在其他密码体系的应用见 [[crypto-ecc-ecdsa-partial-nonce-leak-lattice]]、[[crypto-rsa-common-private-exponent-multiprime-lattice]]。
检测与防御
- 出题/实现侧:选择标准 NTRU 参数集,确保私钥向量范数与格行列式关系不满足 Hermite/LLL 恢复条件;不要把
g ≪ f ≪ p的玩具参数用于真实场景。 - 分析侧:先估算
||(f,g)||与sqrt(n)*det(L)^{1/n},判断能否直接 LLL;不平衡时先缩放再规约,并对结果做模g可逆性/明文格式校验。 - 通用:NTRU 的安全性依赖高维格上 SVP 的困难性,低维/小参数玩具实例可以被 LLL 直接攻破;实际部署应遵循标准化参数。