Cryptography Reference
In-Depth Information
and then we know that this is the SAEP
+
-encoded plaintext but a potential source of
ambiguity remains as it may happen that two of these square roots are
<
/
2.
This ambiguity could be entirely removed if the encoded messages were restricted
to have Jacobi symbol equal to 1 because, as shown in Remarks 8.10, only one
square root of
c
which is less than
n
n
2 satisfies this property. This would be easy to
accomplish in this scheme for it would suffice to try with different random seeds
r
at encryption, until finding one such that the Jacobi symbol of the encoded message
y
is 1. However, this would make encryption less efficient and hence the preferred
solution is the one applied in the decryption algorithm above: when two square roots
remain after step 3, apply steps 3-7 to both of them until the correct one is found
in step 7. Here is where the potential ambiguity mentioned above may surface as
it is possible that a valid ciphertext is rejected because the other root also satisfies
the condition tested in this step, i.e.,
t
i
/
=
G
(
m
i
,
r
i
)
holds for both
i
=
1 and
i
2. However, it is easy to see that the probability of this occurring by chance
is negligibly small for reasonable values of the parameter
s
0
. Indeed, if
y
1
is the
root that corresponds to the correct plaintext, this happens whenever
G
=
t
2
which, assuming that
G
behaves as a random oracle and taking into account that
both terms in the equality are
s
0
-bit strings, occurs with probability 2
−
s
0
. Since
s
0
is
typically taken to be
(
m
2
,
r
2
)
=
≥
128 (and we will take
s
0
=
256 in our implementation), this
is a low probability indeed.
We might also wonder whether a malicious encryptor can create a valid ciphertext
that is rejected in step 7 but, as pointed out in [34], a similar argument shows that,
under the random oracle assumption, the encryptor would have to spend expected
time
O
2
s
0
(
)
to complete this task and so this would be infeasible in practice for
reasonable values of
s
0
.
It is also important to point out that one should be very careful with the messages
informing of decryption errors. As mentionedwhen discussing the implementation of
RSAES-OAEP, these messages may make possible a CCA attack based, for example,
on timing analysis that may allow an attacker to distinguish whether the rejection
was produced in step 2, step 3 or step 7 of the decryption algorithm. Because of
this, in the implementation of Rabin-SAEP
+
below, we will carry out steps 4-7 of
the algorithm even if the ciphertext is already detected as invalid in step 2 or step 3,
and we will delay outputting any invalid ciphertext error message until step 7 of the
decryption algorithm is completed.
8.4.3.2 The Security of Rabin-SAEP
+
Rabin-SAEP
+
is an especially interesting public-key encryption scheme because it
fares well in both security and efficiency. From Boneh's results that we are going
to explain, it seems that this scheme is preferable to RSA-OAEP from the security
point of view and the only aspect in which the latter scheme is (slightly) superior is
the fact that it allows the encryption of longer messages for a given modulus size.
The security properties of Rabin-SAEP
+
can be summed up by saying that it is
a CCA secure scheme under the factoring assumption in the random oracle model.
