Parameter Selection Refinement and Software Implementations of Spectral Modular Exponentiation

Abstract

A consistent challenge to the widespread use public key cryptosystems, such as RSA, is the computational difficulty of performing arithmetic operations with large operands. There are many branches of mathematics and algorithms devoted to the exploration of different aspects of computer arithmetic on large integers. In this thesis, we outline several parameter selection techniques and software implementations that apply to a new technique of exponentiation, referred to as spectral modular exponentiation, which attempts to address computational efficiency of public key cryptosystems, such as RSA and Elliptic Curve Cryptosystems. Spectral modular exponentiation (SME) is a method by which numbers are converted into spectral representations through a process known as Discrete Fourier Transform (DFT), at some initial cost in doing the transformations. The spectral domain has the advantage of greatly reduced multiplication cost during the most costly portions of exponentiation. This thesis will describe the different algorithms that have been proposed independently by two different research groups, compare and contrast these algorithms, and describe various parameter selection techniques that apply to them. It will also cover lessons learned and some difficulties encountered in the development of a working implementation of spectral modular exponentiation. This thesis will also addresses some of the discovered concerns regarding particular approaches to spectral modular exponentiation in software implementations. These difficulties involve the inherent limitations of the algorithm in software and the theoretical potential of performance in hardware. Variations on implementations were attempted to test different environments for the algorithm, but software implementations of spectral modular exponentiation were still characterized by performance less than that of existing algorithms, even at larger operand sizes. Included in this thesis are the actual calculated and verified results for several of these variations. These results include the initial generated parameters, internal interim values, and final results that would be necessary to verify the correctness of future algorithms and implementations. These interim values serve as parameters and interim value references to future attempts for working implementations in both hardware and software. The hardware implementations of spectral modular exponentiation still show possibility for better comparable performance than traditional algorithms. Also in this thesis are two proofs that demonstrate how to reliably generate parameters for a valid DFT and inverse DFT transformation. These are based on multiple previous works on characteristics of Mersenne and Fermat numbers and connecting those characteristics to the requirements for a valid DFT.