By Cetin Kaya Koc
The RSA algorithm, invented by Rivest, Shamir, and Adleman [25], is one of the simplest public-key cryptosystems.
The RSA algorithm can be used to send encrypted messages and to produce digital signatures for electronic documents. It provides a procedure for signing a digital document, and verifying whether the signature is indeed authentic. The signing of a digital document is somewhat dierent from signing a paper document, where the same signature is being produced for all paper documents. A digital signature cannot be a constant; it is a function of the digital document for which it was produced. After the signature (which is just another piece of digital data) of a digital document is obtained, it is attached to the document for anyone wishing the verify the authenticity of the document and the signature. We refer the reader to the technical reports Answers to Frequently Asked Questions About Today's Cryptography and Public Key Cryptography Standards published by the RSA Laboratories [26, 27] for answers to certain questions on these issues.
Computation of Modular Exponentiation
Once the modulus and the private and public exponents are determined, the senders and recipients perform a single operation for signing, veri cation, encryption, and decryption. The operation required is the computation of Me (mod n), i.e., the modular exponentiation. The modular exponentiation operation is a common operation for scrambling; it is used in several cryptosystems. For example, the Diffie-Hellman key exchange scheme requires modular exponentiation [6]. Furthermore, the ElGamal signature scheme [7] and the Digital Signature Standard (DSS) of the National Institute for Standards and Technology [22] also require the computation of modular exponentiation. However, we note that the exponentiation process in a cryptosystem based on the discrete logarithm problem is slightly dierent: The base (M) and the modulus (n) are known in advance. This allows some precomputation since powers of the base can be precomputed and saved [5]. In the exponentiation process for the RSA algorithm, we know the exponent (e) and the modulus (n) in advance but not the base (M); thus, such optimizations are not likely to be applicable.
Once the modulus and the private and public exponents are determined, the senders and recipients perform a single operation for signing, veri cation, encryption, and decryption. The operation required is the computation of Me (mod n), i.e., the modular exponentiation. The modular exponentiation operation is a common operation for scrambling; it is used in several cryptosystems. For example, the Diffie-Hellman key exchange scheme requires modular exponentiation [6]. Furthermore, the ElGamal signature scheme [7] and the Digital Signature Standard (DSS) of the National Institute for Standards and Technology [22] also require the computation of modular exponentiation. However, we note that the exponentiation process in a cryptosystem based on the discrete logarithm problem is slightly dierent: The base (M) and the modulus (n) are known in advance. This allows some precomputation since powers of the base can be precomputed and saved [5]. In the exponentiation process for the RSA algorithm, we know the exponent (e) and the modulus (n) in advance but not the base (M); thus, such optimizations are not likely to be applicable.
In the following sections we will review techniques for implementation of the modular exponentiation operation in hardware. We will study techniques for exponentiation, modular multiplication, modular addition, and addition operations. We intend to cover mathematical and algorithmic aspects of the modular exponentiation operation, providing the necessary knowledge to the hardware designer who is interested implementing the RSA algorithm using a particular technology. We draw our material from computer arithmetic books [32, 10, 34, 17], collection of articles [31, 30], and journal and conference articles on hardware structures for performing the modularmultiplication and exponentiations [24, 16, 28, 9, 4, 13, 14, 15, 33]. For implementing the RSA algorithm in software, we refer the reader to the companion report High-Speed RSA Implementation published by the RSA Laboratories [12].