Mason Archival Repository Service

Number Field Sieve: Pseudocodes and Software Implementation

Show simple item record

dc.contributor.advisor Gaj, Kris
dc.contributor.author Winograd, Theodore Kemp
dc.creator Winograd, Theodore Kemp
dc.date 2011-12-07
dc.date.accessioned 2012-01-30T21:14:34Z
dc.date.available NO_RESTRICTION en_US
dc.date.available 2012-01-30T21:14:34Z
dc.date.issued 2012-01-30
dc.identifier.uri https://hdl.handle.net/1920/7485
dc.description.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.
dc.language.iso en_US en_US
dc.subject Factoring en_US
dc.subject Cryptography en_US
dc.subject Number Field Sieve en_US
dc.subject RSA en_US
dc.title Number Field Sieve: Pseudocodes and Software Implementation en_US
dc.type Thesis en
thesis.degree.name Masters in Computer Engineering en_US
thesis.degree.level Master's en
thesis.degree.discipline Computer Engineering en
thesis.degree.grantor George Mason University en


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search MARS


Advanced Search

Browse

My Account

Statistics