代数攻击是一种重要的密码分析技术,主要利用密码体制的代数性质及现有代数系统求解方法来攻击密码体制。它可以用于攻击流密码、分组密码及多变量密码等体制。常见的代数攻击方法有两类：Grobner基方法和XL (eXtended Linearization)方法。本文对求解F[x,y]上理想的约化Grobner基的算法及Mutant-based Grobner Basis algorithm(MGB)算法进行了改进与实现,主要工作如下：(1)证明了单项式序为字典序时,多项式组G经过约化和多项式排序后,如果其中相邻的元素之间的S-多项式被G除得的余式都为零,那么G就是理想<G>的Grobner基。我们知道当理想的单项式序为分级逆字典序时是最容易计算出其Grobner基。改进的算法利用这两个单项式序的优点,通过在计算过程中改变单项式序,使得S-多项式的计算次数大幅减少,最终正确有效地计算出F[x,y]上理想的Grobner基。最后随机选取了几组多项式,与著名的F4算法进行了对比。实验结果显示,改进的算法比F4算法更快,甚至快上一个数量级,而且可以求解出陈银东等的算法不能求解的案例。(2)发现了MGB算法不能正常终止和不能正确计算出Grobner基的案例,并分析其原因,改进的算法利用继续扩展“已满”分区、更为细致地分区扩展等方法来克服这两点缺陷。MGB算法忽略了上轮产生的但在Enlarge步骤未被选取的mutants多项式,改进的算法发现继续使用这些多项式对求解Grobner基的速度大有裨益。最后利用代入消元法对MGB算法进行了改进。在MGB算法中,可能会产生一次多项式,改进的算法利用这些一次多项式来消去多项式方程组P中的一些变量。在不增加多项式次数的同时,减少了变量和多项式的个数,达到了降低算法复杂度的目的。同样实现了此改进算法,并用它和MGB算法攻击HFE密码体制,攻击结果显示,改进算法比MGB复杂度更低。