RSA Laboratories

3.1.3 What would it take to break the RSA cryptosystem?

There are a few possible interpretations of "breaking" the RSA system. 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 exponent. The hard part is factoring n; the security of RSA depends on 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 2.3.4 and 2.3.5 regarding the state of the art in factoring). It should be noted that hardware improvements alone will not weaken the RSA cryptosystem, as long as appropriate key lengths are used. In fact, hardware improvements should increase the security of the cryptosystem (again, see Question 2.3.5).

Another way to break the RSA cryptosystem is to find a technique to compute eth roots mod n. Since c = me mod n, the eth root of c mod n 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 general methods are currently known that attempt to break the RSA system in this way. However, in special cases where multiple related messages are encrypted with the same small exponent, it may be possible to recover the messages.

The attacks just mentioned are the only ways to break the RSA cryptosystem in such a way as to be able to recover all messages encrypted under a given key. There are other methods, however, that aim to recover single messages; success would not enable the attacker to recover other messages encrypted with the same key. Some people have also studied whether part of the message can be recovered from an encrypted message [ACG84].

The simplest single-message attack is the guessed plaintext attack. An attacker sees a ciphertext and guesses that the message might be, for example, "Attack at dawn," and encrypts this guess with the public key of the recipient and by comparison with the actual ciphertext, the attacker knows whether or not the guess was correct. Appending some random bits to the message can thwart this attack. 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 Håstad [H as88]. Fortunately, this attack can also be defeated by padding the message before each encryption with some random bits. There are also some chosen ciphertext attacks (or chosen message attacks for signature forgery), 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 [Dav82] and Desmedt and Odlyzko [DO86] give some examples).

For a survey of these and other attacks on the RSA cryptosystem, see [KR95c].

Of course, there are also attacks that aim not at the cryptosystem itself but at a given insecure implementation of the system; these do not count as "breaking" the RSA system, 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 a private key insecurely, an attacker may discover it. One cannot emphasize strongly enough that to be truly secure, the RSA cryptosystem 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 4.1.3 for a discussion of secure key management in an RSA system.

Top of the page