有限域Fpn上与逆函数仿射等价的密码函数计数问题

作者：袁峰; 江继军; 杨旸; 欧海文; 王敏娟

来源：计算机学报, 2019, 42(05): 1126-1136.

• 密码学
• 密码函数
• S盒
• 逆函数
• 等价
• 数量

分组密码的安全性主要依赖于S盒(向量值密码函数)的各项安全性指标.分组密码S盒的最优选择就是差分均匀度为4的向量值密码函数.逆函数是最著名的差分均匀度为4各项安全性指标均优良的向量值函数.著名的AES分组密码算法、Camellia分组密码算法、CLEFIA分组密码算法和SMS4分组密码算法均采用有限域F28上与逆函数仿射等价的向量值函数作为S盒.目前对于与逆函数仿射等价S盒的研究,主要侧重于研究分组密码算法经过多轮后活跃S盒的数量.与以往的研究角度有所不同,该文要研究有限域Fpn上与逆函数仿射等价向量值密码函数的计数问题.若能计算出与逆函数仿射等价密码函数的数量,在实际应用中就知道有多少个与逆函数仿射等价的S盒可供算法设计者选择.将有限域F2n上的逆函数推广成有限域Fpn上的逆函数,其中p≥2是一个素数,这是一个更为一般的逆函数.首先,该文定义(T1,R1)和(T2,R2)之间的运算"*"为(T2,R2)*(T1,R1)··=■,其中(T1,R1),(T2,R2)∈Affn-1(Fq)×Affn-1(Fq),Affn-1(Fq)是有限域Fq上的n×n阶可逆仿射变换群,q=pm,p≥2是一个素数,m≥1是一个正整数,"■"表示映射的合成.证明了Affn-1(Fq)×Affn-1(Fq)关于运算"*"是一个群;使得等式F=■成立的可逆仿射变换对(V,W)∈Affn-1(Fq)×Affn-1(Fq)关于运算"*"是Affn-1(Fq)×Affn-1(Fq)的一个子群.然后,利用以上结论和有限域的一些性质证明了,当p≥3且n≥2时,或者p=2且n≥4时,对于有限域Fpn上的逆函数F(x)=x-1=xpn-2,使得等式F=■成立的可逆仿射变换μ和ν线性化多项式的形式只能是μ(x)=Stxpt和ν(x)=Stpn-t xpn-t,0≠St∈Fpn,t=0,1,…,n-1.于是,使得等式F=■成立的所有可逆仿射变换对(ν,μ)的数量为n(pn-1).利用这些可逆仿射变换对(ν,μ)所形成的子群对群Affn-1(Fp)×Affn-1(Fp)划分等价类,商集中陪集首的个数即为与逆函数仿射等价密码函数的数量.因此,在这种情况下,与逆函数仿射等价密码函数的数量为■.最后,当p=2且n=3时,对于有限域F23上的逆函数F(x)=x-1=x23-2,利用计算机作为辅助手段测试出使得等式F=■成立的可逆仿射变换对(ν,μ)的数量为168.利用这些可逆仿射变换对(ν,μ)所形成的子群对群Aff3-1(F2)×Aff3-1(F2)划分等价类,商集中陪集首的个数即为与逆函数仿射等价密码函数的数量.因此,在这种情况下,与逆函数仿射等价密码函数的数量为10 752.研究结果表明,在实际应用中,有限域F28上有■个与逆函数仿射等价的密码函数可作为分组密码的S盒使用.

• 单位
  北京电子科技学院