Cryptography Reference
In-Depth Information
Again, the PSS-R is very efficient and only slightly more expensive than the
basic RSA DSS. So for all practical purposes, there is no reason not to use the PSS
or PSS-R instead of the basic RSA DSS.
15.4
ONE-TIME SIGNATURE SYSTEMS
A
one-time signature system
is a DSS that can be used to digitally sign single
messages. This means that a new verification key is typically required for every
message that is signed (otherwise, it is often the case that digital signatures can be
forged). On one hand, the advantages of one-time signature systems are simplicity
and efficiency (consequently, they are useful in application environments, where
low computational complexity is required). On the other hand, the disadvantages
of one-time signature systems are related to the size of the verification key(s) and
the corresponding key management overhead. If, however, one-time signatures are
combined with techniques to authenticate verification keys, then it is possible to
sign multiple messages with one verification key, and hence the resulting one-time
signature systems become practical.
In 1978, Michael O. Rabin was the first person who proposed a one-time
signature system. The system employs a symmetric encryption system and is far
too inefficient to be used in practice. In 1979, Leslie Lamport proposed a one-time
signature system that is efficient, because it employs a one-way function instead of
a symmetric encryption system and can be used in practice [16].
Let
f
be a one-way function and
m
be a message to be signed. The length of
m
is assumed to be bound by
n
. For example,
n
may be 128 or 160 bits, and any
message longer than this must first be hashed using a cryptographic hash function.
To digitally sign
m
using the Lamport one-time signature system, the signatory must
have a private key that consists of
n
pairs of randomly chosen preimages for
f
:
[
u
10
,u
11
]
,
[
u
20
,u
21
]
,...,
[
u
n
0
,u
n
1
]
Each preimage
u
ij
(
i
=1
,...,n
;
j
=0
,
1) may, for example, be a string of 64
bits. In an efficient implementation, the 2
n
arguments are typically generated using
a PRBG with an appropriate seed. The public key then consists of the 2
n
images
f
(
u
ij
):
[
f
(
u
10
)
,f
(
u
11
)]
,
[
f
(
u
20
)
,f
(
u
21
)]
,...,
[
f
(
u
n
0
)
,f
(
u
n
1
)]
Furthermore, in an efficient implementation, the 2
n
images
f
(
u
ij
) are hashed
to a single value
p
representing a new (master) public key:
