论文部分内容阅读
代数攻击是现代密码学中的一种攻击方法,其主要方法就是利用代数系统的良好性质及求解方法来攻击现存的密码学系统,目前被认为是最具潜力的攻击方法之一。而求解有限域上的多变元二次方程是代数攻击的热点之一,因为该类方程在密码学中有着众多应用,AES（高级加密标准）可以用稀疏的超定的多变元二次方程来描述,而且近年来提出了很多基于多变元二次方程的密码学系统如HFE公钥密码系统等 目前,在国内外求解该类方程一般有两种方法,一种就是Groebner基方法以及它的变种,据我们所知,最高效的一个变种为F4,另一种就是XL方法以及它的变种,像XSL,FXL。但是这两种方法都有着明显的缺点,首先是效率差,用上述两种方法求解多变元二次方程问题时,Groebner基方法的时间复杂度理论上为双指数,实际运行时间为单指数;XL方法的时间复杂度对于一般的情况是双指数的,对非常超定的问题才是多项式的。另外一个缺点是时间复杂度难以度量,由于上诉两种方法都要达到一定条件才能终止算法,但是何时能达到条件不能预先判断,造成时间复杂度难以度量。对于稀疏的系统,Groebner基方法能够受益于系统的稀疏性,但是复杂度难以度量而且效率也不理想,XL更是不能利用系统的稀疏性,因为它没有乘积因子的选择策略. 在现代计算机代数领域中,求解多项式的非线性方程组一般有三种方法,分别为Groebner基方法,吴方法和结式方法。Dixon结式作为结式方法中最为有效的一种结式,受到了众多学者的关注,它被广泛地应用于代数几何和几何定理机器证明中。在使用过程中Dixon结式显示了效率高,时间复杂度容易度量及充分利用系统稀疏性的优点。但是这样一种优秀的算法却没有被引入备受关注的代数攻击领域。基于这种现状,本文把Dixon结式引入到代数攻击领域中来,并提出了一种新的算法DR来求解有限域上多变元多项式二次方程系统。其基本思想为对于MQ问题,把x1,x2,…,xn-1当作变元,而把xn作参数,然后利用和改进扩展Dixon结式方法求解该类系统。并且分析了该算法对于一般情况的复杂度,并且提供强有力的实验证据对于某些稀疏问题新算法的复杂度很有可能是多项式的。实验结果都表明对于m=n的一般和稀疏的问题DR效率优于已有的两种算法。除了高效性,新算法还具有复杂度容易度量,计算时间可以