密码学/线性密码分析

在密码学中，线性密码分析是一种通用的密码分析形式，它基于寻找对密码动作的仿射近似。已针对分组密码和流密码开发了攻击方法。线性密码分析是两种最常用的分组密码攻击之一；另一种是差分密码分析。

该发现归功于松井充，他首先将该技术应用于 FEAL 密码（松井和山岸，1992）。随后，松井发表了对数据加密标准 (DES) 的攻击，最终导致了在公开社区中报告的第一个对该密码的实验性密码分析（松井，1993；1994）。对 DES 的攻击通常不切实际，需要 2⁴³ 个已知明文。

已经提出了对该攻击的各种改进，包括使用多个线性近似或合并非线性表达式，从而导致广义的划分密码分析。新的密码设计通常需要针对线性密码分析的安全性证据。

概述

线性密码分析有两个部分。第一部分是构建将明文、密文和密钥位相关联的线性方程，这些方程具有高偏差；也就是说，它们的保持概率（在所有可能的值空间中）尽可能接近 0 或 1。第二部分是将这些线性方程与已知的明文-密文对结合起来推导出密钥位。

构建线性方程

为了进行线性密码分析，线性方程表示两个表达式的相等性，这些表达式由二进制变量与异或 (XOR) 运算组合而成。例如，以下来自假设密码的方程指出，第一个和第三个明文位的 XOR 和（如分组密码的块中）与第一个密文位相等，等于密钥的第二位

$P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.$

在理想密码中，任何将明文、密文和密钥位相关联的线性方程的保持概率都将为 1/2。由于线性密码分析中处理的方程在概率上会有所不同，因此更准确地将它们称为线性近似。

构建近似的过程对于每个密码都是不同的。在最基本类型的分组密码（替换-置换网络）中，分析主要集中在 S 盒上，这是密码中唯一非线性的部分（即，S 盒的操作无法用线性方程表示）。对于足够小的 S 盒，可以枚举将 S 盒的输入和输出位相关联的每个可能的线性方程，计算它们的偏差并选择最佳方程。然后，必须将 S 盒的线性近似与密码的其他动作（如置换和密钥混合）结合起来，以得出整个密码的线性近似。堆积引理是这种组合步骤的有用工具。还有一些技术可以迭代地改进线性近似（松井 1994）。

推导出密钥位

在获得以下形式的线性近似后

$P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots$

然后，我们可以应用一个简单的算法（松井算法 2），使用已知的明文-密文对来猜测参与近似的密钥位的取值。

对于右侧密钥位值的每一组（称为部分密钥），统计近似在所有已知的明文-密文对上保持成立的次数；将此计数称为T。T 与明文-密文对数量的一半的绝对差值最大的部分密钥被指定为这些密钥位的最可能取值集。这是因为假设正确的部分密钥将导致近似以高偏差保持成立。偏差的大小在这里很重要，而不是概率本身的大小。

该过程可以使用其他线性近似重复执行，以获得对密钥位取值的猜测，直到未知密钥位的数量足够低，可以使用暴力破解进行攻击。

参考文献

• 松井，M. 和山岸，A. "一种对 FEAL 密码进行已知明文攻击的新方法"。密码学进展 - EUROCRYPT 1992。 
• 松井，M. "DES 密码的线性密码分析方法" (PDF)。密码学进展 - EUROCRYPT 1993。已从 原始位置 归档于 2006-04-10. http://web.archive.org/web/20060410133750/http://homes.esat.kuleuven.be/~abiryuko/Cryptan/matsui_des.PDF. 检索于 2007-02-22. 
• 松井，M. "数据加密标准的第一个实验性密码分析"。密码学进展 - CRYPTO 1994。