如何从截断LCG方程中提取格攻击所需的基？

针对你给出的模2^32线性同余生成器（LCG），已知连续5个状态的最低有效字节（LSB），以下是构造格基并通过最短向量求解完整状态的具体步骤：

1. 整理LCG递推关系与约束条件 #

首先明确LCG的递推式（模2^{32，允许整数层面差2}32的倍数）：

k1 = const*(k0+x1) + 1 - m1*2^32
k2 = const*(k1+x2) + 1 - m2*2^32
k3 = const*(k2+x3) + 1 - m3*2^32
k4 = const*(k3+x4) + 1 - m4*2^32

其中m1~m4为0或1（因k_i是32位无符号整数，递推计算结果超出2^{32时需减去一次2}32）。

已知每个k_i的LSB：k_i ≡ b_i mod 256（b0=0x59, b1=0x32, b2=0x89, b3=0x45, b4=0x61），因此可令k_i = 256*q_i + b_i，其中q_i为0≤q_i<2^24的整数（k_i是32位，高24位为q_i）。

2. 转化为线性整数方程 #

将k_i = 256*q_i + b_i代入递推式，整理后两边除以256，得到关于q0（k0的高24位）和m1~m4的线性方程：
对于i=1~4：

q_i = const^i * q0 + C_i - 2^24 * M_i

其中：

• C_i = (const^i * b0 + S_i - b_i) / 256，S_i是递推常数项的累加和（如S1=const*x1+1，S2=const*(S1+x2)+1等），因LSB约束保证分子是256的倍数，C_i为整数；
• M_i是m1~mi的线性组合（如M1=m1，M2=const*m1 + m2，以此类推）。

将方程移项为齐次形式：

q_i - const^i * q0 + 2^24 * M_i = C_i

3. 构造格基矩阵 #

我们构造9×9的整数矩阵，每行对应一个约束或变量范围限制：

简化版矩阵（忽略m_i） #

如果先假设m1~m4=0（即递推结果未超出2^32），可简化为5×5矩阵：

[ -const, 1, 0, 0, 0 ]
[ -const², 0, 1, 0, 0 ]
[ -const³, 0, 0, 1, 0 ]
[ -const⁴, 0, 0, 0, 1 ]
[ 2^24, 0, 0, 0, 0 ]

4. 求解最短向量 #

目标向量为[q0,q1,q2,q3,q4,m1,m2,m3,m4]（或简化版的[q0,q1,q2,q3,q4]），该向量满足所有约束，且因q_i<2^24、m_i∈{0,1}，其欧几里得范数远小于格中其他向量。

使用LLL算法求解格的最短向量，得到结果后：

1. 计算k_i=256*q_i +b_i；
2. 验证是否符合LCG递推式（模2^32）；
3. 若不符合，重新考虑m_i的取值（可调整格矩阵加入m_i的可能取值组合）。

内容的提问来源于stack exchange，提问作者Frank Mathews