Cryptography Reference
In-Depth Information
Exercise 24.6.8
Suppose the pseudorandom function used to select the square root in
Rabin-Williams signatures is a function of
H
(
m
) rather than
m
. Show that, in contrast to
Exercise
24.6.7
, finding a collision in
H
no longer leads to an algorithm to split
N
.Onthe
other hand, show that if one can compute a preimage for
H
and has access to a signing
oracle then one can factor
N
with probability 1
/
2.
Exercise 24.6.9
Adapt the proof of Theorem
24.6.6
to the case where
H
has full domain
output.
}
∗
→
Exercise 24.6.10
Adapt the proof of Theorem
24.6.1
to the case where
H
:
{
0
,
1
κ
where 2
κ
<N<
2
κ
+
O
(log(
κ
))
.
{
0
,
1
}
24.7 Public key encryption based on RSA and Rabin
To prevent algebraic attacks such as those mentioned in Sections
1.2
and
24.4
it is necessary
to use randomised padding schemes for encryption with RSA. We do not have space to
discuss secure schemes, but we make some general remarks.
Three goals of padding schemes for RSA are: to introduce randomness; to ensure that
algebraic relationships among messages do not lead to algebraic relationships between the
corresponding ciphertexts; to ensure that random elements of
Z
N
do not correspond to valid
ciphertexts (so access to a decryption oracle is not useful).
Bellare and Rogaway [
37
] designed the
OAEP
(Optimal Asymmetric Encryption
Padding) scheme for secure encryption using RSA. We refer to Section 13.2.3 of Katz
and Lindell [
300
], Section 5.9.2 of Stinson [
532
] or Section 17.3.2 of Smart [
513
]for
details. The word “optimal” refers to the length of the padded message compared with the
length of the original message: the idea is that the additional bits in an OAEP padding of a
message are as small as can be.
The security of RSA-OAEP has a complicated history: Shoup [
496
] found a flaw in the
original security proof (though not an attack on the scheme). Shoup also gave a variant of
OAEP (called OAEP+) together with a security proof in the random oracle model. Fujisaki,
Okamoto, Pointcheval and Stern [
198
] were able to give a proof of the security of RSA
using OAEP in the random oracle model by exploiting the random self-reducibility of RSA.
The reader is referred to these papers, and the excellent survey by Gentry [
230
]forthe
details.
Boneh [
69
] has considered a padding scheme (which he calls
SAEP
) that is simpler than
OAEP and is suitable for encrypting short messages with Rabin. Note that the restriction to
short messages is not a serious problem in practice, since public key encryption is mainly
used to transport symmetric keys; nevertheless, this restriction means that SAEP is not an
“optimal” padding. The proof is again in the random oracle model.
Several methods are known for IND-CCA secure encryption based on factoring in the
standard model. Cramer and Shoup [
148
] have given an encryption scheme, using the
universal hash proof systems framework, based on the Paillier cryptosystem. Their scheme
