PENG Liqiang, ZUO Jinyin, HU Lei, XU Jun. Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences[J]. Chinese Journal of Electronics, 2014, 23(1): 175-178.
Citation: PENG Liqiang, ZUO Jinyin, HU Lei, XU Jun. Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences[J]. Chinese Journal of Electronics, 2014, 23(1): 175-178.

Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences

Funds:  This work is supported by the National Basic Research Program of China (No.2013CB834203), the National Natural Science Foundation of China (No.61070172, No.10990011), the Strategic Priority Research Program of Chinese Academy of Sciences (No.XDA06010702).
  • Received Date: 2012-11-01
  • Rev Recd Date: 2013-03-01
  • Publish Date: 2014-01-05
  • Two knapsack public key cryptosystems based on randomized knapsack sequences were proposed in 2009 and 2011 respectively, where the secret knapsack sequence is transformed by secret modular linear transforms into one or three public randomized knapsack sequences with appropriate density. In this paper, we recover the secret modular linear transforms by simultaneous Diophantine approximation and propose secret key recovery attacks on these two cryptosystems. Practical attack experiments are done within one minute.
  • loading
  • R.C.Merkle, M.E. Hellman,"Hiding information and signatures in trapdoor knapsack", IEEE Transaction on Information Theory, Vol.24, No.5, pp.525-530, 1978.
    A. Shamir,"A polynomial-time algorithm for breaking the basic Merkle-Hellman", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp.145-152, 1982.
    J.C. Lagarias, A.M. Odlyzko,"Solving low-density subset sum problems", Journal of the ACM (JACM), Vol.32, No.1, pp.229246, 1985.
    M.J. Coster, A. Joux, B.A. La Macchia, A.M. Odlyzko, C.P. Schnorr, J. Stern,"An improved low-density subset sum algorithm", Computational Complexity, Vol.2, No.2, pp.111-128, 1992.
    Y. Murakami,"A new construction of knapsack PKC by using a random sequence", Global Telecommunications Conference, Hawaii, USA, pp.1-6, 2009.
    Y. Murakami, M. Kasahara,"A differential knapsack publickey cryptosystem", 2011 6th International Conference on Computer Sciences and Convergence Information Technology, Seogwipo, Korea, pp.613-617, 2011.
    A.J. Menezes, P.C. van Oorshot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, pp.117-122, 1996.
    A.K. Lenstra, H.W. Lenstra, L. Lovász,"Factoring polynomials with rational coefficients", Mathematische Annalen, Vol.261, No.4, pp.515-534, 1982.
    D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, Kluwer Academic Publishers, Boston, Massachusetts, pp.11-14, 2002.
    P. Zhang, J. Yu, T. Wang,"A homomorphic aggregate signature scheme based on lattice", Chinese Journal of Electronics, Vol.21, No.4, pp.701-704, 2012.
    W. Bosma, J. Cannon, C. Playoust,"The magma algebra system I: The user language" Journal of Symbolic Computation, Vol.24, No.3, pp.235-265, 1997.
    J. Xu, L. Hu, S. Sun,"Implicit polynomial recovery and cryptanalysis of a combinatorial key cryptosystem", 14th International Conference on Information and Communications Security, Hong Kong, China, pp.45-57, 2012.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (219) PDF downloads(977) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return