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

摘要

分组密码的安全性主要依赖于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)∶=(T2·T1,R1aR2),其中(T1,R1),(T2,R2)∈Aff-1n (Fq)×Aff-1n(Fq),Aff-1n (Fq)是有限域Fq上的n×n阶可逆仿射变换群,q=pm,p≥2是一个素数,m≥1是一个正整数,“·”表示映射的合成.证明了Aff-1n (Fq)×Aff-1n(Fq)关于运算“*”是一个群;使得等式F=V·F·W成立的可逆仿射变换对(V,W)∈Aff-1n (Fq)×Aff-1n(Fq)关于运算“*”是Aff-1n(Fq)×Aff-1n(Fq)的一个子群.然后,利用以上结论和有限域的一些性质证明了,当p≥3且n≥2时,或者p=2且n≥4时,对于有限域Fpn上的逆函数F(x) =x-1=xpn-2,使得等式F=ν°F°μ成立的可逆仿射变换μ和ν线性化多项式的形式只能是μ(x)=Stxpt和ν(x) =Spn-1t,0≠St∈Fpn,t=0,1,…,n-1.于是,使得等式F=ν°F°μ成立的所有可逆仿射变换对(ν,μ)的数量为n(pn-1).利用这些可逆仿射变换对(ν,μ)所形成的子群对群Aff-1n(Fp)×Aff-1n(Fp)划分等价类,商集中陪集首的个数即为与逆函数仿射等价密码函数的数量.因此,在这种情况下,与逆函数仿射等价密码函数的数量为 [pn(n+1)/2Ⅱni=(pi-1)]2(pn-1).最后,当p=2且n=3时,对于有限域F23上的逆函数F(x)=x-1=x23-2,利用计算机作为辅助手段测试出使得等式F=ν°F°μ成立的可逆仿射变换对(ν,μ)的数量为168.利用这些可逆仿射变换对(ν,μ)所形成的子群对群Aff-1n (F2)×Aff-13 (F2)划分等价类,商集中陪集首的个数即为与逆函数仿射等价密码函数的数量.因此,在这种情况下,与逆函数仿射等价密码函数的数量为10752.研究结果表明,在实际应用中,有限域F28上有269×255×[Ⅱ7i=1(2i-1)]2个与逆函数仿射等价的密码函数可作为分组密码的S盒使用.