A public key cryptosystem allows two or more parties to securely communicate
over an insecure channel without establishing a physically secure channel for key
exchange. The RSA cryptosystem is the most popular public key cryptosystem ever
invented. It is based on the difficulty of factoring large composite numbers. Once the RSA
system is setup, i.e., the modulus, the private and public exponents are determined, and the
public components have been published, the senders as well as the receivers perform a
single operation for signing, encryption, decryption, and verification. This operation is the
computation of modular exponentiation. In this thesis, we focus on fast implementations
of the modular exponentiation operation. Several methods for modular exponentiation are
presented, including the binary method and the m-ary method. We give a general algorithm
of implementing the m-ary method, and some examples of the quaternary method
and the octal method. The standard multiplication and squaring algorithms are also discussed
as methods to implement the modular multiplication and squaring operations. Two
methods for performing the modular multiplication operation are given: the multiply and
reduce method and the Montgomery method. The Montgomery product algorithm is used
in the implementation of the modular exponentiation operation. The algorithms presented
in this thesis are implemented in C and 16-bit in-line 80486 assembly code. We have performed
extensive testing of the code, and obtained timing results which are given in the
last chapter of the thesis. / Graduation date: 1995
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/35318 |
| Date | 31 January 1995 |
| Creators | Peng, Yanqun |
| Contributors | Koc, Cetin |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.002 seconds