Number Field Sieve: Pseudocodes and Software Implementation
Date
2012-01-30
Authors
Winograd, Theodore Kemp
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The RSA cryptosystem has been the mainstay of modern cryptography since it was first introduced in 1978. RSA serves as the basis for securing modern e-commerce–it functions as the primary key exchange mechanism for the Secure Sockets Layer (SSL) protocol. It is used by US Government Personal Identity Verification (PIV) smart cards and the Department of Defense Common Access Card (CAC) for authenticating users, digitally signing and encrypting email. Due to the importance of this algorithm, cryptanalysts have been working for decades to identify weaknesses in the algorithm. Because the security of the RSA algorithm rests on the computational infeasibility of factoring large numbers, a good deal of research has been in the field of factorization. Of note was the introduction of the Number Field Sieve in 1993, which remains the fastest known algorithm for factoring large numbers. One of the most difficult aspects of the Number Field Sieve is the complexity of the algorithm, requiring a great deal of number theory simply to understand how the individual steps of the algorithm function. To this end, there are very few implementations of the algorithm that are coupled with concise and detailed descriptions of the algorithm. This thesis describes an implementation of the Number Field Sieve implemented using C++ in a straightforward manner–leaving efforts to improve this particular implementation as future work. Based on the implementation, the author was able to derive a set of pseudocodes that can be provided to students to gain a full understanding of the number field sieve algorithm. Finally, this thesis performs a number of experiments on this implementation–as well as other open source implementations that have been developed in the past few years. This thesis aims to identify the trade-offs within the algorithm that can be made based on the wide variety of parameters that can be applied. While some of these trade-offs are to be expected (e.g., the performance impact of using a lattice sieve over a line sieve), a more detailed understanding of the various options will aid both implementers and students in improving software implementations and–where possible–identifying methods for breaking the number field sieve algorithm into components and identifying which components are best implemented in hardware and which components are best implemented in software.
Description
Keywords
Factoring, Cryptography, Number Field Sieve, RSA