通信学报 ›› 2015, Vol. 36 ›› Issue (6): 60-65.doi: 10.11959/j.issn.1000-436x.2015182

• 学术论文 • 上一篇    下一篇

新扩展多变量公钥密码方案的安全性分析

聂旭云1,2,刘波1,鲁刚3,钟婷1   

  1. 1 电子科技大学 信息与软件工程学院,四川 成都 611731
    2 中国科学院信息工程研究所 信息安全国家重点实验室,北京 100093
    3 电子科技大学 计算机科学与工程学院,四川 成都 611731
  • 出版日期:2015-06-25 发布日期:2017-05-11
  • 基金资助:
    国家重点基础研究发展计划(“973”计划)基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目

Cryptanalysis of novel extended multivariate public key cryptosystem

Xu-yun NIE1,2,Bo LIU1,Gang LU3,Ting ZHONG1   

  1. 1 School of Information and Software Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
    2 State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China
    3 School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
  • Online:2015-06-25 Published:2017-05-11
  • Supported by:
    The National Natural Basic Research Program of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要:

新扩展多变量公钥密码方案是乔等提出的一种多变量公钥密码体制的安全性增强方案。该方案引入了一个非线性“温顺变换”,试图隐藏原始方案的弱点,如线性化方程。然而,分析表明,若原始方案满足线性化方程,则改进方案必然满足二次化方程。给定公钥,在找到所有的二次化方程之后,将要破解的合法密文代入到二次化方程中,可以得到关于明文变量的二次方程。这降低了要求解的方程组的次数。结合Groebner基方法,可以快速地恢复合法密文相应的明文。

关键词: 多变量公钥密码系统, 二次化方程, 线性化方程, 温顺变换, 代数攻击

Abstract:

The novel extended multivariate public key cryptosystem is a new security enhancement method on multivariate public key cryptosystems,which is proposed by Qiao,et al.A nonlinear invertible transformation was used,named“tame transformation”,on the original multivariate public key cryptosystem to hide its weakness such as linearization equation.However,it is found that if there are many linearization equations satisfied by the original MPKC,there would be many quadratization equations (QE) satisfied by the improved scheme.Given a public key,after finding all QE,a valid cipheretext can be substituted into the QE to derive a set of quadratic equations on the plaintext variable.This exactly reduce the degree of the system wanted to solve.Then the corresponding plaintext can be recovered for a given valid ciphertext combining with Groebner basis method.

Key words: multivariate public key cryptosystems, quadratic equations, linear equations, tame transformation, algebraic attack