Cryptography Reference
In-Depth Information
With
that
amount of inventive talent, you might think that cryptologists should
certainly have found other methods! Well, they have, and one such story is
worth being told.
Two years after the first asymmetric algorithm was published by Diffie and Hell-
man, Merkle and Hellman proposed another method, the so-called
knapsack
algorithm
. It takes much less background knowledge than RSA to under-
stand it.
The knapsack problem is mathematically formulated like this: let a number be
a sum, where the summands are taken from a given set of summands. This
can be expressed in more culinary terms: several yummy slices of different
thickness and the same diameter are placed on a table. Pack some of the slices
in a certain cylindrical knapsack (with the width of the slice diameter) such
that the knapsack is filled up to the rim. Which slices have to be packed?
The problem is not always solvable, and when it is, the result is not always
unambiguous. We are mainly interested in making its solution generally difficult
for large knapsacks. We say purposefully 'general', because the summands are
very easy to find for specific number sequences. One such number sequence
is, for instance,
1, 2, 4, 8, 16, 32, ...
For example, the representation of 13 as the sum of such numbers can even be
read from right to left from its representation as a binary number (dual number)
in this case. The following holds:
13 = 1101
2
so we choose the first, third, and fourth members of the sequence above:
13=1+4+8
Solving the knapsack problem becomes generally simple if each summand in
the ascending sequence of the given set of summands is greater than the sum
of all previous summands. Such knapsacks are said to be
superincreasing
.
