GPU and ASIC Acceleration of Elliptic Curve Scalar Point Multiplication

Karl Bernard Leboeuf, University of Windsor


As public information is increasingly communicated across public networks such as the internet, the use of public key cryptography to provide security services such as authentication, data integrity, and non-repudiation is ever-growing. Elliptic curve cryptography is being used now more than ever to fulfill the need for public key cryptography, as it provides security equivalent in strength to the entrenched RSA cryptography algorithm, but with much smaller key sizes and reduced computational cost. All elliptic curve cryptography operations rely on elliptic curve scalar point multiplication. In turn, scalar point multiplication depends heavily on finite field multiplication. In this dissertation, two major approaches are taken to accelerate the performance of scalar point multiplication. First, a series of very high performance finite field multiplier architectures have been implemented using domino logic in a CMOS process. Simulation results show that the proposed implementations are more efficient than similar designs in the literature when considering area and delay as performance metrics. The proposed implementations are suitable for integration with a CPU in order to provide a special-purpose finite field multiplication instruction useful for accelerating scalar point multiplication. The next major part of this thesis focuses on the use of consumer computer graphics cards to directly accelerate scalar point multiplication. A number of finite field multiplication algorithms suitable for graphics cards are developed, along with algorithms for finite field addition, subtraction, squaring, and inversion. The proposed graphics-card finite field arithmetic library is used to accelerate elliptic curve scalar point multiplication. The operation throughput and latency performance of the proposed implementation is characterized by a series of tests, and results are compared to the state of the art. Finally, it is shown that graphics cards can be used to significantly increase the operation throughput of scalar point multiplication operations, which makes their use viable for improving elliptic curve cryptography performance in a high-demand server environment.