Rijndael算法的代数方程系统改进

The Improvement on Algebraic System of Multivariate Quadratic Equations for Rijndael

该文根据Rijndael算法中S盒的代数表达式，通过合理假设S盒变量，利用各变量之间的关系建立方程，把Rijndael加密算法描述成GF（2^8）上的一个多变量二次方程系统。该二次方程系统是稀疏的且是超定（0Verdefined）的，可以认为恢复Rijndael的密钥等同于求解这个方程系统。与其他描述Rijndael密码的方程系统相比，该文中描述S盒方程的项数与变量更少，因此用XSL（eXtended Sparse Linearization）技术求解该系统的计算复杂度更低。

According to the algebraic expression of the S-box in Rijndael algorithm, an algebraic system of multivariate quadratic equations over GF（2） are proposed to describe Rijndael. The variables of S boxes are supposed rationally and the relations between these variables are used to establish equations in this paper. The derived system of multivariate quadratic equations is sparse and overdefined. The key recovery of Rijndael can be regarded as a problem of solving this system. By comparing with other parallel systems, this system has fewer terms and variables. So it has a lower complexity while applying the XSL （eXtended Sparse Linearization） technique.