Non-super-increasing Knapsack Public-key Scheme

Data encryption techniques are the core of modern network security technology. Because public cryptosystem technology was separated the relations between the key of encryption and the key of decryption, it has advantageous for the key management, could use in authentication and digital signature which conventional encryption cryptosystem was unable to accomplish. So public cryptosystem technology plays huge role in electronic business and electronic government affairs. The MH knapsack scheme is one of the first proposed public schemes, although it was broken soon after its proposed. Some improved schemes were proposed immediately, but most of them are proved to be insecure. Therefore some are proved to be secure so far. So the reason of secure and the their constructions are worth of studying. Nowadays, the public cryptosystems, which are in real applications, base on Integer Factorization problem and Discrete Logarithm problem that are not NP problems. With the development of computer science, these problems may dissolve in Polynomial time in the future. Knapsack cryptosystems are first attempt of use NP-Complete problem in public cryptosystem, so seek and design a secure knapsack scheme has the significance extremely. This paper proceeds with the secure knapsack cryptosystems, analyses their constructions and secure factors, obtains a conclusion that the Morii-Kasahara scheme and the Naccache-Stern scheme are the identical scheme in fact; and analyses the common attacking method to knapsack cryptosystem,seeks the reason how the trapdoors were found. Though those concrete analysis, it is proposed a new method to construct knapsack scheme, which is use non-super-increasing sequence in this paper. 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. It is analyzed a kind of coding sequence of a pseudo-prime's general formula and nature at large,then modify it to a new sequence –simplified sequence S. After prove simplified sequence S can conquer the two problem mentioned above, and use it to construct a knapsack scheme, unifies the specific programming experiment, It is also analyses the security of non-super-increasing knapsack scheme in this paper. At last, this paper give the stimulant implementation of non-super-increasing knapsack scheme.