## RCM3720 Cryptography, Network and Computer Security

### Laboratory Class 7: Knapsack cryptosystems

You will need to read in the rcm3720.input file for various necessary procedures.

The subset sum problem

We will first experiment with this problem; creating random lists and adding up elements from them.
• ln:=8
• lst:=[random(10^6) for i in 1..ln]
• m:=[random(2) for i in 1..ln]
• c:=reduce(+,[m.i*lst.i for i in 1..ln])
• subsetsum(lst,c)
• The subsetsum command implements a fairly non-efficient command for attemping to solve the subset sum problem for an arbitrary list.
• Try the above commands, but starting with a length ln of 12. You should find the command is a bit slower this time. Use this command to time it:
• )set messages time on
• Experiment with lengths of 16 and 20. How long does the subsetsum command take for each of these values?

Superincreasing sequences
• Create a superincreasing sequence with
• ln:=8
• lst:=[random(10^6) for i in 1..ln]
• for i in 2..ln repeat lst.i:=reduce(+,[lst.j for j in 1..i-1])+random(10)+1
• Now create m and c as above. This time, solve the problem with
• siSolve(lst,c)
• Now try with larger lengths: 12, 16 and 20, and time the commands each time.
• What can you say about solving the subset sum problem for general and superincreasing lists?

• Create a superincreasing list of length ln 10, and call it a. Create a new number N greater than the sum of all values of a. Check with
• N>reduce(+,[a.i for i in 1..ln])
• Now choose (randomly) a value wN and which is relatively prime to N. Then construct your public key:
• b:=map(x +-> x*w rem N,a)
• Now for an encryption and decryption. Create a random message m as above, and encrypt it to a ciphertext c using the public key b.
• Decrypt it as follows:
• c1:=inv_mod(w,N)*c rem N
• siSolve(a,c1)
• Experiment with longer lists and messages: 12, 16, 20 or even larger.

The Merkle-Hellman multiplicative knapsack system
• Choose a to be the first ten primes, and a large prime p:
• a:=[2,3,5,7,11,13,17,19,23,29]
• p:=6469785001
• Check that p is greater than the product of all elements of a:
• p>reduce(*,[a.i for i in 1..10])
• and that p-1 has only small factors:
• factor(p-1)
• Choose as a primitive root the value 34:
• r:=34
• primitive?(r)\$PF(p)
• and compute the public key:
• b:=map(x +-> discreteLog(r,x)\$PF(p),a)
• Create a message of length 10, and encrypt it using the public key b:
• c:=reduce(+,[m.i*b.i::INT for i in 1..ln])
• Decryption is now done with:
• c1:=powmod(r,c,p)
• factor(c1)