能否对LCG变体方程实施格攻击？计算优化咨询

问题明确 #

给定32位模运算方程：
$$k_i = ((k_{i-1} + x_i) \times CONST + 1) \mod 2^{32}$$
已知条件：

• $k_i$ 和 $k_{i-1}$ 的最高字节（首字节）
• $x_i$ 为单字节（8位）变量
• 其余变量均为32位，运算模 $2^{32}$

当前通过暴力枚举（65536*2*2次计算）求解，计算量过高，需优化或采用格攻击方法。

数学推导优化计算量 #

先对原方程做模逆变形：
$$k_{i-1} + x_i = (k_i - 1) \times CONST^{-1} \mod 2^{32}$$
记 $C = CONST^{-1} \mod 2^{32}$（预计算固定逆元），$D = (k_i - 1) \times C \mod 2^{32}$，则：
$$k_{i-1} = D - x_i \mod 2^{32}$$

拆分变量为已知最高字节+未知低字节：

• $k_i = MSB_i \times 2^{24} + LSB_i$（$MSB_i$ 已知，$LSB_i$ 为24位未知值）
• $k_{i-1} = MSB_{i-1} \times 2^{24} + LSB_{i-1}$（$MSB_{i-1}$ 已知，$LSB_{i-1}$ 为24位未知值）
• $x_i \in [0, 255]$

代入后重点约束最高字节：
计算基准值 $Base = (MSB_i \times 2^{24} - 1) \times C \mod 2^{32}$，提取其最高字节 $Base_{MSB}$。$LSB_i \times C$ 会产生0~3字节的进位到最高位，结合 $x_i$ 的8位范围，最高字节需满足：
$$MSB_{i-1} = (Base_{MSB} + carry - x_i) \mod 256$$
由此可反推 $carry$ 的可能范围，进而将 $LSB_i$ 的24位枚举（16777216次）压缩至最多几百次，大幅降低计算量。

格攻击构建思路 #

该问题可转化为小整数解的线性同余问题，适合用LLL格约简算法求解：

1. 构建线性方程 #

从原方程推导得：
$$k_i - CONST \times k_{i-1} = CONST \times x_i + 1 + 2^{32} \times d$$
其中 $d$ 为整数（模运算进位）。代入变量拆分形式：
$$a - CONST \times b - CONST \times c - 2^{32} \times d = CONST \times MSB_{i-1} \times 2^{24} - MSB_i \times 2^{24} + 1$$
（$a=LSB_i, b=LSB_{i-1}, c=x_i$，均为小范围未知整数）

2. 构建格基矩阵 #

构建4维格的基矩阵，目标是让满足条件的解对应格中的短向量：
$$
\begin{pmatrix}
1 & 0 & 0 & 0 \
0 & CONST & 0 & 2^{32} \
0 & 0 & CONST & 0 \
K & 0 & 0 & 1
\end{pmatrix}
$$
其中 $K = CONST \times MSB_{i-1} \times 2^{24} - MSB_i \times 2^{24} + 1$

3. LLL约简求解 #

用LLL算法对格基约简，约简后的短向量对应符合条件的 $(a,b,c,d)$，直接得到 $k_i$ 和 $k_{i-1}$ 的完整值，无需暴力枚举。

现有代码优化点 #

针对提供的C代码，可从以下方向减少计算量：

• 预过滤无效组合：计算 temp2 后，若其最高字节与 MSBiminus1 的差值超出 $x_i$ 能覆盖的范围（0~255），直接跳过当前 i,j 组合，无需进入内层循环。
• 合并枚举维度：通过最高字节约束直接推导满足条件的 i,j（中间字节）组合，避免全量枚举256*256次。
• 精简内层循环：基于数学推导缩小 diff 的可能取值范围，减少 t 和 k 循环的执行次数。

内容的提问来源于stack exchange，提问作者terry franklin