模逆隐藏数:data = t·m⁻¹ mod g,2×2 格配平缩放恢复短 t 与明文 m
ctf/crypto · verified
一句话结论
当 data ≡ t·m^{-1} (mod g),g 是 512 bit 素数、t 只有 150 bit 而 m 是较短的明文时,(k, m)·[[g·2^150, 0], [data·2^150, 1]] 得到向量 (t·2^150, m);用缩放因子 2^150 把两个分量配到同一量级后,LLL 会把这个短向量直接约出来,从而同时恢复 t 与明文 m。
原理
- 由
data ≡ t·m^{-1} (mod g)两边乘m:data·m ≡ t (mod g),即存在整数k使k·g + data·m = t。 - 构造二维格基
M = [[g·2^150, 0], [data·2^150, 1]]。整数系数向量(k, m)在M上的像为(k·g·2^150 + m·data·2^150, m) = (t·2^150, m)。 - 该像向量长度:
t150 bit 乘2^150后约 300 bit,m(短明文)也约 300 bit,两个分量同量级,整体远短于格的行范数(约g·2^150,600+ bit)。 - LLL 在多维格中寻找短向量,二维格上等价于高斯约减,因此会直接返回
±(t·2^150, m);取绝对值、去掉缩放、long_to_bytes即得 flag。 - 为什么缩放是必需的:不配平时第一分量
t只有 150 bit 而第二分量m有 300 bit,短向量的判据被第一分量主导,m可能被约成非明文值;乘2^150让两者平衡,是把「数值大小」对齐到「格的几何长度」的标准做法。
触发条件
- 给出
g(素数或大整数)与data = t·m^{-1} mod g; - 未知乘子
t与明文m的比特长度之和明显小于g(本卡150 + ~300 < 512),目标向量相对格基足够短; m与g互素(否则invert不存在,题目不会这样出)。
利用步骤
- 估计
t的位长n(由生成脚本getPrime(n)得知,本卡 150)。 - 构造
M = matrix(ZZ, [[g << n, 0], [data << n, 1]])。 M.LLL(),检查返回向量的两个分量:第一分量应能被2^n整除,第二分量绝对值即m。- 对候选分量逐个
long_to_bytes并过滤可打印/含 flag 格式的结果。
PoC
from Crypto.Util.number import long_to_bytes
from sage.all import matrix, ZZ
g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547
data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498
n = 150 # t 的位长
M = matrix(ZZ, [[g << n, 0], [data << n, 1]]).LLL()
for row in M:
for v in row:
b = long_to_bytes(int(abs(v)))
if b.isprintable():
print(b)
变体与关联
- 变体:
data = t·m^{-1} mod g中t未知且较长时,可改成三维格加入t的界,或用gcd(data·m - t, g)反推。 - 变体:
data = (a·m + b) mod g(线性同余)时,用二维格[[g,0],[a,1]]直接求短向量(HNP 的最简形式)。 - 关联:[[ctf-crypto-hnp-2h-continued-fraction-kannan-embedding]](HNP 的连分数/Kannan 嵌入)、[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](Kannan 嵌入求短向量)。
- 边界:
t、m都接近g的位长时目标向量不再显著短于格基,LLL 无法保证约出;此时需要更多样本(多组data)做联立。
检测与防御
- 检测(CTF 视角):看到形如
t * inverse(m, g) % g的密文生成,且t位长明显小于g,优先试二维格。 - 防御(实现视角):不要把「短随机数 × 明文的模逆」当加密;随机数需与模数同量级或做哈希绑定,否则本质上是可约减的短向量问题。