王念平，洪礼荣

（信息工程大学密码工程学院，河南 郑州 450001）

1 引言

线性密码分析是Matsui[1]在1993 年欧洲密码年会上提出的一种针对迭代型分组密码的已知明文攻击方法，其基本思想是利用分组密码算法中明文、密文和密钥之间的不平衡线性逼近来恢复某些密钥比特。对分组密码而言，线性密码分析经过不断的丰富与发展，已成为最有效的密码分析方法之一。因此，评估分组密码抵抗这一攻击的能力是分组密码设计中必须考虑的问题。

在对分组密码抵抗线性密码分析的能力进行评估时，通常的做法是估计多轮线性逼近中活动轮函数（即输出线性逼近非零的轮函数）或活动S 盒（即输出线性逼近非零的S 盒）个数的下界，进而给出最大线性逼近概率的上界。如果该上界足够小，就可以认为分组密码具有较强的抵抗线性密码分析的能力。因此，活动轮函数或活动S 盒的个数是评估分组密码抵抗线性密码分析能力的重要指标。

MARS 密码结构[2-4（]如图1 所示）是一种典型的密码结构，例如 AES（advanced encryption standard）竞赛的5 个最终候选算法之一的MARS[2]就采用了这样的结构。针对MARS 密码结构，人们进行了深入的研究。文献[3]研究了MARS 密码结构的随机性。文献[5-7]对MARS 密码结构或嵌套代替−置换网络（SPN,substitution-permutation network）的MARS 密码结构抵抗线性密码分析的能力进行了详细的分析。文献[8]利用不可能差分归一化（UID,unified impossible differential）方法找到了广义MARS 密码结构的11 轮不可能差分。文献[9]研究了类MARS 密码结构的不可能差分，证明了n分支类MARS 密码结构存在3n− 1轮不可能差分，且当n是奇数时，任意轮结构均存在不可能差分。……