Discuss with an example how knapsack is used in cryptography.

250views

written 7.8 years ago by

teamques10 ★ 64k

• modified 7.8 years ago

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

enter image description here

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.

ADD COMMENT EDIT