Discuss with an example how knapsack is used in cryptography.

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

Marks: 10M

Year: May 2015

  • 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:


enter image description here

  • 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.

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more