李 平， 孙 兵， 李瑞林， 李 超

（国防科技大学 数学与系统科学系，湖南 长沙 410073）

0 引言

分组密码的设计主要关注两方面的性能，第一是算法本身的安全性，第二是算法的软硬件实现效率。大多数分组密码均采用SP轮函数的结构，文献[1]研究了分组密码S盒输出分量函数的密码学性质，文献[2]研究了一类P置换的设计方法。P置换要实现尽可能高的扩散性以抵抗差分线性等密码攻击手段，需要线性变换的分支数尽可能高。对合性质能够使得加解密完全一致，达到节省资源提高效率的目的。目前 AES，Camellia，FOX，SMS4等算法都使用了达到最优分支数的线性变换，分支数均为5，但都不是对合的。为了能够像Feistel型分组密码一样做到加解密一致，在扩散层中采用对合型线性变换就非常必要，目前韩国密码标准ARIA算法就采用了一个对合的线性变换作为其扩散层，并且分支数达到了最优。

基于以上优点，设计尽可能好的分支数以及对合的线性变换是近来的热点问题。由于异或运算和循环移位易于实现，结合这两种技巧来设计线性变换的方法逐渐得到广泛的应用。中国设计的无线局域网中使用的SMS4算法就是采用这种方法设计的扩散层[3]。现在已有的研究基础上，给出了三类达到次最优分支数的对合型线性变换的构造。

1 基础知识

下面给出给出线性变换分支数以及对合的定义：

B(L)=mX≠in0(W （X ) + W(L ( X)))。

根据分支数的定义，可知， B (L)≤ m+1。特别地，当B ( L ) = m+1时，称该线性变换为最优线性变换；当 B ( L) = m时，称该线性变换为次最优线性变换。

现有的构造最优线性变换的方法包括如下一些方法：

①循环矩阵构造[4]，AES算法扩散层基于该方法设计。文献[4]指出，与一般的随机矩阵相比，循环矩阵所对应的线性变换达到最优的概率更大。文献[2]进一步指出，如果还要求变换为对合变换，则这样的对合型线性变换的分支数最大只能达到4；

②组合方法构造[5]，FOX算法扩散层基于该方法设计；

③Hadamard矩阵构造，NESSIE计划中提交的分组密码算法Khazad[6]与Anubis[7]的扩散层基于该方法设计；

④Cauchy矩阵构造[8]。

除这几种常见的构造方法之外，利用循环移位和异或运算也可以构造分支数达到最优的线性变换。假设，用Xi表示将X循环左移i位，其中0 ≤ i≤ n m-1，则利用循环移位和异或运算可以表示从的一类线性变换。文献[9]给出了利用循环移位和异或运算设计最优线性变换时的一些条件这种方法特别适合于软硬件的实现，效率高。但是，已有的基于该构造方法给出的最优线性变换均不是对合变换。

2 三种构造次最优对合线性变换的方法

上一节中基于循环移位结合异或运算的方法均是将X视为整体进行循环移位和异或运算，对X的分量进行考虑，当 4m= 时，给出分支数达到4时的对合线性变换的三种构造方法。

证明：根据分支数的定义，必要性显然。

下面证明充分性，根据分支数的定义，只需按输入X的重量来分别讨论：

首先根据条件输入向量满足 W (X)= 1，则输出向量满足W(Y)≥ 3 ；

当输入向量满足 W (X) = 2 时，假设此时输出 Y =L(X)的重量 W (Y)= 1 。由于L是对合的，可考虑其逆变换L-1=L，由已知条件可知 X =L-1(Y)的重量 W (X)≥ 3。与W(X) = 2 矛盾，故输出 Y =L( X)的重量 W (Y)≥ 2 ；

当输入向量满足 W (X) = 3 时，由于输出是非零的，那么必有 W (Y)≥ 1。

综合以上3种情况，可知 B (L)≥ 4。

则线性变换L满足对合性质且分支数为 B ( L ) = 4。

证明：首先证明L的对合性，由L的定义：Y0⊕Y1⊕Y2⊕ Y3=X0⊕X1⊕X2⊕ X3， 故 T = ( X0⊕ X1⊕X2⊕ X3)i = (Y0⊕Y1⊕Y2⊕Y3)i ,又易知：

从而L为对合变换。

下面证明L的分支数为4，不妨设输入 X = ( X0,0,0,0)，X0≠ 0 ，则容易计算：

可知， Y1≠0, Y2≠0, Y3≠ 0 ，故 W (Y)≥ 3；又由于L是对合的，由定理 1可知 B (L)≥ 4。另一方面，可设输入X=(X0,0,0,0)中的 X0为全1向量，将其代入L的定义验证可知，输出 Y =L( X)的重量 W (Y)= 3 ，由分支数定义，取所有可能的输入输出重量之和的最小值，故分支数为4。

则线性变换L满足对合性质且分支数为 B ( L) = 4。

证明：首先证明L的对合性，由L的定义，可做如下循环移位：并计算 Y0⊕(Y1i1) ⊕(Y2i2) ⊕ (Y3i3) ⊕ (Y0i4)可得:

X0= Y0⊕ ( Y1i1) ⊕ ( Y2i2) ⊕ ( Y33) ⊕ (Y0i4)，同理可得：

从而L为对合变换。类似构造1的证明可知L的分支数为4。

则线性变换L的分支数为 B ( L) = 4，进一步，当n为偶数且i = n /2时，L是对合变换。

证明：首先证明L分支数为4，根据分支数的定义，只需按输入X的重量来分别讨论：

（1）当输入X的重量 W (X)= 1时，输出 Y =L ( X)的重量 W (Y)≥ 3；

不妨设输入 X = ( X0,0,0,0)， X0≠ 0 ，则容易计算：

可知， Y1≠ 0 , Y2≠0, Y3≠ 0 ，故 W (Y)≥ 3 。

（2）当输入X的重量 W (X) = 2 时，输出 Y =L ( X)的重量 W (Y)≥ 2 ；

不妨设输入 X = ( X0, X1,0,0), X0≠0, X1≠0,则容易计算:

若 X0⊕X1=0，则Y0≠0, Y1≠0，此时W(Y)= 2 ；若X0⊕X1≠0，则Y2≠0, Y3≠0，此时W(Y)≥ 2 。从而当W(X) = 2 时， W (Y)≥ 2 。

当输入X的重量 W (X)= 3 时，输出非零，所以必有W(Y)≥ 1；综上并且注意到（2）中存在输出 W (Y)=2的情况，由于分支数的定义，故 B ( L ) = 4。

下面证明当n为偶数且 i = n /2时，L是对合的：由Y0⊕Y1⊕Y2⊕ Y3= ( X0⊕X1⊕ X2⊕X3)i ,故 T = X0⊕ X1⊕X2⊕ X3=( Y0⊕Y1⊕Y2⊕Y3)■ i ，则：

令T'= Y0⊕Y1⊕Y2⊕Y3，则 Ti =T '2 i，从而：

当n为偶数且 /2i n= 时，有2i n= ，此时：

故：

这表明L为对合变换。

3 结语

介绍了分支数较好的对合型线性变换在密码算法中的重要作用，以及主要的构造方法。研究了如何利用循环移位和异或运算构造从的线性变换，使得分支数达到次最优，并且是对合的。给出了三种具体的构造方法，并分别给出了证明。进一步需要研究，在利用这几类线性变换作为扩散层组件时，密码算法是否能够有效地抵抗各种密码分析方法，尤其是截断差分密码分析。同时，利用提出的设计方法能否找到分支数达到最优的线性变换也是下一步继续研究的课题。

[1] 李强,李超.Camellia算法中S盒输出分量函数的等价表示[J].通信技术,2008,41(11)：126-128．

[2] 王念平,金晨辉,余昭平.对合型列混合变换的研究[J].电子学报,2005,33(10)：1917-1920．

[3] 国家商用密码管理办公室．无线局域网产品使用的 SMS4密码算法[EB/OL].(2005-02-05).[2010-01-10].http：//www.oscca.gov.cn/UpFile/200621016423197990.pdf.

[4] DAEMEN J, KNUDSEN L R, RIJMEN V. The Block Cipher Square[C]//FSE 1997, LNCS 1267. Springer-Verlag, Berlin, 1997： 149-165.

[5] PASCAL J, SERGE V. Pergect Diffusion Primitives for Block Ciphers Building Efficient MDS Matrices[C]// SAC 2004, LNCS 3357. Berlin：Springer-Verlag,2005： 84-99.

[6] BARRETO P, RIJMEN V. The Khazad Legacy-level Block Cipher[EB/OL]. (2000-11-13) [2010-01-10]. http：//www.crypt onessie.org.

[7] BARRETO P, RIJMEN V.The Anubis Block Cipher[EB/OL].(2000-11-13).[2010-01-10]. http：//www.cryptonessie.org.

[8] WILLIAMS F M, SLOANE N. The Theory of Error-Correcting Codes[M].Holland：North-Holland Pub. Co.,1977.

[9] 王金波.基于循环移位构造最优线性变换[C]//密码学进展——中国密码学会 2007年会论文集.成都：西南交通大学出版社,2007：306-307.