RSA?

How fast is RSA?

An ``RSA operation,'' whether for encrypting or decrypting, signing
or verifying, is essentially a modular exponentiation, which can be
performed by a series of modular multiplications.

In practical applications, it is common to choose a small public
exponent for the public key; in fact, entire groups of users can use
the same public exponent. This makes encryption faster than decryption
and verification faster than signing. Algorithmically, public-key
operations take O(k^2) steps, private key operations take O(k^3)
steps, and key generation takes O(k^4) steps, where k is the number of
bits in the modulus; O-notation refers to the an upper bound on the
asymptotic running time of an algorithm [22].

There are many commercially available hardware implementations of RSA,
and there are frequent announcements of newer and faster chips. The
fastest current RSA chip [76] has a throughput greater than 600 Kbits
per second with a 512-bit modulus, implying that it performs over 1000
RSA private-key operations per second. It is expected that RSA speeds
will reach 1 Mbit/second within a year or so.

By comparison, DES is much faster than RSA. In software, DES is generally at
least 100 times as fast as RSA. In hardware, DES is between 1,000 and 10,000
times as fast, depending on the implementations. RSA will probably narrow
the gap a bit in coming years, as it finds growing commercial markets, but
will never match the performance of DES.


2.4 How much extra message length is caused by using RSA?

Only a very small amount of data expansion is involved when using RSA. For
encryption, a message may be padded to a length that is a multiple of the
block length, usually 64 bits, since RSA is usually combined with a
secret-key block cipher such as DES (see Question 2.12). Encrypting
the DES key takes as many additional bits as the size of the RSA modulus.


For authentication, an RSA digital signature is appended to a document.
An RSA signature, including information such as the name of the signer, is
typically a few hundred bytes long. One or more certificates (see Question
3.5) may be included as well; certificates can be used in conjunction
with any digital signature method. A typical RSA certificate is a few
hundred bytes long.


2.5 What would it take to break RSA?

There are a few possible interpretations of ``breaking RSA''. The most
damaging would be for an attacker to discover the private key corresponding
to a given public key; this would enable the attacker both to read all
messages encrypted with the public key and to forge signatures. The obvious
way to do this attack is to factor the public modulus, n, into its two prime
factors, p and q. From p, q, and e, the public exponent, the attacker can
easily get d, the private key. The hard part is factoring n; the security
of RSA depends of factoring being difficult. In fact, the task of recovering
the private key is equivalent to the task of factoring the modulus: you can
use d to factor n, as well as use the factorization of n to find d. See
Questions 4.5 and 4.6 regarding the state of the art in factoring. It should
be noted that hardware improvements alone will not weaken RSA, as long as
appropriate key lengths are used; in fact, hardware improvements should
increase the security of RSA (see Question 4.5).

Another way to break RSA is to find a technique to compute e-th roots mod
n. Since c = m^e, the e-th root of c is the message m. This attack would
allow someone to recover encrypted messages and forge signatures even
without knowing the private key. This attack is not known to be equivalent to
factoring. No methods are currently known that attempt to break RSA in this
way.

The attacks just mentioned are the only ways to break RSA in such a
way as to be able to recover all messages encrypted under a given key.
There are other methods, however, which aim to recover single messages;
success would not enable the attacker to recover other messages
encrypted with the same key.

The simplest single-message attack is the guessed plaintext attack. An
attacker sees a ciphertext, guesses that the message might be ``Attack at
dawn'', and encrypts this guess with the public key of the recipient; by
comparison with the actual ciphertext, the attacker knows whether or not
the guess was correct. This attack can be thwarted by appending some random
bits to the message. Another single-message attack can occur if someone
sends the same message m to three others, who each have public exponent
e=3. An attacker who knows this and sees the three messages will be able
to recover the message m; this attack and ways to prevent it are discussed
by Hastad [35]. There are also some ``chosen ciphertext'' attacks, in
which the attacker creates some ciphertext and gets to see the corresponding
plaintext, perhaps by tricking a legitimate user into decrypting a fake
message; Davida [23] gives some examples.

Of course, there are also attacks that aim not at RSA itself but at
a given insecure implementation of RSA; these do not count as ``breaking
RSA'' because it is not any weakness in the RSA algorithm that is exploited,
but rather a weakness in a specific implementation. For example, if someone
stores his private key insecurely, an attacker may discover it. One cannot
emphasize strongly enough that to be truly secure RSA requires a secure
implementation; mathematical security measures, such as choosing a long key
size, are not enough. In practice, most successful attacks will likely be
aimed at insecure implementations and at the key management stages of an RSA
system. See Section 3 for discussion of secure key management in an
RSA system.


2.6 Are strong primes necessary in RSA?

In the literature pertaining to RSA, it has often been suggested that in
choosing a key pair, one should use ``strong'' primes p and q to generate
the modulus n. Strong primes are those with certain properties that make
the product n hard to factor by specific factoring methods; such
properties have included, for example, the existence of a large prime
factor of p-1 and a large prime factor of p+1. The reason for these
concerns is that some factoring methods are especially suited to
primes p such that p-1 or p+1 has only small factors; strong primes
are resistant to these attacks.

However, recent advances in factoring (see Question 4.6) appear to
have obviated the advantage of strong primes; the elliptic curve factoring
algorithm is one such advance. The new factoring methods have as good a
chance of success on strong primes as on ``weak'' primes; therefore, choosing
strong primes does not significantly increase resistance to attacks. So for
now the answer is negative: strong primes are not necessary when using RSA,
although there is no danger in using them, except that it takes longer to
generate a key pair. However, new factoring algorithms may be developed in
the future which once again target primes with certain properties; if so,
choosing strong primes may again help to increase security.


2.7 How large a modulus (key) should be used in RSA?

The best size for an RSA modulus depends on one's security needs. The larger
the modulus, the greater the security but also the slower the RSA operations.
One should choose a modulus length upon consideration, first, of one's
security needs, such as the value of the protected data and how long it needs
to be protected, and, second, of how powerful one's potential enemy is.
It is also possible that a larger key size will allow a digitally signed
document to be valid for a longer time; see Question 3.17.

A good analysis of the security obtained by a given modulus length is given
by Rivest [72], in the context of discrete logarithms modulo a prime, but
it applies to RSA as well. Rivest's estimates imply that a 512-bit modulus
can be factored with an $8.2 million effort, less in the future. It may
therefore be advisable to use a longer modulus, perhaps 768 bits in length.
Those with extremely valuable data (or large potential damage from digital
forgery) may want to use a still longer modulus. A certifying authority
(see Question 3.5) might use a modulus of length 1000 bits or more, because
the validity of so many other key pairs depends on the security of the one
central key.

The key of an individual user will expire after a certain time, say, two
years (see Question 3.12). Upon expiration, the user will generate a new
key which should be at least a few digits longer than the old key to
reflect the speed increases of computers over the two years. Recommended key
length schedules will probably be published by some authority or public body.

Users should keep in mind that the estimated times to break RSA are averages
only. A large factoring effort, attacking many thousands of RSA moduli, may
succeed in factoring at least one in a reasonable time. Although the security
of any individual key is still strong, with some factoring methods there is
always a small chance that the attacker may get lucky and factor it quickly.

As for the slowdown caused by increasing the key size (see Question
2.3), doubling the modulus length would, on average, increase the
time required for public-key operations (encryption and signature
verification) by a factor of 4, and increase the time taken by private
key operations (decryption and signing) by a factor of 8. The reason that
public-key operations are affected less than private-key operations is that
the public exponent can remain fixed when the modulus is increased, whereas
the private exponent increases proportionally. Key generation time would
increase by a factor of 16 upon doubling the modulus, but this is a
relatively infrequent operation for most users.