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