Cryptography Reference
In-Depth Information
1
/q
S
)
q
S
q
S
, which tends to 1
/
(
eq
S
)forlarge
q
S
(where
e
is (1
2
.
71828
...
). Since a
polynomial-time adversary can only make polynomially many signature queries the result
follows. We refer to Coron [
137
] for all the details.
−
=
One problem with the full domain hash RSA scheme is the major loss of security (by
a factor of
q
S
) in Theorem
24.6.1
. In other words, the reduction is not tight. This can be
avoided by including an extra random input to the hash function. In other words, an RSA
signature is (
s
1
,
s
2
) such that
s
2
≡
s
1
)(mod
N
). Then, when the simulator is asked
to output a signature on message
m
, it can choose a “fresh” value
s
1
and define
H
(
m
H
(
m
s
1
)
=
(
s
2
)
e
(mod
N
) as above. This approach avoids previous queries to
H
(
m
s
1
) with high
probability. Hence, the simulator can answer “standard” hash queries with
yr
e
(mod
N
)
and “special” hash queries during signature generation with
r
e
(mod
N
). This scheme is
“folklore”, but the details are given in Appendix A of Coron [
138
]. The drawback is that the
extra random value
s
1
must be included as part of the signature. The
PSS
signature padding
scheme was designed by Bellare and Rogaway [
38
] precisely to allow extra randomness
in this way without increasing the size of the signature. We refer to [
138
] for a detailed
analysis of RSA signatures using the PSS padding.
Exercise 24.6.2
Give a security proof for the RSA full domain hash signature scheme with
verification equation
H
(
m
s
2
s
1
)
=
(mod
N
).
The above results are all proved in the random oracle model. Paillier [
425
] has given some
evidence that full domain hash RSA and RSA using PSS padding cannot be proved secure
in the standard model. Theorem 1 of [
425
] states that if one has a “black box” reduction
from the RSA problem to selective forgery for a signature scheme under a passive attack,
then, under an adaptive chosen-message attack, one can, in polynomial-time, forge any
signature for any message.
24.6.2 Secure Rabin-Williams signatures in the random oracle model
In this section we give a tight security result, due to Bernstein [
44
], for Rabin signatures. We
assume throughout that
N
=
pq
is a
Williams integer
; in other words, a product of primes
p
≡
3(mod8)and
q
≡
7 (mod 8) (such integers were discussed in Section
24.2.1
). We
κ
is a cryptographic hash function (which will be modelled
as a random oracle) where 2
κ
<N<
2
κ
+
O
(log(
κ
))
.
}
∗
→{
assume that
H
:
{
0
,
1
0
,
1
}
Exercise 24.6.3
Suppose
p
≡
3(mod8)and
q
≡
7 (mod 8) are primes and
N
=
pq
. Then
(
−
p
)
(
−
q
)
(
p
)
1 while (
q
)
)
∗
, there
=
=
=−
=
1. Show that, for any integer
h
∈
(
Z
/N
Z
are unique integers
e
∈{
1
,
−
1
}
and
f
∈{
1
,
2
}
such that
ef h
is a square modulo
N
.
}
∗
one
computes
H
(
m
) and interprets it as an integer modulo
N
(with overwhelming probability,
H
(
m
)
The signature scheme for public key
N
is as follows. For a message
m
∈{
0
,
1
)
∗
). The signer determines the values
e
and
f
as in Exercise
24.6.3
and
determines the four square roots
s
1
,s
2
,s
3
,s
4
satisfying
s
i
≡
∈
(
Z
/N
Z
H
(
m
)
ef
(mod
N
). The signer
