HFM-PKC抗攻击性分析
摘要
随着计算机运算能力的不断提高,公钥密码已经成为密码学研究的重要方面。HFM-PKC是以多变元二次方程组和有限域上遍历矩阵的性质为理论基础构造的公钥密码方案。
本文首先给出以多变元二次方程组为基础的陷门构造方法。其次介绍HFM-PKC的公钥设计方案和加解密过程实现,同时分析其求解难度,证明了此公钥密码体制是NP完全问题。本文主要工作是对HFM-PKC方案的抗攻击性进行分析：首先通过差分分析证明了作用于HFM-PKC方案中心映射之上的仿射变换均可以被简化为线性变换。其次通过多项式同构攻击验证HFM-PKC方案的安全性。最后通过重线性化和指定变量法分析证明HFM-PKC在方程数量和变元数量相同时安全强度最大。
The advent of the Public-Key Cryptosystem is of epoch-making significance for the development of the cryptology. Because the encryption and decryption keys are different, so it can provide data encryption and signature authentication. However, the rapid development of computing power at the program on the security of public key cryptography presented a huge challenge. In particular, the emergence of quantum computing will inevitably lead to collapse of the current public key cryptography. Find a good public-key cryptosystem to against quantum attack is of cryptography to solve the pressing problems.
The trapdoor is based on the difficulty in solving a system of Multivariate Quadratic Polynomials Equations over finite fields. The central map must be easy to invert and the two affine transformations S and T are invertible affine transformation over the finite field F.In particular, these two affine transformations are used to hide the internal structure of the central equations. There are different public key cryptographic schemes for every the central map. such as MIA, HFE. UOV and so on.
HFM-PKC public key cryptography scheme is a special case of MQ problem and it is a NP-complete problem. The scheme haveλ·n equations andλ·n variables x= (x1,x2,…,x(λ-1)n)∈Fq(λ-1)n,y=(y1,y2,…,yn)∈Eqn. The scheme's public key is (Fq,ρ=[ρ1 (v),ρ2(v),…ρλn(v)]) and the private key is (A,B,S,T). In my paper, there are four methods are used to analysis the HFM-PKC scheme.
1. By the research on differentials cryptanalysis I arrive at a conclusion that the HFM-PKC scheme can't resist the difference value's attack. To known the difference value,Δv= (δ1,δ2,…δ(λ-1)n,δ1',…δn') forΔv∈Fλn, The system of Multivariate Quadratic Polynomials Equations of HFM-PKC can be solved in polynomial time. In additional, the affine transformation S(x). we haveρ(v)= S(?)P=P(Sv+S0) and deduce further that v=S-1 (x-S0)=S-1x-S-1S0. However, if the v0 exactly equal to -S-1S0, we can getΔv=S-1x. In order to let the coefficients of the linear equations which include (δ1,δ2,…δ(λ-1)n,δ1',…δn) equal to 0, we didρ1(v0+Δv)-ρ1(v0). There areλ·n equations andλ·n variables' linear equations must exist a nonzero solution, that is, the coefficient matrix |A| equal to 0. So the affine transformation can be reduced to linear transformation.
2. For the central map P and the two affine transformations S and T, by constructing a new central map P we find the two affine transformations S and T. If S(?)p(?)T=S(?)p(?)T is established, then the key (S,P,T) equivalent to the private key(S,P,T).
We fix the matrices sets A' and B' to attack the system of HFM-PKC. The matrices number of the set A' is (λ-1)n, and every matrix is aλ×n matrix. The matrices number of the set B' is n, and every matrix is a n×n matrix. The matrices set A' and B' generate vector space are VS(A) and VS(B). To the assumption set A' and B', We select an arbitrary basis RAB=[R1,…,Rλn] in If VS(R([(?)]))=VS(R1,…,Rλn) is established, then we acquire the equivalent private key by finding the coordinates of [(?)] in [R1,…,Rλn]T under. That is to say, when [(?)]=Γ'[R1,…,Rλn]T, the key (A',B',Γ') equivalent to the private key (A,B,Γ),inΓ,Γ∈Fqλn×λn.
3. The HFM-PKC scheme's central equations are pi=(?)γi,j,kxjyk+αi. Some new variables wj,k=xjyk are introduced, whenλ≥2. The new system of equations haveλ·n equations and (λ-1)n2 variables. If the number of linear independent equations is less than(λ- 1)n2, the system of equations need to build new equations by the commutativity of multiplication by higher relinearization. For generalized BMQ equations with (?)0 equations and (?)0 variables, the higher relinearzation will produce an increasing number of linear equations. In addition, when the system's variables more than 240 over the finite Fq, the degree i relinearization requires the space cost (?) log2 q. Under the case of degree i relinearzation, even though we obtain (?)=(?) also the system of equations can't be solved. If n is large enough ,to contrast the number of new variables ,the space that the degree i relinearization required shows exponential growth. The required space and time is very larger that is infeasible in solving the HFM-PKC cryptosystem.
4. By the method of fixing variables y = (y1 ,…,yn ), we have a proper approach to solve HFM-PKC equations. The central equations p(x,y) derive from the space So the equation x(?)y=(x1y1,…x1yn,…x(λ-1)ny1,…,x(λ-1)nyn)∈Fq(λ-1)n2 have a zero vector and (q(λ-1)n-1)(qn-1)/(q-1) non-zero vectors. For different x=0 or y=0 , the solutions to the M Equations are 0, qn-1, q(λ-1)n-1, respectively. Especially for givenα∈ρ(M) andα≠0, there are not less than q -1 equivalent solutions. Because the space which the vector x derive from is greater than the space of y, we fix the variables y. Let y =y0 ,then the HFM-PKC central equations become a system ofλn polynomials in (λ- 1)n variables with maximum degree 1. By exhausting the vector y , we can solve the HFM-PKC central equations. For the system of HFM-PKC, the variables isλn and it equals the equations. The number of solutions are q-1 . The successful probability is q -1/qn-1≈1/qn-1 by exhausting the vector y to attack the system HFM-PKC. So we are easy to know that the attack is infeasible to the appropriate parameter.
本文首先给出以多变元二次方程组为基础的陷门构造方法。其次介绍HFM-PKC的公钥设计方案和加解密过程实现,同时分析其求解难度,证明了此公钥密码体制是NP完全问题。本文主要工作是对HFM-PKC方案的抗攻击性进行分析：首先通过差分分析证明了作用于HFM-PKC方案中心映射之上的仿射变换均可以被简化为线性变换。其次通过多项式同构攻击验证HFM-PKC方案的安全性。最后通过重线性化和指定变量法分析证明HFM-PKC在方程数量和变元数量相同时安全强度最大。
The advent of the Public-Key Cryptosystem is of epoch-making significance for the development of the cryptology. Because the encryption and decryption keys are different, so it can provide data encryption and signature authentication. However, the rapid development of computing power at the program on the security of public key cryptography presented a huge challenge. In particular, the emergence of quantum computing will inevitably lead to collapse of the current public key cryptography. Find a good public-key cryptosystem to against quantum attack is of cryptography to solve the pressing problems.
The trapdoor is based on the difficulty in solving a system of Multivariate Quadratic Polynomials Equations over finite fields. The central map must be easy to invert and the two affine transformations S and T are invertible affine transformation over the finite field F.In particular, these two affine transformations are used to hide the internal structure of the central equations. There are different public key cryptographic schemes for every the central map. such as MIA, HFE. UOV and so on.
HFM-PKC public key cryptography scheme is a special case of MQ problem and it is a NP-complete problem. The scheme haveλ·n equations andλ·n variables x= (x1,x2,…,x(λ-1)n)∈Fq(λ-1)n,y=(y1,y2,…,yn)∈Eqn. The scheme's public key is (Fq,ρ=[ρ1 (v),ρ2(v),…ρλn(v)]) and the private key is (A,B,S,T). In my paper, there are four methods are used to analysis the HFM-PKC scheme.
1. By the research on differentials cryptanalysis I arrive at a conclusion that the HFM-PKC scheme can't resist the difference value's attack. To known the difference value,Δv= (δ1,δ2,…δ(λ-1)n,δ1',…δn') forΔv∈Fλn, The system of Multivariate Quadratic Polynomials Equations of HFM-PKC can be solved in polynomial time. In additional, the affine transformation S(x). we haveρ(v)= S(?)P=P(Sv+S0) and deduce further that v=S-1 (x-S0)=S-1x-S-1S0. However, if the v0 exactly equal to -S-1S0, we can getΔv=S-1x. In order to let the coefficients of the linear equations which include (δ1,δ2,…δ(λ-1)n,δ1',…δn) equal to 0, we didρ1(v0+Δv)-ρ1(v0). There areλ·n equations andλ·n variables' linear equations must exist a nonzero solution, that is, the coefficient matrix |A| equal to 0. So the affine transformation can be reduced to linear transformation.
2. For the central map P and the two affine transformations S and T, by constructing a new central map P we find the two affine transformations S and T. If S(?)p(?)T=S(?)p(?)T is established, then the key (S,P,T) equivalent to the private key(S,P,T).
We fix the matrices sets A' and B' to attack the system of HFM-PKC. The matrices number of the set A' is (λ-1)n, and every matrix is aλ×n matrix. The matrices number of the set B' is n, and every matrix is a n×n matrix. The matrices set A' and B' generate vector space are VS(A) and VS(B). To the assumption set A' and B', We select an arbitrary basis RAB=[R1,…,Rλn] in If VS(R([(?)]))=VS(R1,…,Rλn) is established, then we acquire the equivalent private key by finding the coordinates of [(?)] in [R1,…,Rλn]T under. That is to say, when [(?)]=Γ'[R1,…,Rλn]T, the key (A',B',Γ') equivalent to the private key (A,B,Γ),inΓ,Γ∈Fqλn×λn.
3. The HFM-PKC scheme's central equations are pi=(?)γi,j,kxjyk+αi. Some new variables wj,k=xjyk are introduced, whenλ≥2. The new system of equations haveλ·n equations and (λ-1)n2 variables. If the number of linear independent equations is less than(λ- 1)n2, the system of equations need to build new equations by the commutativity of multiplication by higher relinearization. For generalized BMQ equations with (?)0 equations and (?)0 variables, the higher relinearzation will produce an increasing number of linear equations. In addition, when the system's variables more than 240 over the finite Fq, the degree i relinearization requires the space cost (?) log2 q. Under the case of degree i relinearzation, even though we obtain (?)=(?) also the system of equations can't be solved. If n is large enough ,to contrast the number of new variables ,the space that the degree i relinearization required shows exponential growth. The required space and time is very larger that is infeasible in solving the HFM-PKC cryptosystem.
4. By the method of fixing variables y = (y1 ,…,yn ), we have a proper approach to solve HFM-PKC equations. The central equations p(x,y) derive from the space So the equation x(?)y=(x1y1,…x1yn,…x(λ-1)ny1,…,x(λ-1)nyn)∈Fq(λ-1)n2 have a zero vector and (q(λ-1)n-1)(qn-1)/(q-1) non-zero vectors. For different x=0 or y=0 , the solutions to the M Equations are 0, qn-1, q(λ-1)n-1, respectively. Especially for givenα∈ρ(M) andα≠0, there are not less than q -1 equivalent solutions. Because the space which the vector x derive from is greater than the space of y, we fix the variables y. Let y =y0 ,then the HFM-PKC central equations become a system ofλn polynomials in (λ- 1)n variables with maximum degree 1. By exhausting the vector y , we can solve the HFM-PKC central equations. For the system of HFM-PKC, the variables isλn and it equals the equations. The number of solutions are q-1 . The successful probability is q -1/qn-1≈1/qn-1 by exhausting the vector y to attack the system HFM-PKC. So we are easy to know that the attack is infeasible to the appropriate parameter.
引文
[1]Bauer F L著.密码编码和密码分析：原理与方法[M].吴世忠等译.北京：机械工业出版社.2001-9：5-158.
[2]刘嘉勇,任德斌，方勇等编著.应用密码学[M].北京：清华大学出版社,2008.：41-171.
[3]杨波.现代密码学.北京：清华大学出版社.2003.
[4]William Stallings(美)著,孟庆树,王丽娜,傅建明等译.密码编码学与网络安全：原理与实践[M].北京：电子工业出版社,2006.
[5]卢官明.李海波,刘莉.生物特征识别综述[J].南京邮电大学学报.2007.2.27(1)：81-87.
[6]Okamoto T, Tanaka K, Uchiyama S. Quantum public-key cryptosystems:proceeding of the 20th Annual International Cryptology Conference on Advances in Cryptology, Stanta Barbara,California, USA, August 20-24,2000[C]. Berlin:Springer,2000.
[7]曾贵华.量子密码学[M].北京：科学出版社,2006.
[8]肖国镇,卢明欣.DNA计算与DNA密码[J].工程数学学报,2006-2,23(1)：1-5.
[9]Lai, X. et al. Asymmetric encryption and signature method with DNA technology[J]. SCIENCE CHINA Information Sciences,2010,53(3):506-514.
[10]赵永哲.隐藏有限域上遍历矩阵的公钥密码[J].通信学报, 2009.
[11]赵永哲.隐藏域上遍历矩阵的公钥加密改进方法及签名方案[P].中国,200910174731.2010-01.
[12]Aviad Kipnis, Adi Shami. Cryptanalysis of the HFE public key cryptosystem by relinearization [C]. Advances in Cryptology CRYPTO'99, LNCS 1666, Berlin:Springer, 1999:19-30.
[13]Nidolas Courtois, Alexander Klimov, Jacques Patarin etc. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations[C]. Advandes in Cryptology. EUROCRYPT 2000:International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium. May 14-18,2000:392-407.
[14]Aviad Kipnis. Adi Shamir. Cryptography[M]. ACM3, Chapter 4 "Hidden Monomial Cryptosystems", Springer-Verlag,1998:80-102.
[15]Aviad Kipnis, Adi Shami. Cryptanalysis of the Oil and Vinegar Signature Scheme[C]. Advances in Cryptology CRYPTO'98. LNCS 1462. Berlin:Spring,1998:257-266.
[16]Pierre-Alain Fouque, Louis Granboulan, and Jacques Stern. Differential cryptanalysis for multivariate schemes[C]. In Proc. Advances in Cryptology-EUROCRYPT 2005,2005: 341-353.
[17]Eli Matsui, Adi Shamir. Differential Cryptanalysis of the Data Encryption Standard[M]. London:Springer-Verlag,1993.
[18]Christopher Wolf, Bart Preneel. Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations[DB/OL]. http://eprint.iacr.org/2005/077.
[19]Jacques Patarin. Hidden Field Equations (HFE) and Isomorphisms of Polynomials(IP): two new families of Asymmetric Asymmetric Algorithms[C]. Advances in Cryptology-Eurocrypt'96, international conference on the theory and application of cryptographic techniques, Saragossa, Spain, May 12-16,1996:33-48.
[20]Jacques Patarin. Louis Goubin, Nicolas T. Courtois. Improved algorithms for isomorphism of polynomials[C]. In Kaisa Nyberg (editor), Advances in cryptology——EUROCRYPT'98. international conference on the theory and application of cryptographic techniques, Espoo. Finland. May 31-June 4,1998:184-200.
[21]Willi Geiselmann, Willi Meier, Rainer Steinwandt. An Attack on the Isomorphism of Polynomials Problem will one Secret[DB/OL]. http://eprint.iacr.org/2002/143.
[22]华罗庚,数论导引[M].北京：北京科学出版社.1957：1-83.
[23]Behrouz A.Forouzan著.密码学与网络安全[M].马振晗,贾军保译.北京：清华大学出版社,2009.
[24]张禾瑞.近世代数基础[M].北京：高等教育出版社.1978：1-182.
[25]Jintai Ding, Bo-Yin Yang. Multivariate public key cryptography[C]. In:Daniel J. Bernstein. Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer, Berlin. ISBN 978-3-540-88701-0.2009:193-242.
[26]Christopher Wolf. Multivariate quadratic polynomials in public key cryptography. [DB/OL]. http://eprint.iacr.org/2005/393.
[27]Oded Goldreich著.密码学基础[M].温巧燕,杨义先译.北京：人民邮电出版社, 2003-9.
[28]Garey, M.R. and Johnson, D.S. Computers and Intractability-A Guide to Theory of NP-Completeness[M]. San Francisco:W. H. Freeman and Company.1979.
[29]Nicloas T Courtois. Higher Order Correlation Attacks, XL algorithm and Cryptanalysis of Toyocrypt[C]. In information security and cryptology—ICISC 2002:182-199.
[30]Xijin Tang and Yong Feng, A new efficient algorithm for solving systems of multivariate polynomial equations[R], Cryptology ePrint Archive. Report 2005/312,2005.
[2]刘嘉勇,任德斌，方勇等编著.应用密码学[M].北京：清华大学出版社,2008.：41-171.
[3]杨波.现代密码学.北京：清华大学出版社.2003.
[4]William Stallings(美)著,孟庆树,王丽娜,傅建明等译.密码编码学与网络安全：原理与实践[M].北京：电子工业出版社,2006.
[5]卢官明.李海波,刘莉.生物特征识别综述[J].南京邮电大学学报.2007.2.27(1)：81-87.
[6]Okamoto T, Tanaka K, Uchiyama S. Quantum public-key cryptosystems:proceeding of the 20th Annual International Cryptology Conference on Advances in Cryptology, Stanta Barbara,California, USA, August 20-24,2000[C]. Berlin:Springer,2000.
[7]曾贵华.量子密码学[M].北京：科学出版社,2006.
[8]肖国镇,卢明欣.DNA计算与DNA密码[J].工程数学学报,2006-2,23(1)：1-5.
[9]Lai, X. et al. Asymmetric encryption and signature method with DNA technology[J]. SCIENCE CHINA Information Sciences,2010,53(3):506-514.
[10]赵永哲.隐藏有限域上遍历矩阵的公钥密码[J].通信学报, 2009.
[11]赵永哲.隐藏域上遍历矩阵的公钥加密改进方法及签名方案[P].中国,200910174731.2010-01.
[12]Aviad Kipnis, Adi Shami. Cryptanalysis of the HFE public key cryptosystem by relinearization [C]. Advances in Cryptology CRYPTO'99, LNCS 1666, Berlin:Springer, 1999:19-30.
[13]Nidolas Courtois, Alexander Klimov, Jacques Patarin etc. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations[C]. Advandes in Cryptology. EUROCRYPT 2000:International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium. May 14-18,2000:392-407.
[14]Aviad Kipnis. Adi Shamir. Cryptography[M]. ACM3, Chapter 4 "Hidden Monomial Cryptosystems", Springer-Verlag,1998:80-102.
[15]Aviad Kipnis, Adi Shami. Cryptanalysis of the Oil and Vinegar Signature Scheme[C]. Advances in Cryptology CRYPTO'98. LNCS 1462. Berlin:Spring,1998:257-266.
[16]Pierre-Alain Fouque, Louis Granboulan, and Jacques Stern. Differential cryptanalysis for multivariate schemes[C]. In Proc. Advances in Cryptology-EUROCRYPT 2005,2005: 341-353.
[17]Eli Matsui, Adi Shamir. Differential Cryptanalysis of the Data Encryption Standard[M]. London:Springer-Verlag,1993.
[18]Christopher Wolf, Bart Preneel. Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations[DB/OL]. http://eprint.iacr.org/2005/077.
[19]Jacques Patarin. Hidden Field Equations (HFE) and Isomorphisms of Polynomials(IP): two new families of Asymmetric Asymmetric Algorithms[C]. Advances in Cryptology-Eurocrypt'96, international conference on the theory and application of cryptographic techniques, Saragossa, Spain, May 12-16,1996:33-48.
[20]Jacques Patarin. Louis Goubin, Nicolas T. Courtois. Improved algorithms for isomorphism of polynomials[C]. In Kaisa Nyberg (editor), Advances in cryptology——EUROCRYPT'98. international conference on the theory and application of cryptographic techniques, Espoo. Finland. May 31-June 4,1998:184-200.
[21]Willi Geiselmann, Willi Meier, Rainer Steinwandt. An Attack on the Isomorphism of Polynomials Problem will one Secret[DB/OL]. http://eprint.iacr.org/2002/143.
[22]华罗庚,数论导引[M].北京：北京科学出版社.1957：1-83.
[23]Behrouz A.Forouzan著.密码学与网络安全[M].马振晗,贾军保译.北京：清华大学出版社,2009.
[24]张禾瑞.近世代数基础[M].北京：高等教育出版社.1978：1-182.
[25]Jintai Ding, Bo-Yin Yang. Multivariate public key cryptography[C]. In:Daniel J. Bernstein. Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer, Berlin. ISBN 978-3-540-88701-0.2009:193-242.
[26]Christopher Wolf. Multivariate quadratic polynomials in public key cryptography. [DB/OL]. http://eprint.iacr.org/2005/393.
[27]Oded Goldreich著.密码学基础[M].温巧燕,杨义先译.北京：人民邮电出版社, 2003-9.
[28]Garey, M.R. and Johnson, D.S. Computers and Intractability-A Guide to Theory of NP-Completeness[M]. San Francisco:W. H. Freeman and Company.1979.
[29]Nicloas T Courtois. Higher Order Correlation Attacks, XL algorithm and Cryptanalysis of Toyocrypt[C]. In information security and cryptology—ICISC 2002:182-199.
[30]Xijin Tang and Yong Feng, A new efficient algorithm for solving systems of multivariate polynomial equations[R], Cryptology ePrint Archive. Report 2005/312,2005.