Cryptography Reference
In-Depth Information
the total message length. Although Coppersmith's attack will not work with more
sophisticated padding methods, it is one of the reasons why the value
e
=
3 is not
2
16
recommended for RSA implementations and the value
e
1 is commonly
used instead. For the latter value of
e
this attack is unsuccessful if a modulus of
reasonable size is being used.
Coppersmith's attack suggests that the padding length for RSA should not be too
small in comparison with message length. Suppose that
=
+
is a function such that
(
1 and that the plain RSA encryption scheme defined in Definition 8.12
is modified as follows:
k
)
≤
2
k
−
Gen
: As in Definition 8.12, on input 1
k
•
it outputs a public key
pk
=
(
n
,
e
)
and a
private key
sk
=
(
n
,
d
)
such that len
(
n
)
=
2
k
.
}
(
k
)
,a
•
Enc
: On input a public key
pk
=
(
n
,
e
)
and a message
m
∈{
0
,
1
2
k
−
(
k
)
−
1
random string
r
←{
0
,
1
}
is chosen and the output is the ciphertext
e
mod
n
c
:=
(
r
||
m
)
∈ Z
n
(where
r
||
m
is interpreted as the element of
Z
n
given
by its binary expansion).
•
Dec
: On input a private key
sk
=
(
n
,
d
)
and a ciphertext
c
∈ Z
n
, the message
c
d
mod
n
m
)
∈ Z
n
is computed, where
LSB
x
denotes the function
that assigns to an integer the integer defined by its
x
least significant bits.
:=
LSB
(
k
)
(
, whose value
should not be too close to 2
k
in order to allow a substantial amount of padding and
prevent brute-force attacks in which all the possible padding values are searched.
A possibility that has been used in practice is to use padding equal in length to the
unpadded message, i.e., to take
The security of this encryption scheme depends on the function
(
)
=
k
and, while the resulting scheme has not
been proved to be CPA secure, it seems reasonable to conjecture that this is indeed the
case under the RSA assumption. A related construction is [87, Construction 5.3.16],
which has a security reduction to an assumption that may be stronger than the RSA
assumption. At any rate, even without a security reduction, the padded RSA scheme
is clearly preferable to plain RSA, which is demonstrably insecure.
On the other hand, the above-defined padded RSA scheme can be proved CPA
secure if the value of
k
(
k
)
is small compared with
k
and, more specifically, if
(
k
)
=
. This follows from the main result in [98] where, building on early results
about the security of the least significant bits in an RSA-encrypted message, the
following fact—which we only state in an informal way—is proved:
The RSA assumption is equivalent to the impossibility of distinguishing blocks of
O
(
ln
k
)
bits in the above notation) of a message
m from blocks of random bits, given the ciphertext corresponding to m
.
Apart from [98], we refer also to [109] for further discussion of these aspects as
well as for a general construction ([109, 10.7.2]) that builds a CPA secure public-
key encryption scheme from any family of one-way trapdoor permutations (such
as the RSA family under the RSA assumption) by using the existence of hard-core
predicates provided by the Goldreich-Levin theorem ([86, Theorem 2.5.2]).
We see that there are ways to obtain CPA secure encryption schemes from the
RSA function but, as we have mentioned, the security property one should aim for
is IND-CCA security. This is more difficult to attain than CPA security but it is clear
O
(
ln ln
n
)
bits (and hence blocks of O
(
ln
k
)
