Question: Discuss with an example how knapsack is used in cryptography.
0

Mumbai University > Information Technology > Sem6 > System and Web Security

Marks: 10M

Year: May 2015

 modified 3.3 years ago  • written 3.3 years ago by Ramnath • 3.8k
0
• Knapsack is an asymmetric-key cryptosystem which requires two keys for communication: public key and private key.
• In knapsack public key is used only for encryption and private key is used only for decryption.
• The underlying mathematical problem is the subset sum problem which can be stated as follows: ‘Given which elements from a predefined set of numbers are in knapsack, it is easy to calculate the sum of the numbers; if the sum is given (Known),it is difficult to find which elements are in the knapsack.’

• We can define the knapsack problem as follows:

Let S = ($S_1,S_2…………,S_n$) be a predefined set and

X = ($X_1,X_2…………., X_n$)be a 0-1 vector in which Xi is either 0 or 1.

The sum of the elements in knapsack is given as

T = knapsackSum(S, X) = $X_1S_1 + X_2S _2+………….…+X_nS_n$.

• The search problem is to find the vector(X1,X2,……………….,Xn).

• Given knapsackSum(S,X) it is easy to find T but given T and S it is difficult to find X which is inverse of knapsackSum(T,S).

• Super-increasing sets

i. It is easy to find knapsackSum and its inverse if the sets S is super increasing.

ii. A set of sizes is said to be super-increasing if each term is greater than or equal to the sum of all previous elements.

i.e $S_i ≥S_1 +S_2 +………..+S_{i-1}$

iii. For e.g. 3,7,12,30,60,115 is a super increasing set whereas 3,5,7,9,11 is not. Run time complexity of the subset sum problem is O (n).

• The algorithm for knapsack and its inverse is given as follows:

Algorithm

• Example: Let’s consider S = [3, 7, 12, 30, 60,115] and T=82. To find the vector X?
i Si T T ≥ Si Xi T,T – Si * Xi
6 115 82 No 0 T←82 -,115 * 0 = 82
5 60 82 Yes 1 T←82 – 60 * 1 = 22
4 30 22 No 0 T←22 – 30 * 0 = 22
3 12 22 Yes 1 T←22 – 12 * 1 = 10
2 7 10 Yes 1 T←10 – 7 * 1 = 3
1 3 3 Yes 1 T← 3 – 3 * 1 = 0
• So, the vector X = [1,1,1,0,1,0]

• Merkle-Hellman Knapsack cryptosystem

• Consider Vivek and Arun want to communicate with each other.

i. Generation of key

a. Let t = t1,t2,………..tn be a super-increasing set of values.

b. Choose a prime p such that p > t1 + t2 +……..+ tn and a number b with 1 < b < p.

c. Arun calculates his public set of sizes,Si = b * ti mod p.

d. The public key is S and private key is t,b and p.

ii. Encryption Process

a. Vivek encrypts the message X using T = knapsackSum(X,S) algorithm.

b. Vivek then sends T as ciphertext to Arun.

iii. Decryption Process

When Arun receives T from Vivek,he does the following:

a. Calculates T’ = $b^{-1}$ * T mod p.

b. Uses X’ = inverse_knapsackSum(T’,t).

c. Permutes X’ to find X which is original plaintext.