Cryptography Reference
In-Depth Information
The Knapsack Method
Creating keys
:
•
Choose a secret superincreasing number sequence with a length of
N
mem-
bers, (
s
i
)
i
=
1
,...,N
, i.e., a number sequence in which each element is greater
than the sum of all previous elements.
N
should be at least equal to 200; the
s
i
should be of the order of 10
100
.
•
Choose a secret module,
n
, greater than the sum of all elements of the number
sequence.
•
Choose a secret number,
k
, relatively prime to
n
.
Compute
k
by
kk
=
1 mod
n
.
•
•
Multiply all elements of (
s
i
)by
k
modulo
n
:
t
i
=s
i
k mod n
(i=1,...,N).
Sequence (
t
i
)
i
=
1
,...,N
forms the public key;
k
,
n
, and sequence (
s
i
)
i
=
1
,...,N
compose the private key.
•
Encryption
:
•
Decompose the plaintext into blocks of
N
bits each (the last block does not
have to be padded).
•
For each block, compute the sum from those
t
i
, where bit
i
in the block is
equal to 1. The sum is the ciphertext.
Decryption
:
•
Decompose the ciphertext into
N
-bit blocks.
•
Multiply each ciphertext block by
k
modulo
n
.
•
Solve the knapsack problem for each number thus obtained with regard to
(
s
i
) by successively subtracting the largest possible
s
i
from the sequence. If
summand
s
i
occurs in the sum, then set bit
i
in the plaintext block to 1;
otherwise set it to 0.
Figure 4.19:
Asymmetric encryption using the knapsack method.
