Cryptography Reference
In-Depth Information
For the solution with such knapsacks, we only have to subtract the largest
possible element from the sum to successively obtain the set of summands
looked for.
How should we use it for encryption, or even for constructing an asymmetric
encryption algorithm? The trick is to transform the superincreasing knapsack
into a normal one. To this end, we choose a
secret
superincreasing number
sequence, (
s
i
)
i
=
1
,...,N
, from
N
numbers. We then define a
secret
module,
n
,
and a
secret
factor,
k
. The module should be greater than the sum of all
s
i
numbers, and
k
should be relatively prime to
n
. We multiply the given
s
i
summands by
k
modulo
n
. This results in different summands,
t
i
,t
i
=
s
i
k
mod
n
. The
t
i
compose the
public
key.
If you want to encrypt, you represent your message as a bit sequence. You
decompose this bit sequence into
N
-bit blocks. For each block, you compute
the sum of all
t
i
, for which the
i
th bit in the block is equal to 1. This is the
ciphertext.
But since we know
n
and
k
, we can use
kk' = 1 mod n
to determine a
k
.
Multiplying the ciphertext by
k
modulo
n
gives us those values that would have
resulted had we used the superincreasing sequence for encryption. This problem
is easy to solve. It's how we reveal the bits of the plaintext (Figure 4.19).
Except for finding
k
and doing the modulo
n
multiplication, we need no number
theory at all. The rest is almost school arithmetic, and the implementation is
extremely easy, compared with RSA. Beautiful, isn't it?
Because of this question, you already may have a hunch that the algorithm
is
too
beautiful. Though some flaws were found, nobody was initially able
to crack the entire algorithm. At the CRYPTO '82 conference in California,
however, several cryptanalysts claimed they had achieved it. Their attack might
have consisted in transforming the 'public knapsack' into the superincreasing
knapsack (this is actually jargon; we are talking of disks
=
summands that are
packed in the knapsack rather than of the knapsack
=
sum itself).
In light of these claims, a ciphertext decryption challenge was published as early
as on the first night. All lecturers expounded theoretical problems, but the riddle
