that is, has no common factors with) the product (p-1)(q-1). Different sources recommend different values, but e is typically one of the following: 3, 17, and more often 65537 216 + 1). The RSA public key is the pair (n, e). 3. The RSA private key is then the number d = e-1 mod [(p-1)(q-1)]. 4. Either key can be used for encryption and the other one will be able to decrypt the cipher. 5. Encryption on a message m to produce cipher C is mod N. 6. Decryption of the cipher C to recover the message m is = dmod N. Implementations for the decryption are usually based on the Extended Euclid Algorithm to find the inverse of a number in modular arithmetic. However, to accelerate the private-key operations, some cryptographic coprocessors offer the possibility of using a special module that implements the famous Chinese Remainder Theorem (CRT). In that case, the values of p, q, and values close to them, such as d mod (p-1) or d mod (q-1), are saved and others are easily calculated from them for subsequent use. Both theorems are fundamental pieces of knowledge in elementary number theory and can be found in any good textbook on cryptography or number theory. Several sources of benchmarking information are available to compare the time it takes between various operations. Without intending to scrutinize the efficiency of algorithms or code implementa- tions, we show some results publicly available from Wei Dai's Crypto + benchmarking work in Table 17.1 (see www.eskimo.com/~weidai/benchmarks.html). This is provided solely to compare the impact of some typical cryptographic operations on systems. The absolute values of these items are irrelevant to our discussion. What is important here is the impact on the performance from the choice of algorithm and the key size. Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. SECURITY COPROCESSORS SECURITY COPROCESSORS