分组密码是一类重要且应用广泛的对称密码体制.从分组密码算法的设计模型来说,分组密码算法的设计模型主要分为:以DES算法^[1]为代表的Feistel模型、以CAST-256算法^[2]和SMS4算法^[3]为代表的不平衡Feistel模型、以Rijndael算法^[4]为代表的SP模型及以IDEA算法^[5]为代表的Lai-Massey模型等.SP模型是目前广泛使用的分组密码结构之一,很多著名的密码算法都采用这种结构,如AES算法^[4]、ARIA算法^[6]、Serpent算法^[7]和SAFER算法^[8]等.

差分分析和线性分析是两种对分组密码算法进行分析的最基本的手段.为了使SP模型更好地抵抗差分分析和线性分析,密码设计者希望构造差分分支数及线性分支数以尽可能大地扩散结构,从而增加差分及线性路径中活动S盒的个数.MDS矩阵的差分和线性分支数均达到了最大值^[9],故,利用MDS矩阵来构造分组密码的扩散结构是一种重要的方法,国内外的密码学者都对MDS矩阵的构造与密码特性进行了大量的研究^{[10, 11, 12, 13, 14, 15, 16]}.

本文研究了SPS模型差分概率上界的估计问题.在该问题的研究中,2000年,Hong等人在文献^[17]中证明:

当P变换的分支数达到最大值m+1时,2轮SP网络差分概率的上界为$p_{\max }^m;$当P变换的分支数达到次大值m时,2轮SP网络差分概率的上界为$p_{\max }^{m - 1}.$2001年,Kang等人在文献^[9]中证明了2轮SP网络差分概率的上界为$p_{\max }^{{B_d} - 1},$从而推广了Hong等人的结论,并据此给出了2轮AES算法的差分概率的上界为2^-24.2002年,Park等人

对类Rijndael结构的差分概率的上界进行了研究^[18],指出,4轮类Rijndael结构差分概率的上界为1.06x2^-96.2003年,Park等人给出了2轮SP网络差分概率上界的估计公式^[19],该上界是SPS模型迄今最紧的上界.对SPS模型差分概率的上界进行理论估计,可为SP网络、嵌套SP的Feistel结构等密码模型的可证明安全性提供理论支撑.在文献^[20] 中,Choy等人利用Park给出的关于SPS模型差分概率上界的结论,给出了E2算法及MCrypton算法抵抗飞来去器^[21]攻击的安全性.此外,针对SP网络的分组算法ARIA,文献^[22]对该算法差分概率进行了研究.Shirai等人对嵌套SP结构的Feistel模型的差分概率的上界进行了研究^[23],并指出,10轮Camellia差分概率不会大于2^-128.

针对P盒为n-MDS矩阵对应的仿射变换构造的扩散结构,本文给出了该类SPS模型差分概率的一个新上界.当SPS模型中的S盒均为仿射等价时,该上界等于Park等人给出的上界;当S盒是独立S盒时,我们的模拟实验结果说明,该上界一般比Park等人给出的上界更紧,从而说明使用独立的S盒可能获得比使用相同S盒获得更好的抗差分攻击的能力.

1 SPS模型的简化

定义1. 设S_i→{0,1}ⁿ→{0,1}ⁿ是双射,S:[Z/(2ⁿ)]^m→[Z/(2ⁿ)]^m,使任意的(x₁,…,x_m)∈[Z/(2ⁿ)]^m,有S(x₁,…,x_m)= (S₁(x₁),…,S₁(x_m)).再设P:{0,1}^mn→{0,1}^mn是二元域上的仿射双射,则称由S盒、P盒、与密钥逐位模2加及S盒这4个变换复合的模型为SPS模型.

在分组密码中,S盒有时设计为非线性变换与仿射变换的复合,如AES算法中的S盒.对于这类S盒构成的SPS模型,我们可将S盒中的仿射变换与扩散结构P看作一个整体,从而构成一个新的扩散结构P_new.引理1给出了具体的约简关系.

引理1. 设S_i:{0,1}ⁿ→{0,1}ⁿ是双射,S:[Z/(2ⁿ)]^m→[Z/(2ⁿ)]^m使任意的(x₁,…,x_n)∈[Z/(2ⁿ)]^m,有S(x₁,…,x_m)= (S₁(x₁),…,S₁(x_m)),且P:{0,1}^mn→{0,1}^mn是二元域上的仿射双射.再设T_i:{0,1}ⁿ →{0,1}ⁿ且存在仿射双射j_i,y_i:{0,1}ⁿ→{0,1}ⁿ使S_i(x)=ψ_i(T_i(ϕ_i(x))),定义ϕ=(ϕ₁,…,ϕ_m),ψ=(ψ₁,…,ψ_m),T=(T₁,…,T_m),P_new:{0,1}^mn→{0,1}^mn使P_new(x)=ϕoPoψ(x),则有:

S(PS(x)⊕k)=ψT(P_newTϕ(x)⊕ϕ(k)⊕ϕ(0)).

引理1说明采用扩散结构为P、混淆层设计为T(x)=ψ(S(ϕ(x)))的TPT模型,其差分概率的取值分布规律与采用扩散结构P_new(x)=ϕ(P(ψ(x)))、混淆层为S(x₁,…,x_m)=(S₁(x₁),…,S₁(x_m))的SP_newS模型的差分概率的取值分布规律相同,故下面只需研究SP_newS的差分概率规律即可.例如:对于S盒为有限域上的仿射变换与仿射变换复合构成的SPS模型,我们只需假设S盒是有限域上的逆变换即可.即使P是GF(2ⁿ)上的线性变换,但j_i和y_i可能只是二元域上的仿射变换而不是GF(2ⁿ)上的仿射变换,故P_new可能是二元域上的仿射变换而不是GF(2ⁿ)上的线性变换.因此,我们通常假设SP_newS模型中的P盒P_new是二元域上的仿射变换,这说明定义1中对扩散结构P的定义具有一般性.

定义2^[21]. 设函数f:{0,1}^u→{0,1}^v,α∈{0,1}^u,β∈{0,1}^v,则称p_f(α→β)=#{x∈{0,1}^u:f(x)⊕f(x⊕α)=β}/2^u为f的差分对应α→β的差分概率,其中,#表示集合中元素的个数.

定义3. 设f:{0,1}^mn→{0,1}^mn是仿射变换,α,β∈{0,1}^mn,则称$DB_f^{(n)} = \mathop {\min }\limits_{\alpha \ne 0} \{ w{t_n}(\alpha ) + w{t_n}(f(\alpha ))\} $为f的n-差分分支数.这里,wt_n(α)是α=(α₁,…,a_m)中非零的n比特块的个数.

定义4. 设f:{0,1}^mn→{0,1}^mn是仿射变换且f(x)=Ax⊕f(0),当f的n-差分分支数达到最大值m+1时,则称f对应的变换矩阵A为n分块MDS矩阵,简记为n-MDS矩阵.

在本文中,在不引起歧义时,我们简称n-差分分支数为n-分支数.

2 预备知识

以下均假设所研究的SPS模型是定义1所定义的SPS模型,且其中的S盒都是有限域GF(2ⁿ)上的逆变换,P是{0,1}^mn到自身的仿射变换.

引理2. 设f(x)=Ax⊕f(0),A是mnxmn二元矩阵,E是mn级单位方阵.再设A||E=A₁||…||A_2m且诸A_i是mnxn矩阵,则矩阵A的n-差分分支数≥d的充要条件为A₁,…,A_2m中任意d-1个矩阵的列向量全体构成的向量组均线性无关.

证明:

· 充分性

若A||E的任意d-1个n-分块列在二元域上线性无关,则A||E中至少d个n-分块列在二元域上才可能线性相关,从而任何重量小于d的向量(X,Y)^T都不能使(A||E)(X,Y )^T=0成立,即,A的n-差分分支数≥d.

· 必要性

若矩阵A的n-差分分支数≥d,则对任意非零的X,Y∈[Z/(2ⁿ)]^m,wt_n(X)+wt_n(Y)的最小值为d,其中Y=AX.若A||E存在d-1个n-分块列在二元域上线性相关,不妨设第t₁,t₂,…,t_d-1个n-分块列线性相关,将这些n-分块列依次记为z₁,z₂,…,z_d-1,则存在d-1个n维0-1列向量c₁,c₂,…,c_d-1∈Z/(2ⁿ)使得c₁·z₁⊕c₂·z₂⊕…⊕c_d-1·z_d-1=0成立,其中,运算“·”为c·z=c¹·z¹⊕c²·z²⊕…⊕cⁿ·zⁿ,c=(c¹,c²,…,cⁿ)∈Z/(2ⁿ),z为一个n-分块列,zⁱ表示0-1块z的第i列.cⁱzⁱ表示cⁱ与zⁱ作数乘运算.

现构造2mn维列向量${(X',Y')^T} = {(0,...,0,c_1^T,0,...,0,c_2^T,0,...,0,c_{d - 1}^T,0,...,0)^T}$,其中,诸c_i及零元素均为n维0-1列向量,且$c_i^T$为(X′,Y′)^T中的第t_i个n维向量,i=1,2,…,d-1,则有:

(A||E)(X′,Y′)^T=c₁·z₁⊕c₂·z₂⊕…⊕c_d-1·z_d-1=0.

此时,由A||E中存在d-1个n-分块列在二元域上线性相关的假设,构造了向量重量wt_n(X′)+wt_n(Y′)为d-1的X′,Y′∈[Z/(2ⁿ)]^m,这与A的n-差分分支数≥d矛盾,故必要性成立.

定理1. 设mn级二元矩阵P是n-MDS矩阵,t₁,t₂,…,t_2m是1,2,…,2m的一个排列,则有:

(1) 存在二元域上的m²个n级可逆方阵e_i,j,i,j=1,2,…,m,使得任意的X,Y∈[GF/(2ⁿ)]^m,Y=PX等价于对1≤ i≤m,均有${z_{{t_i}}} = \mathop \oplus \limits_{j = 1}^m {e_{i,j}}{z_{{t_{m + j}}}}.$这里,列向量z_i是X||Y的第i个坐标;

(2) 如果P是GF(2ⁿ)上的m级方阵,则存在GF(2ⁿ)上的非零元e_i,j,i,j=1,2,…,m,使得任意的X,Y∈[GF/(2ⁿ)]^m,Y=PX等价于对1≤i≤m,均有${z_{{t_i}}} = \mathop \oplus \limits_{j = 1}^m {e_{i,j}}{z_{{t_{m + j}}}},$这里,列向量z_i是X||Y的第i个坐标.

证明:设P||E=h₁||…||h_2m且诸h_i都是mnxn二元矩阵,X,Y∈[GF/(2ⁿ)]^m,则Y=PX等价于(P||E)(X,Y)^T=0.由于z_i是Z=X||Y的第i坐标,故上式等价于$\mathop \oplus \limits_{i = 1}^{2m} {\eta _i}{z_i} = 0,$即$\mathop \oplus \limits_{j = 1}^m {\eta _{{t_j}}}{z_{{t_j}}} = \mathop \oplus \limits_{j = m + 1}^{2m} {\eta _{{t_j}}}{z_{{t_j}}},$亦即:

$({\eta _{{t_1}}},...,{\eta _{{t_m}}}){({z_{{t_1}}},...,{z_{{t_m}}})^T} = ({\eta _{{t_{m + 1}}}},...,{\eta _{{t_{2m}}}}){({z_{{t_{m + 1}}}},...,{z_{{t_{2m}}}})^T}.$

由P的n-分支数为m+1,故由引理2可知,矩阵$A = ({\eta _{{t_1}}},{\eta _{{t_2}}},...,{\eta _{{t_m}}})$是可逆矩阵,因而上式等价于:

${({z_{{t_1}}},...,{z_{{t_m}}})^T} = {A^{ - 1}}({\eta _{{t_1}}},...,{\eta _{{t_m}}}){({z_{{t_{m + 1}}}},...,{z_{{t_{2m}}}})^T} = ({A^{ - 1}}{\eta _{{t_1}}},...,{A^{ - 1}}{\eta _{{t_m}}}){({z_{{t_{m + 1}}}},...,{z_{{t_{2m}}}})^T}\mathop = \limits^{def} $ ${({e_{i,j}})_{m \times m}}{({z_{{t_{m + 1}}}},...,{z_{{t_{2m}}}})^T},$

其中,e_i,j是二元域上的n级方阵.这说明Y=PX等价于对1≤i≤m,均有${z_{{t_i}}} = \mathop \oplus \limits_{j = 1}^m {e_{i,j}}{z_{{t_{m + j}}}}$.下证诸e_i,j都是二元域上的可逆矩阵.

假设${e_{{i_0},{j_0}}}$不是二元域上的可逆矩阵,则存在c∈{0,1}ⁿ\{0},使得${e_{{i_0},{j_0}}}c = 0.$构造Z=(z₁,…,z_2m),使得对于

i∈{1,2,…,2m},有:

${z_{{t_i}}} = \left\{ {\begin{array}{*{20}{l}} {c,{\text{ }}i = m + {t_0}} \\ {0,{\text{ }}i > mi \ne m + {t_0}} \\ {{e_{i,{j_0}}}c,{\text{ }}1 \leqslant i \leqslant m} \end{array}} \right.,$

则1≤i≤m,均有${z_{{t_i}}} = \mathop \oplus \limits_{j = 1}^m {e_{i,j}}{z_{{t_{m + j}}}}.$令X,Y∈[GF/(2ⁿ)]^m,使得Z=X||ψ,则由已证结论可知ψ=PX.由于${e_{{i_0},{j_0}}}c = 0,$因而Z的非零块的个数≤m,这与P是n-MDS矩阵矛盾.该矛盾说明,诸e_i,j都是二元域上的可逆矩阵.

显然,当P是GF(2ⁿ)上的m级方阵时,诸h_i都是GF(2ⁿ)上的m维列向量,只需将m级矩阵与向量的乘法换为有限域GF(2ⁿ)上乘法,直接沿用上述证明即可证明后一结论.

由定理1的证明可知,矩阵(e_i,j)_mxm只与矩阵P和排列t₁,t₂,…,t_2m有关,故以下称定理1中,以n级可逆方阵e_i,j为元素的矩阵(e_i,j)_mxm为由矩阵P和排列t₁,t₂,…,t_2m决定的矩阵.

下面先给出排序定理的一个推广形式.

引理3^[24]. 设对1≤i≤m,均有0≤a_i,1≤a_i,2≤…≤a_i,n.如果对任意的i,b_i,1,b_i,2,…,b_i,n均是a_i,1,a_i,2,…,a_i,n的一个排列,则有$\sum\limits_{j = 1}^n {\prod\limits_{i = 1}^m {{b_{i,j}}} } \leqslant \sum\limits_{j = 1}^n {\prod\limits_{i = 1}^m {{a_{i,j}}} } .$再设${j_0} = \min \left\{ {j:\prod\limits_{i = 1}^m {{a_{i,j}}} > 0} \right\},$则上式等号成立的充要条件是:对任意的j≥j₀和任意的i,均有b_i,j=a_i,j.

3 给定差分对应的差分概率估计

当P是n-MDS矩阵构造的扩散变换时,下面我们将给出给定一个差分对应α→b时,其差分概率上界的估计问题.由于SPS模型的差分路径$\alpha \xrightarrow{{{S_{(1)}}}}A\xrightarrow{P}PA\xrightarrow{{{S_{(2)}}}}\beta $的概率为

${p_{{S_{(1)}}}}(\alpha \to A){p_{{S_{(2)}}}}(PA \to \beta ) = {p_{{S_{(1)}}}}(\alpha \to A){p_{S_{(2)}^{ - 1}}}(\beta \to PA),$

因而,SPS模型一条差分路径的概率分析可以转化为S变换${S_{(1)}}||S_{(2)}^{ - 1}$的一个差分对应$\alpha ||\beta \xrightarrow{{{S_{(1)}}||S_{(2)}^{ - 1}}}$A||PA的概 率分析,此时,叙述和研究起来更加简捷.

定理2. 设扩散变换P为n-MDS矩阵对应的仿射变换构造且P的分支数为m+1,α||β=(α₁,…,α_m,β₁,…,β_m)∈[Z/(2ⁿ)]^m\{0}.再设S_i在输入差为α_i时所有差分对应的概率从大到小依次为${p_{i,0}},...,{p_{i,{2^n} - 1}}$,S_i在输出差为b_i时所有差分对应的概率从大到小依次为${p_{m + i,0}},...,{p_{m + i,{2^n} - 1}}$,定义变换T=(T₁,T₂,…,T_2m),使得:

${T_i} = \left\{ {\begin{array}{*{20}{l}} {{S_i},{\text{ }}1 \leqslant i \leqslant m} \\ {S_i^{ - 1},{\text{ }}m + 1 \leqslant i \leqslant 2m} \end{array}} \right.,$

则有:

(1)${p_{SPS}}(\alpha \to \beta ) \leqslant \min $,$\Omega $是Λ的m+1元子集，其中,Λ是α||β的非零坐标构成的集合;

(2) 对1≤i≤2m,记r_i是S_i的能达到输入差为${\gamma _{{t_i}}}$时的最大差分概率的输出差的个数,wt_n(α)+wt_n(β)≥m+2,如果p_SPS(α→β)≠0且情形(1)中的等号成立,则存在α||β的非零坐标${\gamma _{{t_1}}},{\gamma _{{t_2}}},...,{\gamma _{{t_{m + 2}}}}$,使得:

$\# \{ \xi :{p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to \xi ) \ne 0\} \leqslant \min \{ 1 + C_{{r_i}}^2:1 \leqslant i \leqslant m + 1\} .$

证明:

(1) 设wt_n(α)+wt_n(β)≤m,则对任意的A,B∈[Z/(2ⁿ)]^m,由S是双射可知:当p_S(α→A)＞0时,有wt_n(A)=wt_n(α);当p_S(B→β)＞0时,有wt_n(B)=wt_n(β).因而:

wt_n(A)+wt_n(B)=wt_n(α)+wt_n(β)≤m.

再由α||β≠0可知A||B≠0,因而A≠0,从而由P的差分分支数为m+1可知B≠PA.

这说明B=PA蕴涵p_S(α→A)p_S(β→B)=0,故有:

${p_{SPS}}(\alpha \to \beta ) = \sum\limits_{A,B} {{p_S}(\alpha \to A){p_P}(A \to B){p_S}(B \to \beta )} = \sum\limits_{A \in {{[Z/({2^n})]}^m},B = PA} {{p_S}(\alpha \to A){p_S}(B \to \beta )} = 0.$

故,此时本定理成立.现设wt_n(α)+wt_n(β)≥m+1,定义T=(T₁,T₂,…,T_2m),使得:

${T_i} = \left\{ {\begin{array}{*{20}{l}} {{S_i},{\text{ }}1 \leqslant i \leqslant m} \\ {S_i^{ - 1},{\text{ }}m + 1 \leqslant i \leqslant 2m} \end{array}} \right..$

对任意的A∈[Z/(2ⁿ)]^m,令g=α||β,则有:

${p_{SPS}}(\alpha \to \beta ) = \sum\limits_{A \in {{[Z/({2^n})]}^m},B = PA} {\left( {\prod\limits_{i = 1}^m {{p_{{S_i}}}({\alpha _i} \to {A_i})} } \right)\left( {\prod\limits_{i = 1}^m {{p_{{S_i}}}({B_i} \to {\beta _i})} } \right)} = \sum\limits_{A \in {{[Z/({2^n})]}^m}} {{p_T}(\gamma \to A||PA)} .$

设${\gamma _{{t_1}}},{\gamma _{{t_2}}},...,{\gamma _{{t_{m + 1}}}}$都非零,即Ω={i₁,i₂,…,i_m+1}是(g₁,g₂,…,g_2m)的非零分量的坐标构成的集合Λ的一个m+1元子集.再设n级可逆方阵e_i,ϕ为元素的矩阵,(e_i,ϕ)_mxm为由矩阵P和排列t₁,t₂,…,t_2m决定的矩阵,则由定理1可知:对任意$H = ({C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}}) \in {[Z/({2^n})]^{m - 1}}$及任意e∈Z/(2ⁿ),当1≤i≤m时,令:

$C_{{t_i}}^{(H)}(\varepsilon ) = \left\{ {\begin{array}{*{20}{l}} {{C_{{t_i}}},{\text{ }}i \geqslant m + 2} \\ {\varepsilon ,{\text{ }}i = m + 1} \\ {{e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}},{\text{ }}i \leqslant m} \end{array}} \right.,$

则$C_{{t_1}}^{(H)}(\varepsilon ),...,C_{{t_{2m}}}^{(H)}(\varepsilon )$使$C_{{t_i}}^{(H)}(\varepsilon ) = \mathop \oplus \limits_{j = 1}^m {e_{i,j}}C_{{t_{m + j}}}^{(H)}(\varepsilon )$对1≤i≤m均成立.故,存在A∈Z/(2ⁿ),使得:

$(C_{{t_1}}^{(H)}(\varepsilon ),...,C_{{t_{2m}}}^{(H)}(\varepsilon )) = A||PA.$

由定理1还可知,上述$C_{{t_1}}^{(H)}(\varepsilon ),...,C_{{t_{2m}}}^{(H)}(\varepsilon )$是满足C=A||PA和$({C_{{t_{m + 2}}}}(\varepsilon ),...,{C_{{t_{2m}}}}(\varepsilon )) = H$的唯一C.

这说明,在$H = ({C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}}) \in {[Z/({2^n})]^{m - 1}}$给定时,满足C=A||PA和$({C_{{t_{m + 2}}}}(\varepsilon ),...,{C_{{t_{2m}}}}(\varepsilon )) = H$的C与Z/(2ⁿ)中的e一一对应,因而:

${p_{SPS}}(\alpha \to \beta ) = \sum\limits_{A \in {{[Z/({2^n})]}^m}} {{p_T}(\gamma \to A||PA)} $ $ = \sum\limits_{{C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}} \in Z/({2^n})} {\left[ {\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} \sum\limits_{\varepsilon = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i = 1}^{m + 1} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(\varepsilon ))} } \right]} } \right]} .$

由于当e遍历{0,1}ⁿ时,对于1≤i≤m,$C_{{t_i}}^{(H)}(\varepsilon )$均遍历{0,1}ⁿ,因而对0≤i≤m+1,${p_T}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(0)),$ ${p_T}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(1)),...,{p_T}({\gamma _{{t_i}}} \to C_{{t_{{t_i}}}}^{(H)}({2^n} - 1))$是${p_{{t_i},0}},{p_{{t_i},1}},...,{p_{{t_i},{2^n} - 1}}$的一个排列${q_{{t_i},0}},{q_{{t_i},1}},...,{q_{{t_i},{2^n} - 1}}$,故,由引理3可知:

$\sum\limits_{\varepsilon = 0}^{{2^n} - 1} {\left( {\prod\limits_{i = 1}^{m + 1} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(\varepsilon ))} } \right)} = \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i = 1}^{m + 1} {{q_{{t_i},j}}} } \right]} \leqslant \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i = 1}^{m + 1} {{p_{{t_i},j}}} } \right]} = \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} .$

于是有:

${p_{SPS}}(\alpha \to \beta ) = \sum\limits_{{C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}} \in Z/({2^n})} {\left[ {\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} \sum\limits_{\varepsilon = 0}^{{2^n} - 1} {\prod\limits_{i = 1}^{m + 1} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(\varepsilon ))} } } \right]} $ $ = \sum\limits_{{C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}} \in Z/({2^n})} {\left[ {\left( {\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} } \right)\sum\limits_{\varepsilon = 0}^{{2^n} - 1} {\left( {\prod\limits_{i \in \Omega } {{q_{i,j}}} } \right)} } \right]} $ $ \leqslant \sum\limits_{{C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}} \in Z/({2^n})} {\left[ {\left( {\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} } \right)\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} } \right]} $${\text{ }} = \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} \sum\limits_{{C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}} \in Z/({2^n})} {\left( {\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} } \right)} $$ = \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} \prod\limits_{i = m + 2}^{2m} {\sum\limits_{{C_{{t_i}}} \in Z/({2^n})} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} } .$

再遍历集合Ω,即证:

${p_{SPS}}(\alpha \to \beta ) \leqslant \min \left\{ {\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} :\Omega \Lambda m + 1} \right\}$

这说明本定理之情形(1)成立.

(2) 设Ω是Λ的m+1元子集,使得${p_{SPS}}(\alpha \to \beta ) = \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} \ne 0,$则由情形(1)的证明可知,情形(1)中不等式成立的充要条件是:对任意的$H = ({C_{{t_{m + 2}}}},...,{C_{{t_{2m}}}}) \in {[Z/({2^n})]^{m - 1}}$,当$\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} \ne 0$时,均有:

$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {{p_{i,j}}} } \right]} = \sum\limits_{\varepsilon = 0}^{{2^n} - 1} {\left( {\prod\limits_{i = 1}^{m + 1} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(\varepsilon ))} } \right)} = \sum\limits_{\varepsilon = 0}^{{2^n} - 1} {\left( {\prod\limits_{i = 1}^{m + 1} {{p_{{T_{{t_i}}}}}\left( {{\gamma _{{t_i}}} \to {e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}}} \right)} } \right)} $ (^*)

记${j_0} = \mathop {\min }\limits_{1 \leqslant i \leqslant m + 1} \# \{ \xi :{p_{{T_i}}}({\gamma _{{t_i}}} \to \xi ) \ne 0\} $,再由引理3得知,公式(^*)等价于${p_{{T_{{t_i}}}}}\left( {{\gamma _{{t_i}}} \to {e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}}} \right),\varepsilon \in Z/({2^n})$的前j₀个大值按大小排列的顺序与i无关,即,${p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to b),b \in Z/({2^n})$的前j₀个大值按大小排列的顺序与i无关.

由于wt_n(α)+wt_n(β)≥m+2且${\gamma _{{t_{m + 2}}}} \ne 0,$故由S是双射可知:当${p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to {C_{{t_{m + 2}}}}) \ne 0$时,一定有${C_{{t_{m + 2}}}} \ne 0.$设x₁=0且${C_{{t_{m + 2}}}} \oplus {\xi _1},{C_{{t_{m + 2}}}} \oplus {\xi _2},...,{C_{{t_{m + 2}}}} \oplus {\xi _k}$是使得${p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to \eta ) \ne 0$的所有输出差h,再设${\varepsilon _1},{\varepsilon _2},...,{\varepsilon _{{r_i}}}$是使

${p_{{T_{{t_i}}}}}\left( {{\gamma _{{t_i}}} \to {e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}}} \right) = \max \{ {p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to b):b \in Z/({2^n})\} $

成立的所有$\varepsilon $.对任意的$H = ({C_{{t_{m + 3}}}},...,{C_{{t_{2m}}}}) \in {[Z/({2^n})]^{m - 2}}$及任意的$\varepsilon $∈Z/(2ⁿ),1≤u≤k,当1≤i≤m时,令:

$C_{{t_i}}^{(H)}(\varepsilon ,u) = \left\{ {\begin{array}{*{20}{l}} {{C_{{t_i}}},{\text{ }}i \geqslant m + 3} \\ {\varepsilon ,{\text{ }}i = m + 1} \\ {{C_{{t_i}}} \oplus {\xi _u},{\text{ }}i = m + 2} \\ {{e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}} \oplus {e_{i,2}}{\xi _u},{\text{ }}i \leqslant m} \end{array}} \right.,$

则$C_{{t_1}}^{(H)}(\varepsilon ,u),...,C_{{t_{2m}}}^{(H)}(\varepsilon ,u)$使$C_{{t_i}}^{(H)}(\varepsilon ,u) = \mathop \oplus \limits_{j = 1}^m {e_{i,j}}C_{{t_{m + j}}}^{(H)}(\varepsilon ,u)$对1≤i≤m均成立.由于${p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to {C_{{t_{m + 2}}}}) \ne 0$等价于${p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to C_{{t_i}}^{(H)}(\varepsilon ,u)) \ne 0,$故,$\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to {C_{{t_i}}})} \ne 0$等价于$\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(\varepsilon ,u))} \ne 0.$

现考察在形如${e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}} \oplus {e_{i,2}}{\xi _u}$的输出差中,哪些能使${T_{{t_i}}}$在输入差是${\gamma _{{t_i}}}$时的差分概率达到最大.设${e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}} \oplus {e_{i,2}}{\xi _u}$使${T_{{t_i}}}$在输入差是${\gamma _{{t_i}}}$时的差分概率达到最大,则由$\varepsilon $_v的定义可知,该假设等价于${e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}} \oplus {e_{i,2}}{\xi _u} \in \left\{ {{e_{i,1}}{\varepsilon _v} \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}}:1 \leqslant v \leqslant {r_{{t_i}}}} \right\},$因而等价于存在$1 \leqslant v \leqslant {r_{{t_i}}}$使得:

${e_{i,1}}\varepsilon \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}} \oplus {e_{i,2}}{\xi _u} = {e_{i,1}}{\varepsilon _v} \oplus \mathop \oplus \limits_{j = 2}^m {e_{i,j}}{C_{{t_{m + j}}}}.$

即$\varepsilon = {\varepsilon _v} \oplus e_{i,1}^{ - 1}{e_{i,2}}{\xi _u}$,亦即$\varepsilon \in \{ {\varepsilon _v} \oplus e_{i,1}^{ - 1}{e_{i,2}}{\xi _u}:1 \leqslant v \leqslant {r_{{t_i}}}\} .$

因而,$\{ {\varepsilon _v} \oplus e_{i,1}^{ - 1}{e_{i,2}}{\xi _u}:1 \leqslant v \leqslant {r_{{t_i}}},1 \leqslant u \leqslant k\} $是使${T_{{t_i}}}$在输入差是${\gamma _{{t_i}}}$时的差分概率达到最大的所有输出差.

由于当1≤u≤k时$\prod\limits_{i = m + 2}^{2m} {{p_{{T_{{t_i}}}}}({\gamma _{{t_i}}} \to C_{{t_i}}^{(H)}(\varepsilon ,u))} \ne 0,$故由公式(^*)对$(C_{{t_{m + 2}}}^{(H)}(\varepsilon ,u),...,C_{{t_{2m}}}^{(H)}(\varepsilon ,u))$成立可知:

$\{ {\varepsilon _v} \oplus e_{i,1}^{ - 1}{e_{i,2}}{\xi _u}:1 \leqslant v \leqslant {r_{{t_i}}},1 \leqslant u \leqslant k\} = \{ {\varepsilon _u}:1 \leqslant u \leqslant {r_{{t_i}}}\} .$

设1≤u≤k,则$\forall v:1 \leqslant v \leqslant {r_{{t_i}}},$存在$w:1 \leqslant w \leqslant {r_{{t_i}}},$使得${\varepsilon _v} \oplus e_{i,1}^{ - 1}{e_{i,2}}{\xi _u} = {\varepsilon _w}.$于是,${\xi _u} = {(e_{i,1}^{ - 1}{e_{i,2}})^{ - 1}}({\varepsilon _w} \oplus {\varepsilon _v}),$因而:

${\xi _u} \in \{ e_{i,2}^{ - 1}{e_{i,1}}({\varepsilon _w} \oplus {\varepsilon _v}):1 \leqslant w,v \leqslant {r_{{t_i}}}\} .$

故$k \leqslant 1 + C_{{r_i}}^2,$即,${T_{{t_{m + 2}}}}$在输入差为${\gamma _{{t_{m + 2}}}}$时非零输出差的个数$ \leqslant 1 + C_{{r_i}}^2,$故${T_{{t_{m + 2}}}}$在输入差分${\gamma _{{t_{m + 2}}}}$时非零输出差的个数$ \leqslant \min \{ 1 + C_{{r_i}}^2:1 \leqslant i \leqslant m + 1\} ,$即,情形(2)成立.

对于AES算法的S盒,$\# \{ \xi :{p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to \xi ) \ne 0\} = 127$且r_i=1,因而定理2之情形(2)的条件:

$\# \{ \xi :{p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to \xi ) \ne 0\} \leqslant \min \{ 1 + C_{{r_i}}^2:1 \leqslant i \leqslant m + 1\} $

不成立.一般地,为保证S盒的差分均匀性,密码算法中的S盒一般都使r_i很小甚至为1,因而,条件:

$\# \{ \xi :{p_{{T_{{t_{m + 2}}}}}}({\gamma _{{t_{m + 2}}}} \to \xi ) \ne 0\} \leqslant \min \{ 1 + C_{{r_i}}^2:1 \leqslant i \leqslant m + 1\} $

通常都不成立,这说明SPS模型的重量大于分支数的差分对应的概率一般达不到定理2给出的上界.

若SPS模型的扩散结构P是分支数为B_d的n-MDS矩阵,则计算根据定理2之情形(1)给出的差分对应α→β的差分概率上界的计算复杂度为${2^n} \times C_{w{t_n}(\alpha ) + w{t_n}(\beta )}^{{B_d}}.$例如:对于以扩散结构P是GF(2⁸)上4x4的MDS矩阵为例,计算差分对应上界的计算复杂度最大为${2^8} \times C_8^5 = {2^{13.8}}.$

4 SPS模型差分概率的新上界

记SPS模型差分概率的上界为B_SPS,下面我们将给出B_SPS的估计公式.

引理4^[19]. 设实数序列$\{ x_i^{(j)}\} _{i = 1}^n,$1≤j≤m,则有:

$\sum\limits_{i = 1}^n {|x_i^{(1)}...x_i^{(m)}|} \leqslant \max \left\{ {\sum\limits_{i = 1}^n {|x_i^{(1)}{|^m}} ,...,\sum\limits_{i = 1}^n {|x_i^{(m)}{|^m}} } \right\},$

其中,等号成立的充要条件为:对任意的j,k∈{1,2,…,m},1≤i≤n,均有$|x_i^{(j)}| = |x_i^{(k)}|$成立.

注:文献^[19]中仅给出了本文引理4中不等号成立的证明,而等号成立的充要条件并没有进行证明.

定理3. 设扩散变换P为n-MDS矩阵对应的仿射变换f(x)=Px⊕b构成,且分支数为m+1,g=(g₁,g₂,…,g_2m)∈

[Z/(2ⁿ)]^2m.如果S_i在输入差为g_i时差分对应概率从大到小依次为$p_{{\gamma _i},0}^{(i)},...,p_{{\gamma _i},{2^n} - 1}^{(i)},$S_i在输出差为g_i时差分对应概率从大到小依次为$p_{{\gamma _i},0}^{(m + i)},...,p_{{\gamma _i},{2^n} - 1}^{(m + i)},$则有:

(1) SPS模型非平凡差分对应的概率上界为

${B_{SPS}} = \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\min }\limits_{\Omega \subseteq {\Lambda _\gamma },|\Omega | = {B_d}} \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} .$

这里,Λ_g是由g的非零坐标构成的集合;

(2) ${B_{SPS}} \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}\backslash \{ 0\} } \sum\limits_{j = 1}^{{2^n} - 1} {{{\{ p_{u,j}^{(i)}\} }^{{B_d}}}} ;$

(3) ${B_{SPS}} = \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}\backslash \{ 0\} } \sum\limits_{j = 1}^{{2^n} - 1} {{{\{ p_{u,j}^{(i)}\} }^{{B_d}}}} $成立的必要条件为:存在使wt(x)≥B_d的x∈[Z/(2ⁿ)]^2m,向量x的非零坐标序号对应的S盒的在给定输入差时差分概率的大小排序都相同;充分条件为:对任意的i,k∈{1,2,…,2m}及任意的u∈{0,1}ⁿ,ϕ∈{0,1,…,2ⁿ-1},均有$p_{u,j}^{(i)} = p_{u,j}^{(k)}$,即:任意两个S盒,在给定输入差时,差分概率的大小排序都相同.

证明:

(1) 设α||β=g∈[Z/(2ⁿ)]^2m\{0},Λ_g是g的非零坐标构成的集合.设p_SPS(α→b)≠0,则wt(g)≥B_d.记Ω为Λ_g的一个B_d元子集,则由定理2之情形(1)可知:

${p_{SPS}}(\alpha \to \beta ) \leqslant \mathop {\min }\limits_{\Omega \subseteq {\Lambda _\gamma },|\Omega | = {B_d}} \left\{ {\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} } \right\}$ $ \leqslant \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\min }\limits_{\Omega \subseteq {\Lambda _\gamma },|\Omega | = {B_d}} \left\{ {\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} } \right\};$

(2) 由引理4可知,对使|Ω|=B_d的ΩϕΛ_g,有:

$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} \leqslant \mathop {\max }\limits_{i \in \Omega } \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ $ \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $

即:

$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ (I)

故有:

$\mathop {\min }\limits_{\Omega \subseteq {\Lambda _\gamma },|\Omega | = {B_d}} \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ (II)

进而有:

${B_{SPS}} = \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\min }\limits_{\Omega \subseteq {\Lambda _\gamma },|\Omega | = {B_d}} \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{\gamma _i},j}^{(i)}} } \right]} $ $ \leqslant \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ $ = \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{u,j}^{(i)}]}^{{B_d}}}} $ (III)

事实上,设1≤i≤2m和r_i≠0,使得$\mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} = \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $,则有:

$\sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{r_i},j}^{(i)}]}^{{B_d}}}} \leqslant \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{u,j}^{(i)}]}^{{B_d}}}} .$

即:

$\mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}\backslash \{ 0\} } \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ $ \leqslant \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{u,j}^{(i)}]}^{{B_d}}}} ;$

反之,设v≠0和1≤i≤2m,使得$\mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{u,j}^{(i)}]}^{{B_d}}}} = \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{v,j}^{(i)}]}^{{B_d}}}} ,$令r=(r₁,r₂,…,r_2m)∈{0,1}^2m,使r_i=v对1≤

i≤2m成立,则有:

$\mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ $ \geqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{r_i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{r_i},j}^{(i)}]}^{{B_d}}}} = \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{v,j}^{(i)}]}^{{B_d}}}} .$

因而

$\sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{v,j}^{(i)}]}^{{B_d}}}} \leqslant \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} .$

即:

$\mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{u,j}^{(i)}]}^{{B_d}}}} $ $ \leqslant \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} .$

这说明:

$\mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{u,j}^{(i)}]}^{{B_d}}}} $ $ = \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}\backslash \{ 0\} } \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} .$

(3) 由于情形(2)中的等式成立等价于公式(III)中的等式成立,即,存在使wt(x)≥B_d的x∈[Z/(2ⁿ)]^2m,使得:

$\mathop {\min }\limits_{\Omega \subseteq {\Lambda _x},|\Omega | = {B_d}} \sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{x_i},j}^{(i)}} } \right]} $ $ = \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} ;$

又由公式(II)对使|Ω|=B_d的ΩϕΛ_x都成立,即:

$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{x_i},j}^{(i)}} } \right]} \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{x_i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{x_i},j}^{(i)}]}^{{B_d}}}} $ $ \leqslant \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $

对使|Ω|=B_d的ΩϕΛ_x都成立,因而公式(III)成立等价于对使|Ω|=B_d的ΩϕΛ_x,都有:

$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{x_i},j}^{(i)}} } \right]} = $$\mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} $ (IV)

· 必要性

设情形(2)成立,则由公式(I)和$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{x_i},j}^{(i)}} } \right]} \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{x_i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{x_i},j}^{(i)}]}^{{B_d}}}} $$ \leqslant \mathop {\max }\limits_{\gamma \in {{[Z/({2^n})]}^{2m}}wt(\gamma ) \geqslant {B_d}} \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{\gamma _i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{\gamma _i},j}^{(i)}]}^{{B_d}}}} ,$从而由公式(IV)可知$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{x_i},j}^{(i)}} } \right]} = \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{x_i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{x_i},j}^{(i)}]}^{{B_d}}}} ;$

再由引理4可知:对ϕi,k∈Ω及ϕ∈{0,1,…,2ⁿ-1},均有$p_{{x_i},j}^{(i)} = p_{{x_k},j}^{(k)}$,即,向量x的非零坐标序号对应的S盒的在

给定输入差x_k时差分概率的大小排序都相同.

· 充分性

设存在重量≥B_d的向量x,使x的非零坐标序号对应的S盒的差分概率的大小排序都相同,则由引理4可知,对使|Ω|=B_d的ΩϕL_x及ϕt,均有:

$\sum\limits_{j = 0}^{{2^n} - 1} {\left[ {\prod\limits_{i \in \Omega } {p_{{x_i},j}^{(i)}} } \right]} = \mathop {\max }\limits_{i \in \Omega } \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{x_i},j}^{(i)}]}^{{B_d}}}} $ $ = \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{x_i},j}^{(t)}]}^{{B_d}}}} = \mathop {\max }\limits_{1 \leqslant i \leqslant 2m,{x_i} \ne 0} \sum\limits_{j = 0}^{{2^n} - 1} {{{[p_{{x_i},j}^{(i)}]}^{{B_d}}}} .$

即,公式(I)中的等号对使|Ω|=B_d的ΩϕL_x均成立,因而公式(II)对x成立.

目前,SPS模型差分概率最好的上界是2003年由Park等人在文献^[19]中给出的上界:

$\max \left\{ {\mathop {\max }\limits_{1 \leqslant i \leqslant m} \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \sum\limits_{j = 1}^{{2^n} - 1} {{{\{ p_{u,j}^{(i)}\} }^{{B_d}}}} ,\mathop {\max }\limits_{1 \leqslant i \leqslant m} \mathop {\max }\limits_{u \in {{\{ 0,1\} }^n}} \sum\limits_{j = 1}^{{2^n} - 1} {{{\{ p_{j,u}^{(i)}\} }^{{B_d}}}} } \right\},$

其中,B_d为线性变换的分支数,$p_{u,j}^{(i)}$为第i个S盒输入差为u、输出差为j时的差分概率.由定理3之情形(3)可知:

若SPS模型中各个S盒的差分概率从大到小的排列完全相同时,本文给出的上界与文献^[19]给出的上界在数值上是相同的.

当SPS模型中各个S盒的差分概率从大到小的排列不完全相同时,我们通过计算机模拟实验考察了本文给出的上界与文献^[19]的上界进行比较的情况.当m=4时,对于8进8出的随机S盒,我们随机生成了700个满足最大差分概率为8/256且最大Walsh谱的绝对值为60/256的S盒,并在m=4时任取其中8个分别作为SPS模型中的8个S盒,共进行2¹⁶组实验.实验结果如图1所示.实验结果表明:当m=4时,对于8进8出的随机S盒,本文给出的SPS模型差分概率的上界大致为文献^[19]给出的上界的一半.这也说明,在设计SP网络的S层时,若使得S层中各个S盒的差分分布不同,可能会使SP网络获得更好 的差分性质.

5 结束语

本文对P盒为n-MDS矩阵的SPS模型差分概率上界的估计问题进行了研究.首先从给定的差分对应入手,给出了其差分概率上界的估计公式,并给出了当差分对应的重量大于分支数时,其差分概率达到该上界的一个必要条件;然后给出了SPS模型输入与输出差分遍历所有的可能差分对时,该类SPS模型差分概率的一个新上界;最后,利用计算机模拟实验对Park等人给出的上界与本文给出的上界进行了对比.实验结果表明:当S盒是独立不同的S盒时,该上界比Park等人给出的上界更紧,从而说明使用独立的S盒可能获得比使用相同S盒获得更好的抗差分攻击的能力.本文的研究丰富了SPS模型差分概率的分析结果,为基于该模型设计的分组密码算法的可证明安全性提供了理论支撑.