Acta Metallurgica Sinica(English letters) ›› 2010, Vol. 17 ›› Issue (4): 80-87.doi: 10.1016/S1005-8885(09)60492-1

• Artificial Intelligence • 上一篇    下一篇

Cryptanalysis of dragon scheme

袁峰1,胡予濮1,王艳2, 欧海文3   

  1. 1. 西安电子科技大学 计算机网络与信息安全教育部重点实验室
    2. 西安建筑科技大学理学院
    3. 北京电子科技学院
  • 收稿日期:2010-04-09 修回日期:2010-07-13 出版日期:2010-08-30 发布日期:2010-08-31
  • 通讯作者: 袁峰 E-mail:fyuan1234@yahoo.cn
  • 基金资助:

    This work was supported by the National Natural Science Foundation of China (60970119,60803149), the Youth Science and Technology Foundation of Xi’an University of Architecture and Technology (QN0831), and the National Basic Research Program of China (2007CB311201).

Cryptanalysis of dragon scheme

YUAN Feng, HU Yu-pu, WANG Yan, OU Hai-wen   

  1. Key Laboratory of Computer Networks and Information Security, Ministry of Education, Xidian University, Xi’an 710071, China
  • Received:2010-04-09 Revised:2010-07-13 Online:2010-08-30 Published:2010-08-31
  • Supported by:

    This work was supported by the National Natural Science Foundation of China (60970119,60803149), the Youth Science and Technology Foundation of Xi’an University of Architecture and Technology (QN0831), and the National Basic Research Program of China (2007CB311201).

摘要:

Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are and

关键词:

cryptography, public key cryptography, polynomials, mapping, multivariate, dragon scheme, algebraic method, cryptanalysis

Abstract:

Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are and

Key words:

cryptography, public key cryptography, polynomials, mapping, multivariate, dragon scheme, algebraic method, cryptanalysis