Alan Daly graduated in 2005.
Masters Thesis Title: Architectures for Public Key Cryptography
Abstract: As the volume of electronic communications continues to grow with the popularity of portable computing devices such as the third generation of mobile phones, palm-top PC’s and smart cards, data security is more important than ever before. The fundamental requirements of a secure communications network include data confidentiality, integrity, authentication, and non-repudiation. These functions are provided by public key cryptography, a concept first proposed by Diffie and Hellman in 1976. Soon after it’s inception, the RSA cryptosystem was invented, and has since been the most widely used public key cryptosystem. The underlying arithmetic operation in RSA, as well as other well known public key systems such as ElGamal, the digital signature algorithm and Diffie-Hellman key exchange, is modular exponentiation on integers which are typically 1024-bits or greater. A new branch of public key cryptography based on elliptic curves in finite fields was independently proposed by Miller and Koblitz in the mid-eighties. Elliptic Curve Cryptography (ECC) offers equivalent security to RSA with much shorter key sizes. It is estimated that a 160-bit ECC key provides equivalent security to a 1024-bit RSA key. The underlying elliptic curve point operations require modular multiplication, inversion, division and addition/subtraction.
This thesis investigates algorithms and architectures to efficiently implement the modular arithmetic required in public key cryptosystems. Montgomery’s algorithm is chosen to perform modular multiplication without the need for trial division, and modifications are made to the basic algorithm to improve its hardware implementation. Several multiplier architectures are proposed, taking into consideration the target FPGA (Field Programmable Gate Array) platform. A novel pipelined multiplexer-based design using carry-propagate adders is compared to radix-2 and radix-4 carry-save multipliers. These multipliers are then used to instantiate modular exponentiation architectures and construct a full RSA encryption co-processor implemented on a prototyping PCI card.
A thorough investigation of modular inversion methods is performed and two architectures based on the extended Euclidean algorithm are proposed. Both architectures perform the computation of all possible intermediate results at each clock cycle and the result is selected upon completion of full magnitude comparisons. This eliminates the magnitude comparisons from the critical paths of the designs. The second, novel architecture employs a carry-select method to halve the critical carry chain and thus avoid the carry-chain overflow routing problem which is found to cause significant delays in FPGA design. The first two known hardware implementations of Shantz’s modular division are proposed based on architectures similar to the modular inversion architectures already investigated. The operations of direct modular division, and division by modular inversion followed by multiplication are compared in terms of operation speed and chip area. Finally, two GF(p) arithmetic units are proposed and compared. The first can perform all ECC modular operations in affine or projective coordinates and includes a dedicated modular inversion function. The second arithmetic unit does not include a dedicated inversion function, and is therefore not suited to point operations in affine coordinates. However a dual mode functionality allows the arithmetic unit to be pipelined to implement both ECC and RSA cryptosystems. This is important as ECC begins to take over from RSA as the most commonly used public key cryptosystem, and devices will have to be capable of supporting both systems.