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.
