Title page for ETD etd-0328100-225237

Document Type thesis

Author Name Guajardo, Jorge

Email Address guajardo at ece.wpi.edu

URN etd-0328100-225237

Title Efficient Algorithms for Elliptic Curve Cryptosystems

Degree MS

Department Electrical & Computer Engineering

Advisors
Dr. Christof Paar, Advisor
Dr. David Cyganski, Committee
Dr. Gabor Sarkozy, Committee
Dr. Robert Dulude, Committee
Dr. John Orr, Department Head

Keywords
cryptography
elliptic curves
Galois Fields

Date of Presentation/Defense 1997-05-03

Availability unrestricted

Abstract
Elliptic curves are the basis for a relative new class of public-key schemes. It is predicted that elliptic curves will replace many existing schemes in the near future. It is thus of great interest to develop algorithms which allow efficient implementations of elliptic curve crypto systems. This thesis deals with such algorithms.

Efficient algorithms for elliptic curves can be classified into low-level algorithms, which deal with arithmetic in the underlying finite field and high-level algorithms, which operate with the group operation. This thesis describes three new algorithms for efficient implementations of elliptic curve cryptosystems. The first algorithm describes the application of the Karatsuba-Ofman Algorithm to multiplication in composite fields GF((2ⁿ)^m). The second algorithm deals with efficient inversion in composite Galois fields of the form GF((2ⁿ)^m). The third algorithm is an entirely new approach which accelerates the multiplication of points which is the core operation in elliptic curve public-key systems. The algorithm explores computational advantages by computing repeated point doublings directly through closed formulae rather than from individual point doublings. Finally we apply all three algorithms to an implementation of an elliptic curve system over GF((2¹⁶)¹¹). We provide ablolute performance measures for the field operations and for an entire point multiplication. We also show the improvements gained by the new point multiplication algorithm in conjunction with the k-ary and improved k-ary methods for exponentiation.

Files
guajardo.pdf

Browse by Author | Browse by Department | Search all available ETDs

Questions? Email etd-questions@wpi.edu
Maintained by webmaster@wpi.edu

Document Type	thesis
Author Name	Guajardo, Jorge
Email Address	guajardo at ece.wpi.edu
URN	etd-0328100-225237
Title	Efficient Algorithms for Elliptic Curve Cryptosystems
Degree	MS
Department	Electrical & Computer Engineering
Advisors	Dr. Christof Paar, Advisor Dr. David Cyganski, Committee Dr. Gabor Sarkozy, Committee Dr. Robert Dulude, Committee Dr. John Orr, Department Head
Keywords	cryptography elliptic curves Galois Fields
Date of Presentation/Defense	1997-05-03
Availability	unrestricted
Abstract Elliptic curves are the basis for a relative new class of public-key schemes. It is predicted that elliptic curves will replace many existing schemes in the near future. It is thus of great interest to develop algorithms which allow efficient implementations of elliptic curve crypto systems. This thesis deals with such algorithms. Efficient algorithms for elliptic curves can be classified into low-level algorithms, which deal with arithmetic in the underlying finite field and high-level algorithms, which operate with the group operation. This thesis describes three new algorithms for efficient implementations of elliptic curve cryptosystems. The first algorithm describes the application of the Karatsuba-Ofman Algorithm to multiplication in composite fields GF((2ⁿ)^m). The second algorithm deals with efficient inversion in composite Galois fields of the form GF((2ⁿ)^m). The third algorithm is an entirely new approach which accelerates the multiplication of points which is the core operation in elliptic curve public-key systems. The algorithm explores computational advantages by computing repeated point doublings directly through closed formulae rather than from individual point doublings. Finally we apply all three algorithms to an implementation of an elliptic curve system over GF((2¹⁶)¹¹). We provide ablolute performance measures for the field operations and for an entire point multiplication. We also show the improvements gained by the new point multiplication algorithm in conjunction with the k-ary and improved k-ary methods for exponentiation.
Files	guajardo.pdf