多变量公钥密码的发展过程

多变量公钥密码的开展过程摘要：多变量公钥密码系统作为一种可替代RSA和ECC的可以抵抗量子攻击的公钥密码体制，是近几年的研究热点。这种体制的平安性基于在有限域上求解多变量多项式方程组是NP-困难问题。关键词：多变量公钥密码，代数攻击1引言众所周知，传统的密码体制如RSA和ECC，他们的平安性基于数论困难问题和离散对数问题的困难性。但是，量子计算机的开展对基于数论问题的密码体制的平安性造成了本质威胁，因为在量子计算机上存在着在多项式时间内求解数论问题的方案。因此有必要去寻找更高效、更平安的公钥密码体制来代替传统密码体制。多变量公钥密码系统将会是一种可能的选择。多变量公钥密码的平安性是建立在求解有限域上随机多变量多项式方程组是NP-困难问题的根底之上。多变量公钥密码的加密效率非常高，且能抵抗量子攻击，因此成为近几年的研究热点。目前已经构造出了多种多变量公钥密码体制，其中有一些非常适用于计算能力有限的低耗设备上。2003年，一种多变量签名体制，SFlash，被欧洲NESSIE密码方案接受用于低耗智能卡的推荐算法。2多变量公钥密码的一般形式多变量公钥密码〔multivariatepublickeycryptosystem，MPKC〕的一般形式如下。令是一个有限域，和是正整数，和分别是和上的随机选取的可逆放射变换。取映射为一个从到的容易求逆的非线性映射。令，其中是一个到的映射。它总可以被表示成有限域上个元多项式，其最高次数等于的次数。在多变量公钥密码系统中，的表达式设为公钥，它是一组多变量多项式，而私钥设为和的表达式。多变量密码设计的关键在于构造映射，后者称为多变量密码的中心映射。为了节省公钥多项式的存储，中心映射和公钥多项式通常选取为最简单的非线性函数，即二次函数。3MPKC的构造现有的MPKC体制大致分为四类：1、MI；2、隐藏域方程〔HFE〕；3、油醋机制；4。、三角形机制。下面我们简单的介绍这几种体制。3.1MI密码体制MI加密体制是Matsumoto和Imai在1988年提出的。它是第一个使用“小域-大域〞思想来构造多变量公钥密码体制的方法。它的公钥是小域上的多元多项式，而它的中心映射可以用的扩域〔大域〕上的单项式来表示。令是特征为的有限域，是的次扩域。在MI体制中，域上的元素与中的向量通过线性同构等同看待，即我们取在上的一组基，定义为，其中。MI的中心映射首先定义在域上，形式如下：，其中满足和。这个条件是确保了是个可逆函数。事实上，假设是一个满足的整数，那么可简单的表示为。通过映射，不难将看成是从到自身的映射，即。3.2HFE密码体制在破解了MI加密体制后，Patarin将MI体制的中心映射作了推广，提出了“隐藏域方程〞体制。HFE的中心映射不再是一个大域上的单项式，而是一个多项式。HFE加密体制的中心映射定义在域上，形式如下：，其中系数为随机选取的，限定和是为了满足的次数小于某个参数的需求。HFE的解密需要在域上求解，这可以用Berlekamp算法的变型算法来求解。假设，那么这一步骤的复杂度为。因此，不能太大，也就是说和不能太大。3.3油醋机制油醋机制是patarin在1997年根据线性化方程的形式构造出来的签名体制。这个体制的关键是应用了一种所谓的油醋多项式。令是一个含个元素的有限域。定义：设，我们称如下形式的多项式为油醋多项式：，其中，称为油变量，称为粗变量。注意在油醋多项式中，假设给定醋变量的值，那么油醋多项式就转变为关于油变量的一次多项式。油醋签名体制的中心映射就有一组油醋多项式构成。生成签名时只需随机选取一组醋变量的值，然后解一个关于油变量的线性方程组。3.4三角形体制现在的多变量公钥密码体制的构造中，三角形体制是最特殊的一种，因为它们起源于代数几何。驯顺变换方法〔TTM〕密码体制是一类著名的三角形体制，这一体制的动机是基于分解非线性可逆多项式映射的复合的困难性。一类著名的可逆三角形映射是deJonquires映射。一个deJonquires映射的形式如下：，其中是任意域，是任意多项式。这种映射的结构比拟特殊，容易求逆，因而也称为驯顺变换。但是从密码学的观点来看，这种映射不能直接用于构造MPKC，因为它满足线性化方程。T．T．Moh基于这种映射构造了很巧妙的新映射，并将其应用在TTM体制当中。其形式如下：，其中称为锁多项式，它们是次数大于2的多项式，但却是的二次多项式。这种设计是使用锁多项式来隐藏映射中的线性化结构以防止线性化方程的出现。4MPKC的攻击方法现有的针对多变量密码体制的分析工具主要有以下几种：线性化方程、XL算法、Grobner基方法、秩攻击和差分攻击。本节简单介绍这几种攻击方法。4.1线性化方程线性化方程的攻击方法最早是Patarin在1995年攻击MI加密体制时提出的，所以线性化方程有时也称为Patarin关系式。对于一个密码体制，一个线性化方程是一个对任意合法密文及其相应明文的分量成立的如下形式的恒等式：。分析一个多变量密码体制是否存在线性化方程可从理论上直接分析其中心映射的构造是否满足线性化方程，也可以通过计算机试验检测其公钥和明文分量之间是否满足线性化方程。4.2XL算法和Grobner基方法XL算法和Grobner基算法都是解多元多项式方程组的方法，即解方程组。对于一个多变量公钥密码体制，一旦给定公钥和一个合法密文就可以得到一个多元多项式方程组。所以自然就会想到去找一种算法能解一个多元多项式方程组。XL算法是2000年由Courtois等人推广线性化方程方法提出来的解有限域上多元多项式方程组的一种算法。4.3秩攻击秩攻击的出发点是将MPKC的二次公钥多项式用矩阵的形式表示，然后结合中心映射的构造及矩阵的秩来进行密码分析。秩攻击可分为以下三种形式：低秩攻击；高秩攻击；油-醋攻击。4.4差分攻击2005年，Fouque等人引入了差分攻击来分析PMI加密体制。该攻击有计算二次函数的双线性型出发，找到一个明文空间的子线性空间，将公钥限制在这个空间上可使得所有的内部扰动项均变为常数，宠儿可以使用Patarin的线性化方程攻击方法恢复给定合法密文的相应明文。5结论多变量公钥密码被认为是一种有希望替代传统公钥密码的密码体制。但是，随着各种攻击方法的提出，目前大局部多变量公钥密码体制均遭受到不同程度的攻击。因此，有必要去寻找新的方法来设计多变量公钥密码，和寻找新的方法来增强多变量公钥密码的平安性。多变量公钥密码的开展带动了代数攻击方法的开展。代数攻击方法不仅仅可以用于分析多变量公钥密码，还可以用来分析对称密码。对多变量公约密码体制的研究能够使我们熟悉各种代数攻击工具，进一步丰富密码分析方法，推动整个密码学领域的开展。参考文献[1]W.Di±eandM.Hellman.Newdirectionsincryptography.IEEETransac-tionsonInformationTheory,22(6):644{654,1976.[2]R.Rivest,A.Shamir,andL.Adleman.Amethodforobtainingdigitalsignaturesandpublickeycryptosystems.CommunicationsoftheACM,21(2):120{126,1978.[3]P.Shor.Polynomial-timealgorithmsforprimefactorizationanddiscretelogarithmsonaquantumcomputer.SIAMRev.,41(2):303{332,1999.[4]L.Vandersypen,M.Ste®en,G.Breyta,C.Yannoni,M.Sherwood,andI.Chuang.ExperimentalrealizationodShor'squantumfactoringalgorithmusingnuclearmagneticresonance.Nature,414:883-887.2001.[5]O.Goldreich，S.Goldwasser,andS.Halevi.Public-keycryptosystemsfromlatticereductionproblem.AdvancesinCryptology-CRYPTO'97,LNCS,volume1294,pages112-131.Springer,1997.[6]J.Ho®tein,J.Pipher,andJ.Silverman.NTRU:aringbasedpublickeycryptosystem.Algorithmicnumbertheory-ANTSIII,LNCS,volume1423,pages267-288.Springer,1998.[7]R.M