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

ADD COMMENTlink
modified 3.0 years ago  • written 3.0 years ago by gravatar for Ramnath Ramnath3.7k
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

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.

ADD COMMENTlink
modified 3.0 years ago  • written 3.0 years ago by gravatar for Ramnath Ramnath3.7k
Please log in to add an answer.