线性密码分析与近似表

线性密码分析（Matsui，1993 年）是一种已知明文攻击，用于找出以概率 p ≠ 1/2 成立的密码线性近似（特定位的 XOR）。通过使用大量明文—密文对，统计偏差可以揭示密钥位。

S 盒的线性近似是指：选定输入位的和 XOR 选定输出位的和 = 0 (mod 2)，其成立概率为 p。可表示为：P[a·x XOR b·y = 0] = 1/2 + ε，其中 a、b 是位掩码，ε 是偏差（|ε| >> 0 较为理想）。

LAT 统计：对于每个输入掩码 a 和输出掩码 b，满足 (a·x) XOR (b·S(x)) = 0 的输入 x 的数量。减去 2^{n-1} 即可得到偏差。优秀的 S 盒具有 |max_bias| = 1（概率为 1/2 ± 1/2^{n/2}），也就是尽可能平坦。

对于通过多轮的相互独立的线性近似，偏差会相乘：ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r。每轮近似都会使有效偏差减半。经过多轮后，总偏差趋近于 0，因此需要指数级更多的明文对才能检测到它。

要攻击 r 轮密码，请找出贯穿前 r-1 轮的线性路径 ε。收集 N = 1/ε^2 个已知明文。对于每个候选的最后一轮密钥字节 k'，通过 XOR 部分解密最后一轮，并检查线性近似成立的次数是否超过 N/2。正确的 k' 会显示出正确的偏差。

Matsui 在 1993 年使用带有 2^{-21.4} 偏差的 14 轮线性近似攻击了 16 轮 DES。该攻击需要 2^{43} 个已知明文。在第一阶段恢复了 26 个密钥位，剩余 30 位则通过穷举搜索恢复。这是首次比针对完整 DES 的暴力破解更快的实际攻击。

高级加密标准的 S 盒每个 S 盒的最大 LAT 项为 |ε| = 4/256 = 1/64。宽轨策略将任何 4 轮路径中的活跃 S 盒数量限制为至少 25 个。总偏差 ≤ (1/64)^{25/2} ≈ 2^{-75}。这需要 2^{150} 个已知明文，在计算上不可行。

差分：已知或选择的明文对，利用输出差分。线性：已知明文，利用统计线性近似。在实际攻击中，两者都可采用选择明文。两者也是设计标准：S 盒必须同时抵抗两者（DDT 最大值低 AND LAT 最大值低）。

同时使用多个线性近似，以降低数据复杂度。Nyberg 和 Leander 扩展了 Matsui 的方法：组合 M 个近似可以将所需数据量减少 log(M) 倍。该方法已应用于 PRESENT、SIMON 及其他轻量级密码。

将线性近似应用于流密码：找出密钥流与 LFSR 输出的某个线性函数之间的相关性。如果相关性不为零，就可以比穷举更快地恢复密钥。这启发了流密码中非线性组合函数的设计。

积分密码分析（Knudsen-Wagner）：选择一组明文，使某些字节取遍全部 256 个值，而其他字节保持不变。经过若干轮后，某些位置的所有输出执行 XOR 后为 0（处于平衡状态）。该方法利用高级加密标准的结构，可以高效破解缩减轮数的高级加密标准。

叠加引理对组合线性近似有什么表述？

线性密码分析找出 S 盒中带有偏差的线性近似。高级加密标准通过 LAT 最优的 S 盒和宽轨设计抵抗这种攻击。Matsui 使用一条 14 轮路径和 2^43 个已知明文破解了 DES。下一节：生日攻击和碰撞查找。