Paper 2009/537

Cryptanalysis of two knapsack public-key cryptosystems

Jingguo Bi, Xianmeng Meng, and Lidong Han

Abstract

In this paper, we cryptanalyze two knapsack cryptosystems. The first one is proposed by Hwang et al [4], which is based on a new permutation algorithm named Permutation Combination Algorithm. We show that this permutation algorithm is useless to the security of the cryptosystem. Because of the special super increasing structure, we can break this cryptosystem use the method provided by Shamir at Crypto'82. The second one is provided by Su et al [16], which is based on the elliptic curve discrete logarithm and knapsack problem. We show that one can recover the plaintext as long as he solve a knapsack problem.Unfounately, this knapsack problem can be solved by Shamir's method or the low density attack. Finally, we give a improved version of Su's cryptosystem to avoid these attacks.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
bijingguo-001 @ 163 com
History
2009-11-05: received
Short URL
https://ia.cr/2009/537
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/537,
      author = {Jingguo Bi and Xianmeng Meng and Lidong Han},
      title = {Cryptanalysis of two knapsack public-key cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2009/537},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/537}},
      url = {https://eprint.iacr.org/2009/537}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.