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.
 Start with a list of eight elements:
 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 nonefficient
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:
 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..i1])+random(10)+1
 Now create m and c as above. This time, solve the
problem with
 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?
The MerkleHellman additive knapsack system
 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 MerkleHellman 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 p1 has only small factors:
 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)