线性化方程方法破解TTM公钥加密体制  

Linearization Equation Attack on TTM Public Key Cryptosystems

作　　者：刘梦娟[1] 聂旭云[1,2] 胡磊[2] 吴劲[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054 [2]中国科学院研究生院信息安全国家重点实验室,北京石景山区100049

出　　处：《电子科技大学学报》2010年第2期293-297,共5页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(60803133;60973161);高等学校博士学科点专项科研基金(200806140010);信息安全国家重点实验室开放课题

摘　　要：TTM是一类三角形多变量公钥密码体制。该文经过分析2004年的TTM实例发现,该实例中存在大量的一阶线性化方程,而且对于给定的公钥,这些线性化方程都可以通过预计算得到。对于给定的合法密文,可以利用一阶线性化方程攻击方法在219个28域上的运算内找到了其相应的明文。该方法与二阶线性化方程攻击方法相比,恢复明文的复杂度降低了212倍。计算机实验证实了上述结果。TTM is a type of Multivariate public key cryptosystem. By analyzing the instance of TTM proposed in 2004, it can be found that there are many first order linearization equations satisfied by the cipher in this scheme. For a given public key, all first order linearization equations can be found through precomputation. For any given ciphertext, the corresponding plaintext can be found in less than 2^19 operations over a finite field of size 28 by linearization equation attack. This attack reduced complexity of recovering plaintext from 2^31 to 2^19 compare to second order linearization equation attack. The results above are further confirmed by computer experiments.

关 键 词：代数攻击 线性化方程 公钥密码学 三角形体制 TTM 

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