Cryptography is concerned with techniques for ensuring confidentiality of communication, and is also usually understood to encompass problems related to confidentiality, such as authentication and enforcement of security properties. This is not the place for a full introduction to the field, and there are many excellent texts on the subject such as [64]. The present discussion will focus on a few aspects of implementing common cryptographic algorithms on the Itanium architecture, showing how special architectural features can be exploited to improve efficiency. For example, a particularly common class of "public key" cryptosystems such as RSA [65] involve a "public" key consisting of e together with n = pq, the product of two large primes, and a "private" key d. Encryption of a message block is achieved by

and decryption by

The keys are chosen so that ed ? 1 (mod( p ? 1 )( q ? 1)), and one can then show using elementary number theory that encryption and decryption are indeed inverse operations, provided m < n. Both encryption and decryption require exponentiation modulo another number, and the same applies to a number of other cryptographic schemes. This exponentiation is then usually carried out using a sequence of multiplications modulo the modulus, to maintain moderate size for the intermediate results. (This is discussed in a little more detail later.) Finally, these modular products are typically implemented using Montgomery multiplication [66], which eventually requires high-precision integer arithmetic. Thus, efficiency of the...