有限域F_(p^n)上与逆函数仿射等价的密码函数计数问题

作     者：袁峰 江继军 杨旸 欧海文 王敏娟 YUAN Feng;JIANG Ji-Jun;YANG Yang;OU Hai-Wen;WANG Min-Juan

作者机构：北京电子科技学院密码科学与技术系北京100070 北京电子科技学院信息安全研究所北京100070 福州大学数学与计算机科学学院福州350108 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2019年第42卷第5期

页      面：1126-1136页

核心收录：

学科分类：0839[工学-网络空间安全] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家重点研发计划资助项目(2018YFB0803600) 国家自然科学基金青年科学基金(61402112) 中央高校基本科研业务费专项资金(2014XSYJ09 328201509) 北京电子科技学院科研团队项目(2014TD2-OHW)资助~~ 

主　　题：密码学 密码函数 S盒 逆函数 等价 数量 

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