Optimizing Arithmetic for Public Key Cryptography

Spencer W. Hall, The College of Wooster

Abstract

Public key cryptography describes a family of systems that allow for secure communication between two parties in the presence of eavesdroppers. We examine the history of cryptography and how the advent of public key cryptography irreversibly changed the science. The Diffie-Hellman key exchange protocol and the RSA cryptosystem and their applications are described in detail, as well as the mathematical theory behind them. The concept of radix representations and radix-sensitive arithmetic algorithms are explored. We create a simple arbitrary precision integer arithmetic system in Java and explore how arithmetic algorithm choices affect the performance of RSA implementations and RSA-related arithmetic functions.