Computation in optimal extension fields.

by Bailey, Daniel V.

This thesis focuses on a class of Galois field used to achieve fast finite field arithmetic which we call Optimal Extension Fields (OEFs), first introduced in [BP98]. We extend this work by presenting an adaptation of Itoh and Tsujii’s algorithm for finite field inversion applied to OEFs. In particular, we use the facts that the action of the Frobenius map in GF (pm) can be computed with only m ? 1 subfield multiplications and that inverses in GF (p) may be computed cheaply using known techniques. As a result, we show that one extension field inversion can be computed with a logarithmic number of extension field multiplications. In addition, we provide new variants of the Karatsuba-Ofman algorithm for extension field multiplication which give a performance increase. Further, we provide an OEF construction algorithm together with tables of Type I and Type II OEFs along with statistics on the number of pseudo-Mersenne primes and OEFs. We apply this new work to provide implementation results for elliptic curve cryptosystems on both DEC Alpha workstations and Pentium-class PCs. These results show that OEFs when used with our new inversion and multiplication algorithms provide a substantial performance increase over other reported methods. iii Preface This thesis represents the culmination of a child-like fascination with the world of cryptography. On August 13-14, 1994, I was persuaded by an old friend from high school named Rich Pell to attend a conference called Hackers on Planet Earth. This gathering of hackers, phreakers, Feds, geeks, and other social misfits was held in New York City to mark the tenth anniversary of 2600 Magazine. We were kids fascinated by the vulnerabilities present in the computing and ideological systems which were so quickly changing our world. At the conference, Bruce Schneier and Matt Blaze gave a panel discussion on cryptography. Years before the explosion of the Internet and electronic commerce, the field of cryptography had not blossomed to its current state of public awareness. They spoke about a new book by Mr. Schneier which had just been published called Applied Cryptography. It blew me away. It piqued my curiousity to such a degree that I find myself six years later writing my own thesis on the subject. I devoured Applied Cryptography in short order and was inspired to focus my energies on doing research in cryptography. This decision meant a return to full-time study which I’d abandoned in late 1993. In looking for a university to resume my education, I was persuaded by Amy Bernheisel to cast my gaze toward Massachusetts. Eventually I decided to attend WPI starting in the fall of 1995, where a new professor had just been hired by the name of Christof Paar, whose research interest was cryptography. Since then, Professor Paar has been my advisor through classes, papers, and projects. Thus I got my wish to iv explore the fascinating world of cryptography, and I cannot sufficiently thank those who made it possible. So I dedicate this thesis to Rich Pell, Bruce Schneier, Matt Blaze, Amy Bernheisel, and Christof Paar, without whom none of this would have been necessary.