XL算法的冗余分析与改进

针对多变量二次方程组的求解问题,对XL算法的冗余性进行分析与改进。用XL算法扩展方程组存在冗余现象,采用该算法扩展由m个方程构成的n元二次方程组,所得到的新方程组中线性独立方程个数的上界为[mn(n+3)?m(m?3)]/2。基于此,对XL算法进行改进。分析表明,改进后的XL算法能降低求解多变量二次方程组的计算复杂性。

一种改进的XL算法

对XL算法中的方程组约简过程进行改进,提出一种更有效的求解算法。改进算法中充分利用各单项式之间的约束关系对方程组进行约简,消去其中次数较高的单项式。采用分步扩展及约简的思想消去扩展过程中添加的冗余等式,有效降低XL算法的计算复杂度及存储复杂度。此外,改进的算法还可用于构建布尔函数的低次零化子。

T′算法在域GF(2)上的性能研究

代数攻击算法XSL是域GF(2)上求解大规模的多元多项式方程组的有效算法,分析发现XSL中的T′算法不能达到其希望的结束条件Free=T或Free=T-1。给出T′算法的一个真实结束条件和2个变量选择原则,并在原T′算法的基础上增加概率算法和以较大概率估计变量取值。结果表明改进后的T′算法可以简化方程组求解。

流密码代数攻击的研究现状及其展望

介绍了流密码代数攻击方法的基本原理及其实现方法,详细描述了对具有LFSR结构的密钥流生成器的代数分析手段,概括了现有的降低已得方程系统次数的有效方法,对整个代数攻击的计算复杂度的估计进行了全面的分析,最后对流密码代数攻击方法的研究前景进行了展望。

代数攻击流密码之研究

说明了对具有LFSR结构的密钥流生成器的代数分析手段，阐述了代数攻击流密码基本原理及实现方法，概括了现有的降低已得方程系统次数的有效方法，对整个代数攻击的计算复杂度的估计进行了全面的分析研究和改进，最后对流密码的代数攻击方法进行了展望。

解多元方程组问题

求解方程组一般使用线性的方法,当方程组的次数比较高的情况下,解多元方程组的问题是一个困难问题。2000年Shamir等人在欧洲密码学会议上提出了著名的求解低次数非线性方程组的XL算法,为代数攻击的成功奠定了数学基础。本文对该方法进行了介绍。