Efficient Elliptic Curve Processor Architectures for Field Programmable Logic

E–cient Elliptic Curve Processor Architectures for Field Programmable Logic by Gerardo Orlando A Dissertation Submitted to the Faculty of the WORCESTER POLYTECHNIC INSTITUTE in partial fulflllment of the requirements for the Degree of Doctor of Philosophy in Electrical Engineering by March 4, 2002 APPROVED: Dr. Christof Paar Dissertation Advisor ECE Department Dr. Fred J. Looft Dissertation Committee ECE Department Dr. Berk Sunar Dissertation Committee ECE Department Dr. Wayne P. Burleson Dissertation Committee ECE Department University of Massacusetts Dr. John Orr Head of ECE Department Abstract Elliptic curve cryptosystems ofier security comparable to that of traditional asymmetric cryptosystems, such as those based on the RSA encryption and digital signature algorithms, with smaller keys and computationally more e–cient algo- rithms. The ability to use smaller keys and computationally more e–cient algo- rithms than traditional asymmetric cryptographic algorithms are two of the main reasons why elliptic curve cryptography has become popular. As the popularity of elliptic curve cryptography increases, the need for e–cient hardware solutions that accelerate the computation of elliptic curve point multiplications also increases. This dissertation introduces elliptic curve processor architectures suitable for the computation of point multiplications for curves deflned over flelds GF(2m) and curves deflned over flelds GF(p). Each of the processor architectures presented here allows designers to tailor the performance and hardware requirements according to their performance and cost goals. Moreover, these architectures are well suited for implementation in modern fleld programmable gate arrays (FPGAs). This point was proved with prototyped implementations. The fastest prototyped GF(2m) processor can compute an arbitrary point multiplication for curves deflned over flelds GF(2167) in 0.21 milliseconds and the prototyped processor for the fleld GF(2192 ¡264 ¡1) is capable of computing a point multiplication in about 3.6 milliseconds. The most critical component of an elliptic curve processor is its arithmetic unit. A typical arithmetic unit includes an adder/subtractor, a multiplier, and possibly a squarer. Some of the architectures presented in this work are based on multiplier and squarer architectures developed as part of the work presented in this disser- tation. The GF(2m) least signiflcant bit super-serial multiplier architecture, the GF(2m) most signiflcant bit super-serial multiplier architecture, and a new GF(p) Montgomery multiplier architecture were developed as part of this work together with a new squaring architecture for GF(2m). Acknowledgements Theworkpresentedinthisdissertationistheresultsof overfouryearsof research. I want to thank Christof Paar for advising me throughout this research work. I also want to thank the members of the dissertation committee, Berk Sunar, Fred J. Looft, and Wayne P. Burleson, for reviewing this work. The majority of the research work presented here was done on a part-time basis while I worked as an engineer. I want to thank Julian Bubrowski, Walter Schneider, and Jim Sheedy for allowing me to balance my professional work with my research work. This work would have not been possible without their help. Finally, this work will not have been possible without the love and moral support of my sisters Clara and Marian, my mother Maria, and my father Juan. Lastly but not least, I want to acknowledge that the love and understanding of my wife Diane, my son Leonardo, and my daughter Jane carried me over the flnish line. i Contents 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Summary of Research Contributions . . . . . . . . . . . . . . . . . . 5 1.3 Dissertation Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Background 9 2.1 Finite Field Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 GF(p) Arithmetic Background . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Montgomery Reduction . . . . . . . . . . . . . . . . . . . . . . 13 2.3 GF(2m) Arithmetic Background . . . . . . . . . . . . . . . . . . . . 16 2.4 Elliptic Curve Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Elliptic Curve Discrete Logarithm Problem (ECDLP) . . . . . . . . . 25 2.6 Coordinate Representation . . . . . . . . . . . . . . . . . . . . . . . . 27 2.7 Special Coordinates and Algorithms . . . . . . . . . . . . . . . . . . . 33 2.7.1 Montgomery Point Multiplication Algorithm for GF(2m) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.7.2 Jacobi Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.8 Point Multiplication Algorithms . . . . . . . . . . . . . . . . . . . . . 39 2.8.1 Generic Point Multiplication Algorithms . . . . . . . . . . . . 40 ii ... - tailieumienphi.vn