有限域F_(p~n)上与逆函数仿射等价的密码函数计数问题
|
摘要
分组密码的安全性主要依赖于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盒使用.
The security of modern block ciphers substantially relies on the cryptographic properties of its S-boxes(vectorial cryptographic functions),which are always the only source of nonlinearity.It is optimal to choose differentially 4-uniform permutations as S-boxes of block ciphers in real applications.The inverse function is the most famous differentially 4-uniform permutation with many desirable cryptographic properties.The vectorial functions of affine equivalent to the inverse function over F28 are frequently selected as the S-boxes of many important block ciphers,such as AES,Camellia,CLEFIA and SMS4.Now the research on the S-boxes of affine equivalent to the inverse function focuses the counting method of the minimum number of active S-boxes for several consecutive rounds of block ciphers.Unlike the previous research works,this paper investigates the counting problem of affine equivalent to the inverse function over F_(p~n).If the exact number of affine equivalent to the inverse function is calculated,the designer of cryptographic algorithm knows that how many the S-boxes of affine equivalent to the inverse function should be selected in real applications.The inverse function over finite field F_(2~n) is generalized to the inverse function over finite field F_(p~n),where p≥2 is a prime number.This is a generalization of the inverse function.Firstly,the product"*"of(T_1,R1)and(T_2,R_2)is defined as(T_2,R_2)*(T_1,R1)··=■,where(T_1,R1),(T_2,R_2)∈Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q),Aff_n~(-1)(F_q)is the n×n invertible affine transformation group over finite field F_q,q=pm,p≥2 is a prime number,m≥1 is a positive integer,and "■"denotes the product of the mapping.This paper proves that Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q)is a group and the pairs of invertible affine transformations(V,W)∈Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q)satisfied by F=■ form a subgroup of the group Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q)with respect to the operation"*".Secondly,when p≥3 and n≥2,or p=2 and n≥4,for the inverse function F(x)=x-1=x~(p~n-2)∈F_(p~n)[x],we utilize the above results and some properties of finite fields to prove that there exists the pairs of invertible affine transformations(ν,μ)∈Aff_n~(-1)(Fp)×Aff_n~(-1)(Fp)such that F=■,where the linearized polynomials of invertible affine transformationsμ andν must beμ(x)=S_tx~(p~t) and ν(x)=S_t~(p~n-t) x~(p~(n-t)),0≠St∈F_(p~n),t=0,1,…,n-1.Then the pairs number of invertible affine transformations(ν,μ)is n(p~n-1).The group Aff_n~(-1)(F_p)×Aff_n~(-1)(F_p)can be partitioned into equivalence classes by using the pairs of invertible affine transformations(ν,μ)form the subgroup.The number of coset representatives of the group Aff_n~(-1)(Fp)×Aff_n~(-1)(Fp)relative to the subgroup is equal to the number of affine equivalent to the inverse function.In this case,the number of affine equivalent to the inverse function is ■.Thirdly,when p=2 and n=3,for the inverse function F(x)=x~(-1)=x~(2~3-2)∈F_2~3[x],the pairs number of invertible affine transformations(ν,μ)∈Aff_3~(-1)(F2)×Aff_3~(-1)(F_2)satisfied by F=■ is 168,which is calculated by the computer.The group Aff_3~(-1)(F2)×Aff_3~(-1)(F_2)can be partitioned into equivalence classes using the subgroup that is formed by the pairs of invertible affine transformations(ν,μ).The number of coset representatives of the group Aff_3~(-1)(F_2)×Aff_3~(-1)(F_2)relative to the subgroup is equal to the number of affine equivalent to the inverse function.In this case,the number of affine equivalent to the inverse function is 10 752.Our results show that there exists ■ cryptographic functions of affine equivalent to the inverse function over finite field F_2~8 to be used in the S-boxes of block ciphers in real applications.
The security of modern block ciphers substantially relies on the cryptographic properties of its S-boxes(vectorial cryptographic functions),which are always the only source of nonlinearity.It is optimal to choose differentially 4-uniform permutations as S-boxes of block ciphers in real applications.The inverse function is the most famous differentially 4-uniform permutation with many desirable cryptographic properties.The vectorial functions of affine equivalent to the inverse function over F28 are frequently selected as the S-boxes of many important block ciphers,such as AES,Camellia,CLEFIA and SMS4.Now the research on the S-boxes of affine equivalent to the inverse function focuses the counting method of the minimum number of active S-boxes for several consecutive rounds of block ciphers.Unlike the previous research works,this paper investigates the counting problem of affine equivalent to the inverse function over F_(p~n).If the exact number of affine equivalent to the inverse function is calculated,the designer of cryptographic algorithm knows that how many the S-boxes of affine equivalent to the inverse function should be selected in real applications.The inverse function over finite field F_(2~n) is generalized to the inverse function over finite field F_(p~n),where p≥2 is a prime number.This is a generalization of the inverse function.Firstly,the product"*"of(T_1,R1)and(T_2,R_2)is defined as(T_2,R_2)*(T_1,R1)··=■,where(T_1,R1),(T_2,R_2)∈Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q),Aff_n~(-1)(F_q)is the n×n invertible affine transformation group over finite field F_q,q=pm,p≥2 is a prime number,m≥1 is a positive integer,and "■"denotes the product of the mapping.This paper proves that Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q)is a group and the pairs of invertible affine transformations(V,W)∈Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q)satisfied by F=■ form a subgroup of the group Aff_n~(-1)(F_q)×Aff_n~(-1)(F_q)with respect to the operation"*".Secondly,when p≥3 and n≥2,or p=2 and n≥4,for the inverse function F(x)=x-1=x~(p~n-2)∈F_(p~n)[x],we utilize the above results and some properties of finite fields to prove that there exists the pairs of invertible affine transformations(ν,μ)∈Aff_n~(-1)(Fp)×Aff_n~(-1)(Fp)such that F=■,where the linearized polynomials of invertible affine transformationsμ andν must beμ(x)=S_tx~(p~t) and ν(x)=S_t~(p~n-t) x~(p~(n-t)),0≠St∈F_(p~n),t=0,1,…,n-1.Then the pairs number of invertible affine transformations(ν,μ)is n(p~n-1).The group Aff_n~(-1)(F_p)×Aff_n~(-1)(F_p)can be partitioned into equivalence classes by using the pairs of invertible affine transformations(ν,μ)form the subgroup.The number of coset representatives of the group Aff_n~(-1)(Fp)×Aff_n~(-1)(Fp)relative to the subgroup is equal to the number of affine equivalent to the inverse function.In this case,the number of affine equivalent to the inverse function is ■.Thirdly,when p=2 and n=3,for the inverse function F(x)=x~(-1)=x~(2~3-2)∈F_2~3[x],the pairs number of invertible affine transformations(ν,μ)∈Aff_3~(-1)(F2)×Aff_3~(-1)(F_2)satisfied by F=■ is 168,which is calculated by the computer.The group Aff_3~(-1)(F2)×Aff_3~(-1)(F_2)can be partitioned into equivalence classes using the subgroup that is formed by the pairs of invertible affine transformations(ν,μ).The number of coset representatives of the group Aff_3~(-1)(F_2)×Aff_3~(-1)(F_2)relative to the subgroup is equal to the number of affine equivalent to the inverse function.In this case,the number of affine equivalent to the inverse function is 10 752.Our results show that there exists ■ cryptographic functions of affine equivalent to the inverse function over finite field F_2~8 to be used in the S-boxes of block ciphers in real applications.
引文
[1]Carlet C.S-boxes,Boolean functions and codes for the resistance of block ciphers to cryptographic attacks,with or without side channels//Proceedings of the 5th International Conference on Security,Privacy,and Applied Cryptography Engineering-SPACE’2015.LNCS 9354.Jaipur,India,2015:151-171
[2]Peng Jie,Tan C H.New explicit constructions of differentially4-uniform permutations via special partitions of GF(22k).Finite Fields and Their Applications,2016,40:73-89
[3]Carlet C.On known and new differentially uniform functions//Proceedings of the 16th Australasian Conference on Information Security and Privacy-ACISP’2011.LNCS 6812.Melbourne,Australia,2011:1-15
[4]Budaghyan L,Carlet C.CCZ-equivalence of bent vectorial functions and related constructions.Designs,Codes and Cryptography,2011,59(1-3):69-87
[5]Berger T P,Canteaut A,Charpin P,Laigle-Chapuy Y.On almost perfect nonlinear functions over GF(2n).IEEETransactions on Information Theory,2006,52(9):4160-4170
[6]Budaghyan L,Carlet C,Helleseth T,Li Nian.On the(non-)existence of APN(n,n)-functions of algebraic degree n//Proceedings of the IEEE International Symposium on Information Theory-ISIT’2016,Barcelona,Spain,2016:480-484
[7]Browning K A,Dillon J F,McQuistan M T,Wolfe A J.An APN permutation in dimension six//Proceedings of the9th International Conference on Finite Fields and Their Applications-Fq’9.Dublin,Ireland,2010,518:33-42
[8]Perrin L,Udovenko A,Biryukov A.Cryptanalysis of a theorem:Decomposing the only known solution to the big APN problem//Proceedings of the Advances in CryptologyCRYPTO’2016,Part II.LNCS 9815.Santa Barbara,USA,2016:93-122
[9]Canteaut A,Duval S,Perrin L.A generalisation of Dillon’s APN permutation with the best known differential and nonlinear properties for all fields of size 24k+2.IEEETransactions on Information Theory,2017,63(11):7575-7591
[10]Tang Deng,Carlet C,Tang Xiao-Hu.Differentially 4-uniform bijections by permuting the inverse function.Designs,Codes and Cryptography,2015,77(1):117-141
[11]Qu Long-Jiang,Tan Yin,Li Chao,Gong Guang.More constructions of differentially 4-uniform permutations on GF(22k).Designs,Codes and Cryptography,2016,78(2):391-408
[12]Tao Biao-Shuai,Wu Hong-Jun.Improving the Biclique cryptanalysis of AES//Proceedings of the 20th Australasian Conference on Information Security and Privacy-ACISP’2015.LNCS 9144.Brisbane,Australia,2015:39-56
[13]Dong Xiao-Yang,Li Lei-Bo,Jia Ke-Ting,Wang Xiao-Yun.Improved attacks on reduced-round Camellia-128/192/256//Proceedings of the Topics in Cryptology-CT-RSA’2015,LNCS 9048.San Francisco,USA,2015:59-83
[14]Tezcan C,Sel9uk A A.Improved improbable differential attacks on ISO standard CLEFIA:Expansion technique revisited.Information Processing Letters,2016,116(2):136-143
[15]Su Bo-Zhan,Wu Wen-Ling,Zhang Wen-Tao.Security of the SMS4block cipher against differential cryptanalysis.Journal of Computer Science and Technology,2011,26(1):130-138
[16]Li Yong-Qiang,Wang Ming-Sheng.Constructing S-boxes for lightweight cryptography with Feistel structure//Proceedings of the Cryptographic Hardware and Embedded Systems-CHES’2014.LNCS 8731.Busan,South Korea,2014:127-146
[17]Mishra P R,Sarkar S,Gupta I.Determining the minimum degree of an S-box.IACR Cryptology ePrint Archive,2017:376
[18]Stoffelen K.Optimizing S-box implementations for several criteria using SAT solvers//Proceedings of the 23rd International Conference on Fast Software Encryption-FSE’2016,LNCS 9783.Bochum,Germany,2016:140-160
[19]Sajadieh M,Mirzaei A,Mala H,Rijmen V.A new counting method to bound the number of active S-boxes in Rijndael and 3D.Designs,Codes and Cryptography,2017,83(2):327-343
[20]Lidl R,Niederreiter H.Finite Fields.2nd Edition.Cambridge,UK:Cambridge University Press,1997
[21]Wan Zhe-Xian.Geometry of Classical Groups over Finite Fields.2nd Edition,Beijing:Science Press,2006
[2]Peng Jie,Tan C H.New explicit constructions of differentially4-uniform permutations via special partitions of GF(22k).Finite Fields and Their Applications,2016,40:73-89
[3]Carlet C.On known and new differentially uniform functions//Proceedings of the 16th Australasian Conference on Information Security and Privacy-ACISP’2011.LNCS 6812.Melbourne,Australia,2011:1-15
[4]Budaghyan L,Carlet C.CCZ-equivalence of bent vectorial functions and related constructions.Designs,Codes and Cryptography,2011,59(1-3):69-87
[5]Berger T P,Canteaut A,Charpin P,Laigle-Chapuy Y.On almost perfect nonlinear functions over GF(2n).IEEETransactions on Information Theory,2006,52(9):4160-4170
[6]Budaghyan L,Carlet C,Helleseth T,Li Nian.On the(non-)existence of APN(n,n)-functions of algebraic degree n//Proceedings of the IEEE International Symposium on Information Theory-ISIT’2016,Barcelona,Spain,2016:480-484
[7]Browning K A,Dillon J F,McQuistan M T,Wolfe A J.An APN permutation in dimension six//Proceedings of the9th International Conference on Finite Fields and Their Applications-Fq’9.Dublin,Ireland,2010,518:33-42
[8]Perrin L,Udovenko A,Biryukov A.Cryptanalysis of a theorem:Decomposing the only known solution to the big APN problem//Proceedings of the Advances in CryptologyCRYPTO’2016,Part II.LNCS 9815.Santa Barbara,USA,2016:93-122
[9]Canteaut A,Duval S,Perrin L.A generalisation of Dillon’s APN permutation with the best known differential and nonlinear properties for all fields of size 24k+2.IEEETransactions on Information Theory,2017,63(11):7575-7591
[10]Tang Deng,Carlet C,Tang Xiao-Hu.Differentially 4-uniform bijections by permuting the inverse function.Designs,Codes and Cryptography,2015,77(1):117-141
[11]Qu Long-Jiang,Tan Yin,Li Chao,Gong Guang.More constructions of differentially 4-uniform permutations on GF(22k).Designs,Codes and Cryptography,2016,78(2):391-408
[12]Tao Biao-Shuai,Wu Hong-Jun.Improving the Biclique cryptanalysis of AES//Proceedings of the 20th Australasian Conference on Information Security and Privacy-ACISP’2015.LNCS 9144.Brisbane,Australia,2015:39-56
[13]Dong Xiao-Yang,Li Lei-Bo,Jia Ke-Ting,Wang Xiao-Yun.Improved attacks on reduced-round Camellia-128/192/256//Proceedings of the Topics in Cryptology-CT-RSA’2015,LNCS 9048.San Francisco,USA,2015:59-83
[14]Tezcan C,Sel9uk A A.Improved improbable differential attacks on ISO standard CLEFIA:Expansion technique revisited.Information Processing Letters,2016,116(2):136-143
[15]Su Bo-Zhan,Wu Wen-Ling,Zhang Wen-Tao.Security of the SMS4block cipher against differential cryptanalysis.Journal of Computer Science and Technology,2011,26(1):130-138
[16]Li Yong-Qiang,Wang Ming-Sheng.Constructing S-boxes for lightweight cryptography with Feistel structure//Proceedings of the Cryptographic Hardware and Embedded Systems-CHES’2014.LNCS 8731.Busan,South Korea,2014:127-146
[17]Mishra P R,Sarkar S,Gupta I.Determining the minimum degree of an S-box.IACR Cryptology ePrint Archive,2017:376
[18]Stoffelen K.Optimizing S-box implementations for several criteria using SAT solvers//Proceedings of the 23rd International Conference on Fast Software Encryption-FSE’2016,LNCS 9783.Bochum,Germany,2016:140-160
[19]Sajadieh M,Mirzaei A,Mala H,Rijmen V.A new counting method to bound the number of active S-boxes in Rijndael and 3D.Designs,Codes and Cryptography,2017,83(2):327-343
[20]Lidl R,Niederreiter H.Finite Fields.2nd Edition.Cambridge,UK:Cambridge University Press,1997
[21]Wan Zhe-Xian.Geometry of Classical Groups over Finite Fields.2nd Edition,Beijing:Science Press,2006