Research On The Knapsack Cryptosystem

Since 1978, Merkle and Hellman first proposed the MH knapsack cryptosystem, until 1990s, knapsack ciphers are public key cryptosystem of the most popular research direction and cryptography circles think it is the most promising cipher algorithm. It and the RSA public key system are considered as the two most promising public key system.The public key cryptosystem is very suitable for the encryption of computer systems and distributed control, nowadays, it has become the focus of computer cryptography research in the world, compared with public key cryptosystem based on knapsack cryptosystem and public key cryptosystem, with the characteristics of fast solution. Although the super knapsack has a considerable security risk, and most of the existing knapsack problem is broken, because of its own encryption and decryption speed, easy hardware implementation, and many other advantages, some scholars who have a passion for knapsack cryptography are still continuing to explore and research, trying to find a more secure and fast knapsack public key cryptography algorithm.The topic of this thesis is about the safety and efficiency of the knapsack problem. A detailed study and Analysis on the public key encryption system of knapsack problem is carried out, on the basis of the original, the existing knapsack cipher encryption algorithm is improved. In this paper, some new knapsack cipher schemes are proposed, the implementation of these schemes can not only improve the security of the knapsack system, at the same time, it can keep the advantage of the knapsack system, finally through the C language code to achieve the algorithm.The main work of this paper includes the following aspects:1. Research on the public key encryption system of knapsack problemKnapsack cipher based on knapsack problem (KP) is the first public key system. The general knapsack problem is a combinatorial optimization of NP complete problem. Knapsack problem can be described as:given a set of items, each item has its own weight and price, in a limited total weight, how we choose, in order to make the highest total price of goods. The solution method can be summarized for exact and approximation algorithms, which exact algorithms, have dynamic programming method, backtracking, branch and bound method etc., approximation algorithm with genetic algorithm, greedy algorithm, particle swarm optimization algorithm, ant colony algorithm. Due to the time complexity and the space complexity of the exact algorithm, the approximate algorithm is used to solve the knapsack problem in recent years.Knapsack public key sequence and the general random sequence are different, the knapsack public key sequence is generated by the initial sequence through the trap door function, and the illegal decryption is not know the initial sequence. We can put the initial sequence to a knapsack public key sequence process as an encryption process, initial sequence as plaintext, trapdoor function for encryption algorithm, knapsack public key sequence cipher, speaking from the computational complexity, if initial sequence to public key sequence process is seen as there is no security risk, then from the public key of reverse solving initial sequence of depression of gate function inverse process) can be regarded as impossible, the algorithm of time and space complex is great, so put the knapsack problem into a NPC problem, corresponding, the algorithm will is seen as a worthwhile use of public key algorithm.The main problem of knapsack cipher is their security problem. Since Merkle and Hellman proposed the first public key cryptography scheme based on knapsack problem, researchers have designed a lot of cryptographic schemes based on knapsack problem. This kind of scheme is vulnerable to Shamir attacks and low density attacks. The new knapsack public key cryptosystem designed to resist these attacks has been a hot topic in the research of public key cryptography.2. A new knapsack cryptosystem design, namely 3.1 programsWe construct a new knapsack cryptosystem, essentially re-select a trapdoor function, or adding one or more trapdoor function in the original basis. This paper chooses a new trapdoor function, that generates a random super increasing sequence A,choose the number (Q,R),and satisfies Q > R and Q and R are relatively prime, using (Q,R), A super increasing sequence disguised as a sequence of two B, satisfy the condition:bi=「Qai/R」。From bi encrypts a plaintext to ciphertext.That knows the private key to decrypt the original super increasing sequence A,simply be relation bi=[Qai/R] inverse transform,that is,from bi to ai is derived from the realization of plaintext to ciphertext is derived,namely the decryption operation.KEY GENERATIONS(1) Choose randomly super increasing sequence A=(a1,…,an);(2) Choose randomly (Q,R), Q>R so Q and R prime number;(3) (A,Q,R)compute B=(bi,…,bn),tnen bi=[Q·ai/R];(4) Public Key is B, Private key is (A,Q,R).ENCRYPTION(1) Plaintext x=(x1,…,xn)∈{0,1}n,Receiver’s public key B=(b1,…,bn);(2) Ciphertext sents to receiver.DECRYPTION(1) Receiver compute S=[R·C/Q];(2) Then:For each possible value for r,so by SA=S+r,(A,SA)solving x=(x1,…,xn),if you can find a legitimate x,then it is added to the set of candidate solution X;(3) If X is the empty set, no solution; if X is only one solution, then x is plaintext; otherwise, can only determine x∈X, this time can be uniquely identified by means of authentication plaintext x。(4) Therefore, in the decryption process need taking into account errors of , if you can find the upper and lower limits of error, it is able to ensure the accuracy of decryption。 If you can find on the lower error, you can decrypt ensure accuracy. Through the program 3.1 Examples of tests to verify the feasibility of the scheme.3. Improvement of Program 3.1, namely Program 4.1.Program 3.1 has a disadvantage, there are relationship between the size of B and A, if bi<bj,certainly has ai<aj. Therefore, if A is a super increasing, B is also likely to be super increasing, which causes the program easily cracked. This can further improve the original Program; the idea is to add a modular multiplication Transform program 3.1 on the basis of the improved Program as described in Program 4.1。KEY GENERATIONS(1) Randomly selected super increasing sequence A=(a1,…,an.);(2) Choose randomly ,0<W<M so gcd(M,W)=1；(3) Compute A’=(a’1:,…,a’n),then a’i+W·ai(mod M);(4) Choose randomly (Q,R), Q>R so Qand R prime number;(5) (A’,Q,R)compute B=(b1,…,bn),then bi=[Q·a’i];(6) Public Key B, Private key (A,Q,R,M)。ENCRYPTION(1) Plaintext x=(x1,…,xn)∈{0,1}",receiver’s public key B=(b1,…,bn.);(2) Ciphertext C= sent to receiver。DECRYPTION(1) Receiver compute then(2) For each possible value of r,so by S’A=S+r,(A,SA)compute SA=W-1·S’A(mod M),resolving x=(x1,…,xn)if you can find a legitimate x,then it is added to the set of candidate solution X；(3) If X is the empty set, no solution; if X is only one solution, then plaintext is x; otherwise, can only determine x∈X, this time can be uniquely identified by means of authentication plaintext x。Above is improvement of programs 3.1, Practical application may also be converted to an additional program 4.1 similar to one of the MH program.4. Improvement of MH program namely program 5.1MH Program attack analysis, we can see the main attack for super increasing sequence knapsack for their private key and public key transform modular multiplication, of "super increasing" feature that can not be effectively shielded cause. If in some way to the first private knapsack super increasing conversion, so that no longer has transformed knapsack super increasing Properties, and then converted to the analog multiplication, and so would allow for MH program of attacks on the new program is invalid. But such improvements difficulty lies:on private property knapsack super increasing "sabotage" should not lead to the decryption cannot be that the destruction must be recoverable. Here is an improved Program.KEY GENERATIONS(1) Choose randomly δ=(δ1,…,δn)∈{0,1)n;(2) Optionally super increasing knapsack A=(r<a1,a2,…,an);(3) Choose randomly 0<W<M such as gcd(M,W)=1；(4) △=|M/2|, cmpute B=(b1,…,bn),then bi=W(ai+δi·△)(mod M)(i=1,…,n);(5) Public key B, Private Key (A,δ)。ENCRYPTION(1) Plaintext x=(x1,…,xn)∈{0,1}";(2) CiphertextDECRYPTION(1) Compute S’=W-1S(mod M): (2)(3) For each possible value of 0≤r’≤r, let SA=(5’-r’)(modM) respectiVely and SA=(S’-△-r’)(modM), Then solved x=(x1,…,xn)by(A,SA),If you can find a legitimate x,Then it is added to the set of candidate solution X;(4) If X is the empty set, no solution; if X is only one solution, then x is plaintext; otherwise, can only determine x∈X, this time can be uniquely identified by means of authentication plaintext x.5. Analysis of the program application mode, implementation and verification.In this paper, according to the characteristics of each program, analyzes its application mode:in practical application must "probability" of transformation to determine the algorithm, namely in the encryption algorithm introduced a "random", in order to make each encrypt the same plaintext can get different ciphertext. The specific method is to add redundant information before encryption, or add redundant information to the encrypted information, the filling should be random, in order to generate a non deterministic encryption algorithm.This paper uses the C language program to achieve the various algorithms, and gives the key implementation code, thus achieving the algorithm validation algorithms, and gives the key to the code, enabling the verification of the algorithm.