Cryptography Reference
In-Depth Information
The secret transformation which is used in order to hide the super-increasing
property is simply a multiplication by a secret key modulo
M
.
Here is the cryptosystem.
Public parameter
: an integer
n
.
Key generation
: choose a super-increasing sequence (
b
1
,...,
b
n
,
b
n
+
1
=
M
), an
Z
∗
M
, and a permutation
integer
W
∈
π
of
{
1
,...,
n
}
.
Compute
a
i
=
Wb
π
(
i
)
mod
M
for
i
=
1
,...,
n
.
Public key
:
K
p
=
(
a
1
,...,
a
n
).
Secret key
:
K
s
=
(
b
1
,...,
b
n
,
,
,π
M
W
).
=
m
1
···
Message
: a binary sequence
m
m
n
of length
n
.
Encryption
:
c
=
m
1
a
1
+···+
m
n
a
n
.
Decryption
: compute
cW
−
1
mod
M
, solve the super-increasing knapsack prob-
cW
−
1
lem
x
1
b
1
+···+
x
n
b
n
=
mod
M
and let
m
i
=
x
π
(
i
)
.
Unfortunately, this cryptosystem was broken a few years later by Adi Shamir (see
Ref. [164]). As it was explained later, the security of the Merkle-Hellman cryptosystem
does not rely on the full genericity of the NP-complete problem, but on some particular
instances which are not necessarily hard. Indeed, the problem can be solved if we can
find a small vector in a related lattice.
Mathematically, a lattice is a discrete subgroup of
R
n
. More intuitively, it is the
set of all linear combinations of some given constant vectors, but with only integral
coefficients. Finding a small vector (in the sense of Euclidean norm) in a lattice is
known to be a hard problem, but which might be easy in many cases. Namely, the
famous LLL algorithm can be used to reduce lattices and break cryptosystems like the
Merkle-Hellman one.
5
9.3
Rivest-Shamir-Adleman (RSA)
The first public-key cryptosystem which is still secure and used was invented by Ronald
Rivest, Adi Shamir, and Leonard Adleman, the initials of whom led to the name of
the cryptosystem: RSA. It was published in 1978 as Ref. [158] in the journal
Commu-
nications of the ACM
. Since then, this algorithm has been adapted, generalized, and
transformed into several standards. Surprisingly, as it will be seen, although the plain
RSA cryptosystem was not broken, many adaptations and standards based on RSA are
weak. This raises all the ambiguity of public-key cryptosystems.
9.3.1 Plain RSA Cryptosystem
As depicted in Fig. 9.7, here is how the
plain RSA
algorithm works. (By plain RSA we
mean a theoretical algorithm. As it will be seen, this algorithm is not directly usable
5
A survey by Nguyen and Stern on lattices in cryptography is available as Ref. [139].
Search WWH ::
Custom Search