一种基于Grobner基的代数攻击方法

Algebraic Attack Method Based on Grobner Basis

代数攻击能够有效分析出分组密码中的密钥值,Grobner基能够快速求解多变量高次方程组。该文提出一种基于Grobner基的代数攻击方法,用超定代数方程组描述Rijndael加密算法,采用项序转换算法FGML将次数反字典序转化为字典序,使算法能够在已知少量明密文对的情况下对密钥进行求解,通过设计合理的项序和方程组解的判定降低算法复杂度。

Algebraic attack is an efficient cryptanalysis method. Grobner basis technique can be applied to solve systems of polynomial equations in several variables. This paper introduces a new efficient algebraic attack based on Grobner basis, describes Rijndael encryption by an extremely sparse overdefined multivariate quadratic system over GF（2）, and converts degree reverse lexicographic order into lexicographic order with conversion algorithm FGLM. By reasonable designed order and solution set judgment, the complexity of Grobner basis attacks is efficiently reduced. Grobner basis attack can recover the full cipher key requiring only a minimal number of plaintext/ciphertext pairs.