Private key operations can be speeded up with the Chinese remainder theorem if you save the values of p and q, and additional values such as d mod (p - 1), d mod (q - 1), and q^-1 mod p [1283, 1276]. These additional numbers can easily be calculated from the private and public keys.

Security of RSA

The security of RSA depends wholly on the problem of factoring large numbers. Technically, that’s a lie. It is conjectured that the security of RSA depends on the problem of factoring large numbers. It has never been mathematically proven that you need to factor n to calculate m from c and e. It is conceivable that an entirely different way to cryptanalyze RSA might be discovered. However, if this new way allows the cryptanalyst to deduce d, it could also be used as a new way to factor large numbers. I wouldn’t worry about it too much.

It is also possible to attack RSA by guessing the value of (p - 1)(q - 1). This attack is no easier than factoring n [1616].

For the ultraskeptical, some RSA variants have been proved to be as difficult as factoring (see Section 19.5). Also look at [36], which shows that recovering even certain bits of information from an RSA-encrypted ciphertext is as hard as decrypting the entire message.

Factoring n is the most obvious means of attack. Any adversary will have the public key, e, and the modulus, n. To find the decryption key, d, he has to factor n. Section 11.4 discusses the current state of factoring technology. Currently, a 129-decimal-digit modulus is at the edge of factoring technology. So, n must be larger than that. Read Section 7.2 on public key length.

It is certainly possible for a cryptanalyst to try every possible d until he stumbles on the correct one. This brute-force attack is even less efficient than trying to factor n.

From time to time, people claim to have found easy ways to break RSA, but to date no such claim has held up. For example, in 1993 a draft paper by William Payne proposed a method based on Fermat’s little theorem [1234]. Unfortunately, this method is also slower than factoring the modulus.

There’s another worry. Most common algorithms for computing primes p and q are probabilistic; what happens if p or q is composite? Well, first you can make the odds of that happening as small as you want. And if it does happen, the odds are that encryption and decryption won’t work properly—you’ll notice right away. There are a few numbers, called Carmichael numbers, which certain probabilistic primality algorithms will fail to detect. These are exceedingly rare, but they are insecure [746]. Honestly, I wouldn’t worry about it.

Chosen Ciphertext Attack against RSA

Some attacks work against the implementation of RSA. These are not attacks against the basic algorithm, but against the protocol. It’s important to realize that it’s not enough to use RSA. Details matter.

Scenario 1: Eve, listening in on Alice’s communications, manages to collect a ciphertext message, c, encrypted with RSA in her public key. Eve wants to be able to read the message. Mathematically, she wants m, in which

m = c^d

To recover m, she first chooses a random number, r, such that r is less than n. She gets Alice’s public key, e. Then she computes

x = r^e mod n

y = xc mod n

t = r^-1 mod n

If x = r^e mod n, then r = x^d mod n.

Now, Eve gets Alice to sign y with her private key, thereby decrypting y. (Alice has to sign the message, not the hash of the message.) Remember, Alice has never seen y before. Alice sends Eve

u = y^d mod n

Now, Eve computes

tu mod n = r^-1y^d mod n = r^-1x^dc^d mod n = c^d mod n = m

Eve now has m.

Scenario 2: Trent is a computer notary public. If Alice wants a document notarized, she sends it to Trent. Trent signs it with an RSA digital signature and sends it back. (No one-way hash functions are used here; Trent encrypts the entire message with his private key.)

Mallory wants Trent to sign a message he otherwise wouldn’t. Maybe it has a phony timestamp; maybe it purports to be from another person. Whatever the reason, Trent would never sign it if he had a choice. Let’s call this message m’.

First, Mallory chooses an arbitrary value x and computes y = x^e mod n. He can easily get e; it’s Trent’s public key and must be public to verify his signatures. Then he computes m = ym’ mod n, and sends m to Trent to sign. Trent returns m’^d mod n. Now Mallory calculates (m^d mod n)x^-1 mod n, which equals n’^d mod n and is the signature of m’.

Actually, Mallory can use several methods to accomplish these same things [423, 458, 486]. The weakness they all exploit is that exponentiation preserves the multiplicative structure of the input. That is:

(xm)^d mod n = x^dm^d mod n

Scenario 3: Eve wants Alice to sign m₃ . She generates two messages, m₁ and m₂, such that

m₃ ≡ m₁m₂ (mod n)

If Eve can get Alice to sign m₁ and m₂, she can calculate m₃:

m₃^d = (m₁^d mod n)(m₂^d mod n )