<<

. 8
( 19 .)



>>

issues, including the system-dependent factors, are
might be argued that “special-purpose” factoring
taken into account.
methods such as Pollard™s p-f method [18] and super-
Recovering the Private Key encryption attacks [23], which we discuss next, might
end up being faster than using the GNFS. With these
As a first line of attack, an adversary might take the
and similar threats in mind, strong primes were intro-
public key (n, e) of some user and attempt to recover
the private decrypting (or equivalently the signing) duced so that p and q were chosen to satisfy a variety
exponent d. Interestingly, one of the links that has of conditions; for instance p might be chosen so that
p-1 has a large factor r and r-l has a large factor, etc.
been established between the RSA cryptosystem and
These conditions, and similar ones on the form of the
the difficulty of factoring is based on a number-theo-
numbers p + 1 and q + 1 would guarantee that the modu-
retic result predating RSA [16], which can be used
lus n resists the special-purpose factoring methods.
to demonstrate that obtaining a private exponent d
from the public exponent e and the modulus n is as
The introduction of the elliptic curve method (ECM)
hard as actually factoring n. In essence, knowledge
of the exponents e and d allows the attacker to fac- of factoring changed all this [15]. This factoring
tor the modulus n. method has some probability of success regardless of
*.. strong primes the actual form of the prime. As a consequence, the
were inttuduced dominant property for the security of the primes we
With this connection in mind, we first consider the
so that [...I the use is size. In protecting against the ECM factoring
most well known (and currently the best) attack that
modulus n technique one protects, with a very high probability,
an adversary might mount on RSA when trying to
against all special-purpose factoring techniques. In
resists the recover the private key, namely an attempt to factor
special-purpose short, large primes are more important than strong
the RSA modulus n.
primes.
factoring
methods. The Factoring
One early proposed attack against RSA is called
introduction of The problem of factoring and its continuing im-
the elliptic superencryption. Simmons and Norris [23] observed
provements are the topic of a great many articles
curve method that after a sufficient number of repeated encrype
and papers and we will not attempt to replicate the
of factoring information that can be found in three, splendid tions, the original message would eventually be re-
changed all this. covered. This would lead to an attack on RSA if the
articles [2,17,20].
number of encryptions required were small. But this
is not the case if the primes are large and chosen at
It is generally accepted that RSA numbers composed
of primes p and q of about the same size are among random and so while an interesting observation, super-
the hardest to factor for their size. (See, however, encryption is not a practical attack. Likewise, the


CRYPTOBYTES HAUTUMN 1995 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
Page 34
Previous Page Home Next Page




observation that p and q being very close together in ately, is there a way to compromise the security of RSA
numerical value allows the efficient factorization of encryption without recovering the private exponent?
n [25], is not relevant to practical security provided
p and q are sufficiently large and chosen at random. We highlight three concerns, and describe how to
deal with each in turn. Among the theoretically
Wiener™s Attack interesting results that we do not have space to
There is an interesting attack due to Wiener [24] cover here are those concerned with the protection
which allows an attacker to recover the private ex- offered by RSA encryption for various bits of mes- Though a
ponent in an ingenious way. Wiener shows that a sage information. The interested reader can find theoretical
continued fraction approximation using the publicly more information about this topic in the work of concern, the
available parameters e and n can provide sufficient Alexi et al. [l]. possibility of
generating a
information to recover d. This attack will be efficient
and practical when the private exponent d is small Small Messages non-prime is
not really a
relative to the RSA modulus; that is when d < n”4. Clearly RSA encryption is not effective on small
practical issue.
messages when the public exponent e is small. In
This attack is a concern if the private exponent d is particular, when c = me < n, m can be recovered from
deliberately chosen to be small, perhaps in an at- c by ordinary root extraction. In fact this attack can
tempt to improve the efficiency of decryption or sign- be extended somewhat even if there has been some
ing. In general use however, it is unlikely that a small modular reduction by guessing how much reduction
private exponent will be generated if the public ex- has taken place. Thus this attack extended to c > n
ponent e is chosen first; when e is small, d is always by trial-and-error might still be faster than exhaus-
large enough to resist this particular attack and if e is tive search form.
chosen at random, then with an overwhelming prob-
ability, d will be large enough to resist Wiener™s at- But the precaution is obvious. Either the public ex-
tack. If the private exponent d is chosen, it should ponent e should be large or the messages should al-
not be too small. ways be large. It is this second suggestion that is the
most useful since a small public exponent is often
Using Probabilistic Primes preferred. However we have to be careful to ensure
One frequent question is how the security of RSA that the large message we use is not merely some
Either the
might be affected if one of the primes used to compute multiple of a known value such as a large power of
the modulus is, in fact, not a prime number after all. two (as would be the case if the message were pad- public
ded on the right with zeroes). As we will see, this exponent e
First, the factors of n will be smaller than expected, would allow an attacker to mount some sophisticated should be
and so it may be easier to factor the modulus with attacks. So when the public exponent e is small the large or the
special-purpose factoring methods. Second, except messages being encrypted should always be large in messages
in the unlikely event that we have mistakenly gen- numerical value and not a multiple of some known should always
erated a so-called “Carmichael number,” decryption value. This can all be achieved by padding the mes- be large.
and verification will yield incorrect results for most sage appropriately prior to encryption.
messages and signatures, an occurrence which could
be used to reveal the factors of the modulus. Chosen Ciphertext Attacks
One of the identities we highlighted at the begin-
Though a theoretical concern, the possibility of gen- ning of this article was:
erating a non-prime is not really a practical issue.
With modem prime generation methods, the prob- (m*re)d= md*r(mdn).
ability that an output is not prime can be made arbi-
trarily small or even eliminated entirely. An attacker might exploit this fact in the following
way. Having intercepted some ciphertext c, the at-
Decrypting Messages tacker chooses some random number r and computes
While recovering the private exponent d seems to be re mod n. By sending c * re mod n to the legitimate
difficult provided we generate the key pair appropri- receiver, cd * r mod n is recovered which will, in all


THE TECHNICAL NEWSLETTER OF RSA LABORATORIES -AUTUMN 1995 CRYPTOBYTES
Page 35
Previous Page Home Next Page




Hastad [12] showed that if an attacker is able to in-
likelihood, appear to be random. If the attacker were
tercept the encryptions of a single message m gener-
to obtain this decrypted string then the intended
ated using several different RSA keys with a com-
ciphertext could be obtained on multiplication by
mon public exponent e, then it might be possible to
r-l mod n.
recover m. As a special case, given 1 different encrypt-
ions ti mod nl , . . . , me mod nl an attacker can solve
More far-reaching than obtaining the correct decryp-
for m with the Chinese Remainder Theorem [ 141.
tion of a particular message, is a generalization of
this technique by Desmedt and Odlyzko [7]. Since
More generally, given t related encryptions
a chosen ciphertext attack on RSA encryption is
equivalent in effect to a chosen-text attack on the
RSA signature scheme, we shall also see this attack ( a, m + b, )™ mod n, , . . . , ( a, m + b, )™ mod n,
in the next section.
where the als and b;s are known and t > e(e+l)/2,
an attacker can solve for m with lattice reduction
The attacker asks the user of RSA to decrypt care-
. ..an attacker
techniques. Note that this attack is a concern if the
should not fully chosen ciphertexts and obtains a pool of data
messages are related in a known way. The use of suf,
consisting of the decryptions of small primes and cer-
be able to
ficient pseudorandom padding prior to encryption
obtain the tain other values. Then, when sufficient information
will make such an attack impossible to mount in
raw RSA has been accumulated, the attacker can decrypt a
practice, and we will describe one method for doing
decryption of particular encrypted message by multiplying the
this in the accompanying box. Messages that are res
an arbitrary ciphertext by a random re and factoring the result
lated in a known way should not be encrypted with
value. into small primes and other values in the pool. (The
many RSA keys.
attacker can try another r if unsuccessful.) The de-
cryption of the ciphertext will be the product of the
Some very recent work by Franklin and Reiter [lo]
factors™ decryptions and I-™ mod n.
(see Algorithms Update in this issue of CryptoBytes)
has highlighted a potential problem when related
While this attack can be more efficient than factor-
messages are encrypted under the same RSA key
ing the modulus, certain precautions can be taken to
with a low exponent. This work should not be cone
ensure that it is impractical. However there is already
fused with that of Hastad but the problem they inge-
one lesson we can learn, and that is that an attacker
niously exploit relies on the fact that the various
should not be able to obtain the raw RSA decryption
components required for their attack are once again
of an arbitrary value.
related in a known way. The use of random padding,
Just how practical is a chosen ciphertext attack? as we have already seen, will destroy any known re-
lation between messages. Related messages should
Consider an environment where a subscriber to some
conditional-access service has access to the decryp- not be encrypted with the same RSA key.
tion equipment but not to the actual keys. In such a
Forging Signatures
case the subscriber might well be free to interrogate
The problem facing an attacker who is attempting
the decryption unit at will, with ciphertexts of the
to forge an RSA digital signature is to construct a
subscriber™s own choosing. It would clearly be a se-
valid signature for a new message while observing
curity flaw if the corresponding decryptions were
the signatures of other messages that might be known
then directly accessible to the attacker.
or chosen.
Low Exponent Attacks
Among the attacks we will consider here are a simple
The use of One class of attacks, perhaps more than any other,
random chosen message attack and existential forgery as well
has been the cause of confusion about the correct
as the signature version of the attack on encryption
padding . . . will and safe use of RSA. These attacks are due to Hastad,
destroy any due to Desmedt and Odlyzko. We do not consider
and while the scope and validity of the attacks is not
known relation in question, some have taken the existence of these issues such as which hash functions are more suit-
able for use with the RSA signing operation. There
between attacks as evidence for avoiding low public expo-
messages. nents in an implementation of RSA. are a great many possible designs for hash functions


CRYPTOBYTES 1995 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
AUTUMN
Page 36
Previous Page Home Next Page




. ..if should not
Desmedt and Odlyzko™s Attack and a Variant
to choose from [19] and while those based on modu-
be possible
The attack of Desmedt and Odlyzko on encryption
lar arithmetic might offer certain implementation
to obtain a
applies equally to signatures. Perhaps it is more prac-
advantages (since they might rely on much the same
raw RSA
tical when applied to signature forgery rather than
operations as are already required for signing),
ciphertext decryption, since it might be easier to de-
Coppersmith has demonstrated attacks on one such signature on
an arbitrary
proposal [S]. Extreme care should be taken before mand and receive the signature on a variety of mes-
value.
considering a hash function based on modular arith- sages instead of demanding decryptions for a range
metic for use with RSA signatures. of ciphertexts. A variant of this attack can be par-
ticularly effective when the messages being signed
are small (for instance if they are generated as the
Chosen and Known Message Attacks
Just as there was a chosen ciphertext attack on output from some message-digest algorithm) unless
encryption, there is the following chosen message care is taken.
attack on raw RSA signatures. As with decryption,
once given the signature of m™ = mre mod n, where Essentially, the attack of Desmedt and Odlyzko (for
r is random, an attacker can obtain the signature of both encryption and signatures) relies on factoring
m since md = (m™)dr-l (mod n). Again, the lesson to the message into small primes and values near A.
learn is simple; it should not be possible to obtain a An interesting adaptation of this attack (see notes
raw RSA signature on an arbitrary value. in Section 8.1 of [22]) applies to the case when the
numerical input to the signing algorithm is always
Using the mathematical identities at the beginning relatively small. In this adaptation, the attacker
of the article, it is always possible to compute new factors the particular message into small primes (this
message-signature pairs (m, s) of the form may or may not succeed); the signature on the mes-
sage equals the product of the factors™ signatures. The
attacker obtains the primes™ signatures from appro-
t
m=˜nmpi m o d n
Messages
priate combinations of signatures on other messages
i=I

to be signed
whose factors are small. As opposed to when the in-
f
s=rnspimodn
put is as large as the modulus, values near G are not should be as
i=l

needed. The probability of success will therefore de- large as the

<<

. 8
( 19 .)



>>