Mason Archival Repository Service

Parameter Selection Refinement and Software Implementations of Spectral Modular Exponentiation

Show simple item record

dc.contributor.advisor Gaj, Kris Estes, Matthew
dc.creator Estes, Matthew 2010-07-23 2010-11-01T16:47:32Z NO_RESTRICTION en_US 2010-11-01T16:47:32Z 2010-11-01
dc.description.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.
dc.language.iso en_US en_US
dc.subject spectral en_US
dc.subject exponentiation en_US
dc.subject cryptography en_US
dc.subject modular en_US
dc.subject parameter en_US
dc.title Parameter Selection Refinement and Software Implementations of Spectral Modular Exponentiation en_US
dc.type Thesis en Master of Science Computer Engineering en_US Master's en Computer Engineering en George Mason University en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search MARS


My Account