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

Algebraic Attack Method Based on Grobner Basis

作　　者：刘连浩[1] 段绍华[1] 崔杰[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2008年第16期157-158,167,共3页Computer Engineering

摘　　要：代数攻击能够有效分析出分组密码中的密钥值,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.

关 键 词：代数攻击 GROBNER基 RIJNDAEL算法 多变元二次方程组 

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]