Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) (Publisher: John Wiley & Sons, Inc.) Author(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book:
Previous | Table of Contents | Next
Table 19.4 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, 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 = cd 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 = re mod n y = xc mod n t = r-1 mod n 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 u = yd mod n Now, Eve computes tu mod n = r-1yd mod n = r-1xdcd mod n = cd 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 = xe 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 (md 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 = xdmd mod n Scenario 3: Eve wants Alice to sign m3 . She generates two messages, m1 and m2, such that m3 ≡ m1m2 (mod n) If Eve can get Alice to sign m1 and m2, she can calculate m3: m3d = (m1d mod n)(m2d mod n )
Previous | Table of Contents | Next
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.