代数攻击是近年来提出的一种密码分析方法,已被应用于流密码、多变量公钥密码、椭圆曲线公钥密码和McEliece公钥密码等的分析中。其核心思想就是把对密码算法的安全性分析转化/规约为一个多元高次方程组的求解问题。一般而言,这个问题是困难的,一类重要的求解算法是通过求解方程组所对应的多变量多项式组的Grobner基来实现的。因此,Grobner基求解算法的效率直接决定了代数攻击的有效性、密码算法的安全性。不仅如此,Grobner基的求解算法已广泛应用于编码理论、物理、生物等其它自然科学领域,所以研究设计高效的Grobner基求解算法是一个十分重要的课题。该文对Grobner求解算法及其在密码函数上的应用进行了深入的研究与分析,概括为以下五个部分。1、首次证明了F5算法的终止性问题。F5算法是求解Grobner基的最快算法之一,其在ISSAC02会议上被提出之后不久便在Crypto03会议上首次被用于攻破了隐藏域方程(HFE)的80比特挑战。然而,任意多项式系统中的F5算法的有限步终止问题在本文之前仍然是一个公开问题。本文根据F5的结构特点,构造了一个通用的F5GEN算法,而F5算法只是我们这一通用算法的一个具体实例。通过证明F5GEN算法的有限步内终止,作为这一结论的一个推论便证明了F5算法的有限步内终止。2、给出一个求解Grobner基的实用算法。从Gao-Volny-Wang(GVW)框架出发,出于对实际应用的考虑,给出一个实例算法,提出算法层次的优化设计方法。同时,还给出一个高效的约化准则。通过实验,该文比较了算法可用的各项准则及策略。结果表明,矩阵型GVW实例在准则和策略的选取上是最优的。同时,矩阵型GVW在某些多项式系统(如,Cyclic系列和Katsura系列多项式系统)下比Buchberger型GVW要快约2-6倍。3、给出齐次F5算法有限步终止的简单证明。提出了一个通用的算法框架,利用重写基的性质证明该框架能在有限步内正确终止。随后,对F5算法的约化操作进行合理的化简,并且对于齐次F5算法,证明了其复杂的选择策略等价于按模序选择。因此,齐次F5算法就能看成该框架的一个特例,从而得到了齐次F5算法有限步内终止的一个更简洁的证明。4、首次证明了非齐次F5的正确终止性。通过比较GVW-Huang-Stroomer (GVWHS)算法和F5算法,发现GVWHS算法在求解某些系统时要比F5算法快一个指数级。首先提出了更通用的算法框架,该框架能够同时模拟GVWHS和F5算法。证明了这一通用算法框架必在有限步内终止,因而,一类算法(包括齐次和非齐F5算法)也在有限步内终止。GVWHS和F5过去被认为两个不同的算法。而我们的工作表明,GVWHS和F5只是在一个框架内应用了不同的模序、选择序以及重写序作为插件的两个算法,因此,只需通过研究我们的这一通用框架就可以得到GVWHS和F5两个算法的更清晰、简洁的结果。实验表明,对于Random-n和HFE-(12,m)系列多项式系统,GVWHS似乎比几种F5算法的实现要快一个指数级。5、给出了一类具有最高次数和最优代数免疫的一阶弹性函数的构造。这个构造方法就是级联相关类中的两个平衡函数。在构造中适当选取平衡函数,这类一阶弹性函数还能达到几乎最优非线性度。与此同时也构造了一类次优代数免疫的一阶弹性函数。