Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-0501103-132249


Document Typethesis
Author NameBaktir, Selcuk
URNetd-0501103-132249
TitleEfficient Algorithms for Finite Fields, with Applications in Elliptic Curve Cryptography
DegreeMS
DepartmentElectrical & Computer Engineering
Advisors
  • Berk Sunar, Advisor
  • William J. Martin, Committee Member
  • Kaveh Pahlavan, Committee Member
  • John A. Orr, Department Head
  • Keywords
  • multiplication
  • OTF
  • optimal extension fields
  • finite fields
  • optimal tower fields
  • cryptography
  • OEF
  • inversion
  • finite field arithmetic
  • elliptic curve cryptography
  • Date of Presentation/Defense2003-04-21
    Availability unrestricted

    Abstract

    This thesis introduces a new tower field representation, optimal tower fields (OTFs), that facilitates efficient finite field operations. The recursive direct inversion method presented for OTFs has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of OTF inversion algorithm is shown to be O(m^2), significantly better than that of the Itoh-Tsujii algorithm, i.e. O(m^2(log_2 m)). This complexity is further improved to O(m^(log_2 3)) by utilizing the Karatsuba-Ofman algorithm. In addition, it is shown that OTFs are in fact a special class of OEFs and OTF elements may be converted to OEF representation via a simple permutation of the coefficients. Hence, OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. While the original OTF multiplication and squaring operations require slightly more additions than their OEF counterparts, due to the free conversion, both OTF operations may be achieved with the complexity of OEF operations. Furthermore, efficient finite field algorithms are introduced which significantly improve OTF multiplication and squaring operations.

    The OTF inversion algorithm was implemented on the ARM family of processors for a medium and a large sized field whose elements can be represented with 192 and 320 bits, respectively. In the implementation, the new OTF inversion algorithm ran at least six to eight times faster than the known best method for inversion in OEFs, i.e., Itoh-Tsujii inversion technique. According to the implementation results obtained, it is indicated that using the OTF inversion method an elliptic curve scalar point multiplication operation can be performed at least two to three times faster than the known best implementation for the selected fields.

    Files
  • Thesis.pdf

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

    [WPI] [Library] [Home] [Top]

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