Cryptography Reference
In-Depth Information
2
k
the ciphertext is, again, rejected as invalid. If just one of the
two roots, say
y
1
,is
<
these roots is
2
k
then
y
2
is discarded and the computations involving
y
2
in the following steps are omitted (or performed as dummy computations for
security reasons as explained below). So we may assume that
y
1
,
<
2
k
.
y
2
<
4. Viewing
y
1
,
y
2
as
k
-bit strings, write
y
1
=
x
1
||
r
1
and
y
2
=
x
2
||
r
2
, where
x
1
,
x
2
∈
l
+
s
0
and
r
1
,
s
1
.
{
0
,
1
}
r
2
∈{
0
,
1
}
5. Compute
v
1
:=
x
1
⊕
H
(
r
1
)
and
v
2
:=
x
2
⊕
H
(
r
2
)
.
l
and
t
1
,
s
0
.
6. Write
v
1
=
m
1
||
t
1
and
v
2
=
m
2
||
t
2
, where
m
1
,
m
2
∈{
0
,
1
}
t
2
∈{
0
,
1
}
7. For
i
and if this condition holds for either
neither or both values of
i
, then reject
c
as an invalid ciphertext.
8. Let
i
=
1
,
2, test whether
t
i
=
G
(
m
i
||
r
i
)
be the unique index for which the condition in the preceding step
holds. The output of
Dec
is
m
i
.
∈{
1
,
2
}
Remarks 8.12
As in the case of RSA-OAEP, the functions
G
H
are modeled as
independent randomoracles and, as we will indicate below, this allows the attainment
of a strong security property. In practice, these functions can be thought of as collision
resistant hash functions and, in the implementation below, we will use SHA-256 to
derive them in a similar way as in RSA-OAEP.
Observe also that, in Definition 8.15, the result of encoding the message
m
,
∈
l
by means of SAEP
+
is the
k
-bit string
y
obtained in step 5 of the encryption
algorithm.
5
When viewed as an element of
{
0
,
1
}
Z
n
,
y
is an integer of at most
k
bits and
this is helpful in the decryption algorithm because, as already remarked, it means that
y
Z
n
obtained in step 3 of
the decryption algorithm and these square roots are matched in pairs
<
/
n
2. This integer is one of the four square roots of
c
in
±
y
1
mod
n
and
±
y
2
mod
n
, where exactly one member of each pair is
<
n
/
2. Thus the two square
roots of
c
in
2 may be automatically discarded, as is done
in step 3. It may be the case that only one of the four square roots is smaller than
n
Z
n
that are greater than
n
/
/
2
5
Once again, we see the difference between encoding and encrypting: SAEP
+
encodes messages
into a specific format and Rabin-SAEP
+
encrypts them.