Cryptography Reference
In-Depth Information
that such attacks are not yet known, but that they may exist and be found at some
point in time in the future). Consequently, they suggested hashing a message
m
onto
the full domain
Z
n
(of the RSA function) before signing, and they constructed and
proposed a corresponding
full-domain-hash
(FDH) function
}
∗
→
Z
n
.
h
FDH
:
{
0
,
1
The function is understood to hash arbitrarily sized strings “uniformly” into
Z
n
. In either case, the FDH signature of
m
is the digital signature for
h
FDH
.
Assuming that
h
FDH
is ideal (i.e., it behaves like a random function) and RSA is a
trapdoor permutation, the security of the FDH DSS can then be shown in the random
oracle model. In [6], Bellare and Rogaway improved the FDH DSS and proposed the
PSS and the PSS-R. These are the secure DSSs that are addressed next. We elaborate
on the PSS and the PSS-R constructions for the RSA DSS. Similar constructions for
the Rabin DSS can be found in [6]. In either case, standardization efforts related to
the PSS and PSS-R are underway in several forums, including, for example, ANSI
X9F1, IEEE P1363, ISO/IEC JTC1 SC27, and PKCS.
15.3.1
PSS
The PSS is a DSS with appendix. In its RSA version, the PSS
Generate
algorithm is
the same as the RSA key generation algorithm. On input of a security parameter,
it outputs a signing key (
n, d
) and a corresponding verification key (
n, e
).The
PSS is further parametrized by
k
0
and
k
1
, which are both numbers between 1 and
k
=log
n
1 (typically,
k
=1
,
024 and
k
0
=
k
1
= 128). In addition, the PSS
Sign
and
Verify
algorithms make use of two hash functions
h
and
g
.
−
k
1
is called the
compressor
.Ithashes
arbitrarily long bit sequences to sequences of
k
1
bits.
}
∗
→{
•
The hash function
h
:
{
0
,
1
0
,
1
}
•
The hash function
g
:
{
0
,
1
}
k
1
→{
0
,
1
}
k−k
1
−
1
is called the
generator
.Let
g
1
be the function that on input
w
∈{
0
,
1
}
k
1
returns the first
k
0
bits of
g
(
w
),
k
1
returns the remaining
and let
g
2
be the function that on input
w
∈{
0
,
1
}
k
−
k
0
−
k
1
−
1 bits of
g
(
w
).
For the security analyis in the random oracle model, we must make the as-
sumption that
h
and
g
are ideal, meaning that they behave like random functions. For
all practical purposes, however,
h
and
g
must be implemented with cryptographic
hash functions.
The PSS
Sign
algorithm is specified in Algorithm 15.3 and illustrated in Figure
15.1 (note that the figure only illustrates how the message is prepared for the RSA
