RivestKaliski-RSAProblem.pdf

(97 KB) Pobierz
RSA Problem
Ronald L. Rivest, MIT Laboratory for Computer Science
rivest@mit.edu
and Burt Kaliski, RSA Laboratories
bkaliski@rsasecurity.com
December 10, 2003
1
Introduction
In RSA public-key encryption [30], Alice encrypts a plaintext
M
for Bob
using Bob’s public key (n,
e)
by computing the ciphertext
C
=
M
e
(mod
n) .
(1)
where
n,
the
modulus,
is the product of two or more large primes, and
e,
the
public exponent,
is an odd integer
e
≥
3 that is relatively prime to
φ(n),
the
order of the multiplicative group
Z
∗
.
n
Bob, who knows the corresponding RSA private key (n,
d),
can easily
decrypt, since
de
= 1 (mod
φ(n))
implies that
M
=
C
d
(mod
n) .
(2)
An adversary may learn
C
by eavesdropping, and may very well also
know Bob’s public key; nonetheless such an adversary should not be able to
compute the corresponding plaintext
M
.
One may formalize the task faced by this adversary as the
RSA Problem:
The RSA Problem:
Given an RSA public key (n,
e)
and a ciphertext
C
=
M
e
(mod
n),
to compute
M
.
To solve the RSA Problem an adversary, who doesn’t know the private
key, must nonetheless invert the RSA function.
1
The
RSA Assumption
is that the RSA Problem is hard to solve when
the modulus
n
is sufficiently large and randomly generated, and the plain-
text
M
(and hence the ciphertext
C)
is a random integer between 0 and
n
−
1. The assumption is the same as saying that the RSA function is a
trapdoor one-way function (the private key is the tradpoor).
The randomness of the plaintext
M
over the range [0,
n
−
1] is important
in the assumption. If
M
is known to be from a small space, for instance,
then an adversary can solve for
M
by trying all possible values for
M
.
The RSA Problem is the basis for the security of RSA public-key encryp-
tion as well as RSA digital signature schemes.
See also surveys by Boneh [10] and Katzenbeisser [24].
2
Relationship to integer factoring
The RSA Problem is clearly no harder than integer factoring, since an adver-
sary who can factor the modulus
n
can compute the private key (n,
d)
from
the public key (n,
e).
However, it is not clear whether the converse is true, that is, whether an
algorithm for integer factoring can be efficiently constructed from an algo-
rithm for solving the RSA Problem.
Boneh and Venkatesan [9] have given evidence that such a construction
is unlikely when the public exponent is very small, such as
e
= 3 or 17.
Their result means that the RSA Problem for very small exponents could be
easier than integer factoring, but it doesn’t imply that the RSA Problem is
actually easier, i.e., efficient algorithms are still not known. For larger public
exponents, the question of equivalence with integer factoring still open as of
this writing.
3
Recovering the private key
Clearly, if the adversary could compute Bob’s private key (n,
d)
from his
public key (n,
e),
then the adversary could decrypt
C
using equation (2).
However, de Laurentis [15] and Miller [27] have shown that computing
an RSA private key (n,
d)
from the corresponding RSA encryption key (n,
e)
is as hard as factoring the modulus
n
into its prime factors
p
and
q.
As
already noted, given the factors
p
and
q,
it is easy to compute
d
from
e,
and
2
conversely there is a probabilisitic polynomial-time algorithm which takes as
input
n, e,
and
d,
and which factors
n
into
p
and
q.
(See also Fact 1 in
Boneh [10].)
If the modulus
n
was chosen as the product of two “sufficiently large”
randomly-chosen prime numbers
p
and
q,
then the problem of factoring
n
appears to be intractable. Thus, the private exponent
d
is protected from
disclosure by the difficulty of factoring the modulus
n.
An adversary might also try to compute
d
using some method of solving
the discrete logarithm problem. For example, an adversary could compute
the discrete logarithm of
M
to the base
M
e
(mod
n).
If
d
is too small (say,
less than 160 bits), then an adversary might be able to recover it by the baby
step-giant step method.
Even if
d
is too large to be recovered by discrete logarithm methods,
however, it may still be at risk.
For example, Wiener [33] has shown that if the secret exponent is less than
1/4
n /3,
an adversary can efficiently compute
d
given
n
and
e.
An improved
bound of
n
0.292
has been presented by Boneh and Durfee [8].
However, it does appear to be the case that if the RSA parameters were
chosen large enough, then the adversary can not solve the RSA Problem by
computing the private RSA exponent of the recipient.
4
Self-reducibility
It is conceivable that someone could devise a clever procedure for solving the
RSA Problem without factoring the modulus
n
or determining the private
key
d.
An adversary might, for example, have a procedure that decrypts a
small fraction of “weak” ciphertexts. However, the RSA procedure enjoys a
certain kind of “self-reducibility”, since it is multiplicative:
(M
R)
e
=
M
e
R
e
(mod
n) .
An adversary can transform a given ciphertext
M
e
into another one (M
R)
e
by multiplying it by the encryption
R
e
of a randomly chosen element
R
of
Z
∗
. Since the result has a chance of being a “weak” ciphertext, it follows
n
that if there is an adversarial procedure
A
that can decrypt a fraction
of ciphertexts, then there is another (randomized) adversarial procedure
A
that can decrypt all ciphertexts in expected running time that is polynomial
3
in the running time of
A,
in 1/ , and in log
n
(see polynomial time). (See
Motwani and Raghavan [28, Section 14.4].)
Self-reducibility is a double-edged sword. On the one hand, it provides
assurance that “all” random ciphertexts are equally hard to invert. This
property has been helpful in the security proofs for several public-key en-
cryption and signature schemes based on the RSA Problem. On the other
hand, self-reducibility provides an avenue for an adversary to gain informa-
tion about the decryption of one ciphertext from the decryption of other
ciphertexts (see “chosen ciphertext attacks”) below.
5
Low public exponent RSA
A user of the RSA cryptosystem may reasonably wish to use a public expo-
nent
e
that is relatively short: common choices are
e
= 3 or
e
= 2
16
+ 1 =
65537. Using a short public exponent results in faster public-key encryption
and faster public-key signature verification. Does this weaken RSA?
If the public exponent is small and the plaintext
M
is very short, then
√
the RSA function may be easy to invert: in particular, if
√
<
e
N
, then
M
e
e
C
=
M
over the integers, so
M
can be recovered as
M
=
C.
H˚
astad [22] shows that small public exponents can be dangerous when
the same plaintext is sent to many different recipients, even if the plaintext
is “padded” in various (simple) ways beforehand.
Coppersmith et al.[12] give a powerful “related messages” attack, which is
effective when the public exponent is small, based on the LLL algorithm [25]
for lattice reduction.
Because of these concerns, small public exponents are sometimes avoided
in industry standards and in practice. However, the concerns can also be
addressed with appropriate padding schemes (see “chosen ciphertext at-
tacks” below), provided they are correctly implemented. For digital signature
schemes, small public exponents are generally not an issue.
6
Strong RSA Assumption
The
Strong RSA Assumption
was introduced by Bari´ and Pfitzmann [3] and
c
by Fujisaki and Okamoto [18] (see also [13]).
This assumption differs from the RSA Assumption in that the adversary
4
can select the public exponent
e.
The adversary’s task is to compute, given a
modulus
n
and a ciphertext
C,
any
plaintext
M
and (odd) public exponent
e
≥
3 such that
C
=
M
e
(mod
n).
This may well be easier than solving
the RSA Problem, so the assumption that it is hard is a stronger assumption
than the RSA Assumption. The Strong RSA Assumption is the basis for a
variety of cryptographic constructions.
7
Bit-security of RSA encryption
It is conceivable that RSA could be “secure” in the sense that the RSA
Assumption holds (i.e. RSA is hard to invert), yet that RSA “leaks” infor-
mation in that certain plaintext bits are easy to predict from the ciphertext.
Does RSA provide security to individual bits of plaintext?
Goldwasser et al. [21] first studied the bit-security of RSA, showing that
an adversary who could reliably extract from a ciphertext the least signficant
bit of the plaintext would in fact be able to decrypt RSA efficiently (i.e.
obtain the entire plaintext efficiently).
This line of research was pursued by other researchers. For example,
Vazirani et al. [32]) showed that the adversary could still decrypt even with
an lsb procedure that was only 0.732 + accurate. They also showed that
the low-order log(log(n)) bits of plaintext are 3/4 + secure.
Chor and Goldreich [11] improved this result to show that the least-
significant bit of RSA plaintext can not be predicted with probability better
than 1/2 + 1/poly(log(n)) (under the RSA Assumption). Alexi et al. [1, 2]
completed this result to show that the least-significant log(log(n)) bits are
secure in the same sense. (Fischlin and Schnorr [17] provide a simpler and
tighter proof of this result.)
H˚
astad and N¨slund [23] have shown that
all
of the plaintext bits are
a
well-protected by RSA, in the sense that having a nontrivial advantage for
predicting any one plaintext bit would enable the adversary to invert RSA
completely.
The results about bit-security of RSA generally involve a
reduction
tech-
nique (see computational complexity theory), where an algorithm for solv-
ing the RSA Problem is constructed from an algorithm for predicting one
(or more) plaintext bits. Like self-reducibility, bit-security is a double-edged
sword. This is because the security reductions also provide an avenue of
attack on a “leaky” implementation. If an implementation of an RSA de-
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin