Knapsack Crypto System

Posted in Cryptography by

The Knapsack Crypto System is based on the subset sum problem. It is easy to learn, but is not secure, cause the subset sum problem is broken.

knapsack You have a empty knapsack "s" and want to fill it as good as possible with elements "a0...an". It is possible to find out by trial and error, but once you find one solution you can find more solutions. There is no unique solution. knapsack

the knapsack procedure //Receiver generates public key 1) Generate random, but ascending numbers: a0...an-1; 2) Choose a number: m with m > the sum of a0...an-1; 3) Choose a number: b (must be coprime with m); 4) Calculate and publish: (aa0 mod m,...,aan-1 mod m) = (w0,...,wn-1); //Sender ciphers message 5) Calculate and publish: s = the sum of xiwis; //x is the message in bits //Receiver deciphers s 6) Calculate: bs = bsumof(xiwi = sumof(xiai;

break the knapsack crypto system It is not needed to trial and error to find a possible key, because of the LLL-Algorithm from Adi Shamir. the statement of the problem is: s = sumof(aixi); //xi {0,1}, ai in N and not 0 A grid L(b1,...,bn+1) with b as columns represents the problem: knapsack grid If one finds a x1,...,xn for -sumof(aixi + s = 0. Then the sumof xibi+bn+1 = (x1,...,xn,0 //vector Because this often works, the security of the knapsack crypto system is vulnerable.

Published at , Updated at 2011-10-25

next: ElGamal Crypto System prev: Diffie Hellman Key Exchange