|Previous||Table of Contents||Next|
RSA Speeds for Different Modulus Lengths
with an 8-bit Public Key (on a SPARC II)
|512 bits||768 bits||1, 024 bits|
|Encrypt||0.03 sec||0.05 sec||0.08 sec|
|Decrypt||0.16 sec||0.48 sec||0.93 sec|
|Sign||0.16 sec||0.52 sec||0.97 sec|
|Verify||0.02 sec||0.07 sec||0.08 sec|
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, thats 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 wouldnt 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 .
For the ultraskeptical, some RSA variants have been proved to be as difficult as factoring (see Section 19.5). Also look at , 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 Fermats little theorem . Unfortunately, this method is also slower than factoring the modulus.
Theres 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 wont work properlyyoull 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 . Honestly, I wouldnt 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. Its important to realize that its not enough to use RSA. Details matter.
Scenario 1: Eve, listening in on Alices 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
To recover m, she first chooses a random number, r, such that r is less than n. She gets Alices public key, e. Then she computes
If x = re mod n, then r = xd 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
Now, Eve computes
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 wouldnt. 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. Lets call this message m.
First, Mallory chooses an arbitrary value x and computes y = xe mod n. He can easily get e; its Trents 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 md mod n. Now Mallory calculates (md mod n)x-1 mod n, which equals nd 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:
Scenario 3: Eve wants Alice to sign m3 . She generates two messages, m1 and m2, such that
If Eve can get Alice to sign m1 and m2, she can calculate m3:
|Previous||Table of Contents||Next|