New Knapsack Public Key Cryptosystem

Network and information security is becoming a country's political,military, economic and social life of the normal operation of the foundation. It will be a comprehensive national strength of the important embodiment. And cryptography is the core of information security. Public key cryptography is to separate the encryption key and the decryption key or encryption function and the decryption function. Users retain only decryption key,while encryption keys and encryption function together made public. Public key cryptography is an important part of cryptography.The knapsack public-key like the RSA is one of the well-known public key system. In particular the knapsack public-key is based on the knapsack problem. It is a NP-hard problem. Although the break was mode soon,in the improve of knapsack public-key system there are some which is proven to be safe. The knapsack problem is the first cryptography system which use the NP problem to the public-key cryptography. And the others at the application of public-key cryptography are based on factorization or discrete number issues. They are not the structural problems of the NP. So the research of knapsack public-key system is very meaningful.From the commonly used knapsack attacking method ,finds the reasons for the break,proposes new thought against the break,and makes use of non-super-increasing knapsack sequence construct the knapsack system. There are two prominent problems of using non-super-increasing sequence to construct knapsack scheme: encryption result is not unique and the difficulty of decipher. This article analysis one of the congruence multi-mode knapsack sequence,use it to construct a knapsack scheme, proves that the L sequence can solve the above two problems and propose a plan to use the L sequence to construct a new knapsack public-key system. To speed up the encryption and decryption speed,The article also propose the reverse construction algorithm of m and w-1. Finally this article give the stimulant implementation of non-super-increasing knapsack scheme.