LLL 恢复高精度 sin 背后的整数角:m=arcsin(c)+2kπ 构造三维格,2^320 配平后约出明文整数 m
ctf/crypto · verified
一句话结论
当题目只给出一个高精度实数 c = sin(m)(例如精确到小数点后 1024 bit),而 m 是把 flag 转成的整数(约 2^320)时,利用 m = arcsin(c) + 2kπ 的周期性,把 [1,0,S]、[0,2^320,S*arcsin(c)]、[0,0,S*2π] 组成三维格做 LLL,短向量 (m, -2^320, ≈0) 会直接给出 m,long_to_bytes 即得 flag;S(示例 2^683)用于把实数关系分量放大到与整数分量同一竞争尺度。
原理
- 信息形态:
print(sin(m).n(1024))只泄露sin(m)的 1024 bit 小数,但m是整数且远小于2^1024。由sin(m) = c得m = arcsin(c) + 2kπ(或π - arcsin(c) + 2kπ,取决于象限),其中k是未知整数;arcsin(c)和π都能用同样精度算出。 - 目标短向量:对整数系数
(m, -1, -k)组合格基行
text
[1, 0, S]
[0, 2^320, S*arcsin(c)]
[0, 0, S*2π]
得到
text
(m, -2^320, S*(m - arcsin(c) - 2kπ))
第三分量因为 m = arcsin(c) + 2kπ 而接近 0;第一分量 m ≈ 2^320,第二分量正好 -2^320。三个分量同量级且都很小,构成格中的短向量。
- 为什么 LLL 能约出来:该三维格的行列式约为 2^320 * S * 2π。取 S = 2^683 时 det^(1/3) ≈ 2^335,明显大于目标向量范数 ≈ sqrt(m² + 2^640) ≈ 2^320.8,Hermite 界与 LLL 的近似因子都有余量;若 S 取太小(如 2^640),det^(1/3) 与目标范数几乎相等,规约结果不稳定。
- 参数配平:2^320 是对 flag 长度的假设(约 40 字节 → m < 2^320);S 越大,实数关系分量的权重越高、det 越大,目标向量相对越短,但过大会放大浮点误差。S = 2^683 是该题实测能稳定出解的值,换题要按 flag 长度和精度重新试。
- 精度要求:arcsin(c)、π 必须在约 1024 bit 精度下计算(RealField(1024),pi 也用高精度重建),否则 S*(m - arcsin(c) - 2kπ) 的残差会淹没短向量;1024 bit 精度下残差约 S*2^-1024 ≈ 2^-341,可忽略。
- 结果读取:LLL 输出第一行形如 (±m, ∓2^320, ≈0),取第一分量绝对值转字节即 flag;若不可打印,说明 m 落在 π - arcsin(c) 分支或 S/2^320 需调整。
触发条件
- 题目给出高精度
sin(m)(或cos(m)等周期函数值),精度显著高于秘密整数的位长。 m是整数且位长上界已知(如 flag 约 30~40 字节,m < 2^320)。- 能构造
m = arcsin(c) + 2kπ(或π - arcsin(c) + 2kπ)的整数关系,且k为整数。 - 有 SageMath/高精度实数与 LLL 环境。
利用步骤
- 读取
c的全部小数位,构造R = RealField(1024),计算asin = arcsin(R(c))、pi = R(pi)。 - 估计
m上界2^B(flag 40 字节取 B=320)。 - 选缩放
S = 2^s(示例 s=683),构造Matrix(QQ, [[1,0,S], [0,2^B,S*asin], [0,0,S*2*pi]])。 LLL(),取第一行第一分量绝对值作为候选m;long_to_bytes(int(m))检查是否可打印/含 flag 格式。- 若失败:换
π - asin分支、调整B/s(逐步增大S直到出解)、或提高RealField精度。 - 验证:把候选
m代回sin(m)与题目小数比较,确认前 1024 bit 一致。
PoC
from sage.all import *
from Crypto.Util.number import long_to_bytes
tmp = "-0.5763216138185318403737346358040179184476364123728865572799211128243702354488581188939012847259223762780574285919778334891033655170438095281317540535577851035632940469300832811280408518388896020483094512571194149462558073200869265861278472233179527377781153969581392345206909655605217731481771369571884721388" # 1024 位小数
R = RealField(1024)
c = R(tmp)
asin = arcsin(c)
pi = R(pi) # 高精度 π
S = 2**683
B = 2**320 # flag 约 40 字节,m < 2^320
L = Matrix(QQ, [[1, 0, S],
[0, B, S * asin],
[0, 0, S * 2 * pi]])
v = L.LLL()[0]
m = abs(int(v[0]))
print(long_to_bytes(m).decode())
输出为 flag{...} 形式的明文;若得到乱码,先试 π - arcsin(c) 分支或调整 S。
变体与关联
- 象限分支:一般
sin(m)=c有m = arcsin(c) + 2kπ与m = π - arcsin(c) + 2kπ两支,构造格时两条都要试;cos(m)对应arccos(c) + 2kπ/-arccos(c) + 2kπ。 - 其他高精度函数:
tan/arctan、根号、对数的十进制高精度输出也可建成“公开实数 + 未知整数 + 周期/代数关系”的格,思路相同。 - 与 cos/sin 线性关系卡的区别:[[ctf-crypto-lll-trig-integer-relation]] 处理的是
enc ≈ a*cos(x)+b*sin(x)、未知的是小整数系数 a,b;本卡处理的是未知角度m本身,需要arcsin + 2πk的周期关系和2^320配平,构造与读取方式不同。 - 精度不足:若小数位数低于秘密位长,短向量不再唯一,需要更多信息或无法恢复。
- 关联:[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](一般短向量嵌入)、[[ctf-crypto-lll-linear-congruence-two-small-unknowns-2d]](二维模线性同余格)。
检测与防御
- CTF 识别:看到
sin(m).n(1024)、cos、高精度根号/对数与整数密文组合,优先估计秘密位长并尝试高精度实数格。 - 设计视角:不要把高精度三角函数值直接当“单向承诺”保护整数秘密;一旦精度高于秘密熵,
arcsin + 2kπ就能反解。 - 加固:只泄露远低于秘密熵的精度,或对机密整数加随机偏移后再取函数值;如需承诺,应使用哈希/同余等抗反解结构。