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 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:
- 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
- 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 Merkle-Hellman 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 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:
- 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)