New hardware algorithms and designs for Montgomery modular inverse computation in Galois Fields GF(p) and GF(2 [superscript n]) Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/k35697382

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • The computation of the inverse of a number in finite fields, namely Galois Fields GF(p) or GF(2ⁿ), is one of the most complex arithmetic operations in cryptographic applications. In this work, we investigate the GF(p) inversion and present several phases in the design of efficient hardware implementations to compute the Montgomery modular inverse. We suggest a new correction phase for a previously proposed almost Montgomery inverse algorithm to calculate the inversion in hardware. It is also presented how to obtain a fast hardware algorithm to compute the inverse by multi-bit shifting method. The proposed designs have the hardware scalability feature, which means that the design can fit on constrained areas and still handle operands of any size. In order to have long-precision calculations, the module works on small precision words. The word-size, on which the module operates, can be selected based on the area and performance requirements. The upper limit on the operand precision is dictated only by the available memory to store the operands and internal results. The scalable module is in principle capable of performing infinite-precision Montgomery inverse computation of an integer, modulo a prime number. We also propose a scalable and unified architecture for a Montgomery inverse hardware that operates in both GF(p) and GF(2ⁿ) fields. We adjust and modify a GF(2ⁿ) Montgomery inverse algorithm to benefit from multi-bit shifting hardware features making it very similar to the proposed best design of GF(p) inversion hardware. We compare all scalable designs with fully parallel ones based on the same basic inversion algorithm. All scalable designs consumed less area and in general showed better performance than the fully parallel ones, which makes the scalable design a very efficient solution for computing the long precision Montgomery inverse.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Submitted by Kevin Martin (martikev@onid.orst.edu) on 2012-06-26T18:03:17ZNo. of bitstreams: 1GutubAdnanAA2003.pdf: 966653 bytes, checksum: 14e65db1bb7f98c390625da99a4394ac (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-06-28T21:57:29Z (GMT) No. of bitstreams: 1GutubAdnanAA2003.pdf: 966653 bytes, checksum: 14e65db1bb7f98c390625da99a4394ac (MD5)
  • description.provenance : Made available in DSpace on 2012-07-26T19:02:58Z (GMT). No. of bitstreams: 1GutubAdnanAA2003.pdf: 966653 bytes, checksum: 14e65db1bb7f98c390625da99a4394ac (MD5) Previous issue date: 2002-06-11
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-07-26T19:02:58Z (GMT) No. of bitstreams: 1GutubAdnanAA2003.pdf: 966653 bytes, checksum: 14e65db1bb7f98c390625da99a4394ac (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items