Efficient algorithms for elliptic curve cryptosystems on embedded systems.

by Woodbury, Adam D.

This thesis describes how an elliptic curve cryptosystem can be implemented on low cost microprocessors without coprocessors with reasonable performance. We focus in this paper on the Intel 8051 family of microcontrollers popular in smart cards and other cost-sensitive devices, and on the Motorola Dragonball, found in the Palm Computing Platform. The implementation is based on the use of the Optimal Extension Fields GF ((28 ? 17)17) for low end 8-bit processors, and GF ((213 ? 1)13) for 16-bit processors. Two advantages of our method are that subfield modular reduction can be performed infrequently, and that an adaption of Itoh and Tsujii’s inversion algorithm may be used for the group operation. We show that an elliptic curve scalar multiplication with a fixed point, which is the core operation for a signature generation, can be performed in a group of order approximately 2134 in less than 2 seconds on an 8-bit smart card. On a 16-bit microcontroller, signature generation in a group of order approximately 2169 can be performed in under 700 milliseconds. Unlike other implementations, we do not make use of curve parameters defined over a subfield such as Koblitz curves. iii Preface This work details the research I conducted at Worcester Polytechnic Institute in pursuit of my Master’s degree. I would first like to thank Prof. Christof Paar, who has been my advisor, mentor, and friend since I began my studies with him. Working with Prof. Paar has taken me to foreign lands, presented amazing opportunities, and introduced me to the legends of the field. It was solely my desire to do further work in cryptography with Prof. Paar that led me to continue my studies at WPI. I would like to thank my Thesis committee, Prof. Berk Sunar and Prof. William Martin for their time and suggestions. I am grateful for their acceptance of my unreasonable requests and timeline. I would like to thank Dan Bailey, Brendon Chetwynd, Adam Elbirt, Jorge Guajardo, Carleton Jillson, Andre Weimerskirch, and Thomas Wollinger for such a great atmosphere in and surrounding the Cryptography lab. Finally, and most importantly I would like to dedicate this thesis to Sandra, my wife. She was willing to live with me in a graduate student’s life (and meager pay) so that I was able to study for my Master’s degree. She has sacrificed more than I care to mention here, and it is my intention to make it up to her some day. I thank her for this chance, as this graduate work has been more rewarding than I could have imagined. Adam D. Woodbury