##
Knapsack Crypto System

Posted in Cryptography by #care-crew

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 "a_{0}...a_{n}". 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.

**the knapsack procedure**
//Receiver generates public key
1) Generate random, but ascending numbers: a_{0}...a_{n-1};
2) Choose a number: m with m > the sum of a_{0}...a_{n-1};
3) Choose a number: b (must be coprime with m);
4) Calculate and publish: (aa_{0} mod m,...,aa_{n-1} mod m) = (w_{0},...,w_{n-1});
//Sender ciphers message
5) Calculate and publish: s = the sum of x_{i}w_{is}; //x is the message in bits
//Receiver deciphers s
6) Calculate: b*s = b*sumof(x_{i}*w*_{i} = sumof(x_{i}a_{i};

**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(a_{i}x_{i}); //x_{i} {0,1}, a_{i} in N and not 0
A grid L(b_{1},...,b_{n+1}) with b as columns represents the problem:
If one finds a x_{1},...,x_{n} for -sumof(a_{i}*x*_{i} + s = 0. Then the sumof x_{i}b_{i}+b_{n+1} = (x_{1},...,x_{n},0 //vector
Because this often works, the security of the knapsack crypto system is vulnerable.

Published at 2011-10-25, Updated at 2011-10-25

next: ElGamal Crypto System
prev: Diffie Hellman Key Exchange