Let us assume that we need to use the following weights: SIK = {1, 7, 9, 18, 50,

ID: 665194 • Letter: L

Question

Let us assume that we need to use the following weights: SIK = {1, 7, 9, 18, 50, 86} as private key. Answer the following three questions:

(a) Assume modulus n=175, and multiplier m=27. Find the public key (i.e., set of weights out of SIK based on n and m).

(b) Based on the previous public key, can you encrypt the number 25. Assume number is to be represented as six bit. Show detailed calculation.

(c) Suppose, that you receive 129 for the above public and private knapsack crypto system. Show detailed steps to decrypt the message.

(a)

step 1: generate superincreasing knapsack (SIK), which is already given, SIK = {1,7,9,18,50,86}

step 2: n>sum of SIK (175>171, which is true)

step 3: public key is General Knapsack (GK), SIK.m (mod n)

1.27(mod 175) = 27

7.27(mod 175) = 14

9.27(mod 175) = 68

18.27(mod 175) = 136

50.27(mod 175) = 125

86.27(mod 175) = 47

Therefore, Public Key = (27,14,68,136,125,47) , n=175

(b)

25 = 011001

(27*0 + 14*1 + 68*1 + 136*0 + 125*0 + 47*1) = (14 + 68 +47)

= 129

Therefore, encrypted number is 129

(c)

For decrypt calculate private key = m-1 mod n

=27-1 mod 175

=13

Therefore, Private Key = 13

To decrypt 129, S

129.13 = S (mod 175)

obtain plain text = 011001

Therefore, decrypted message = 25

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.