Lecture 2 in Public key ciphers

5.7 Knapsack Cipher :
Knapsack cipher system is a public key system based on
the so –called Knapsack problem. The Knapsack problem can be
described as follows .The vector A = (a1,a2,a3……..an) consist of
positive integer .The elements of this vector are multiplied by a binary
vector denoted by X=(x1,x2……xn) in which every xi ; i= 1,……..,n
is either 0 or 1 . This results is the sum s :
S=??
n
i
aixi
1
If X and A are given the value of S can be calculated without any
effort . However if S and A are given, it is considerably more difficult
to calculate X. figure 5-3 illustrates the knapsack problem. A
Knapsack filled with a selection of object) from a large set , each
object has a different weight (the elements of a correspond to the
determine which items are in the Knapsack?
In other word is it possible to determine the elements of X ? when A is
sufficiently large (more than 100 elements), it is almost impossible to
calculate X from a given S and A.
Figure (5-3) The knapsack
Lecture 17-18 Part 2 of Chapter 5: Public Key Cipher Systems
2
Now suppose A is selected such that Scan be calculated from X and A
, but the calculation of X given S and A is almost impossible , unless
additional information is available .The vector X would then
represent the plaintext , which would be converted to a cipher text S
with the aid of A. The procedure is performed as follows :
Select two numbers , u and v, which are relatively prime and u > ?aj,
the knapsack vector A (which is a super – increasing sequence) is
transformed to vector B whose elements satisfy :
bi = V ai (mod u) for all values of i :
The vector B is made