title   
  

Efficient unified Montgomery inversion with multibit shifting

Savaş, Erkay and Naseer, Mansoor and Gutub, Adnan Abdül-Aziz and Koç, C. K. (2004) Efficient unified Montgomery inversion with multibit shifting. (Accepted/In Press)

WarningThere is a more recent version of this item available.

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
241Kb

Abstract

Computation of multiplicative inverses in finite fields GF(p) and GF(2/sup n/) is the most time-consuming operation in elliptic curve cryptography, especially when affine co-ordinates are used. Since the existing algorithms based on the extended Euclidean algorithm do not permit a fast software implementation, projective co-ordinates, which eliminate almost all of the inversion operations from the curve arithmetic, are preferred. In the paper, the authors demonstrate that affine co-ordinate implementation provides a comparable speed to that of projective co-ordinates with careful hardware realisation of existing algorithms for calculating inverses in both fields without utilising special moduli or irreducible polynomials. They present two inversion algorithms for binary extension and prime fields, which are slightly modified versions of the Montgomery inversion algorithm. The similarity of the two algorithms allows the design of a single unified hardware architecture that performs the computation of inversion in both fields. They also propose a hardware structure where the field elements are represented using a multi-word format. This feature allows a scalable architecture able to operate in a broad range of precision, which has certain advantages in cryptographic applications. In addition, they include statistical comparison of four inversion algorithms in order to help choose the best one amongst them for implementation onto hardware.

Item Type:Article
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:601
Deposited By:Erkay Savaş
Deposited On:14 Oct 2005 03:00
Last Modified:08 May 2009 14:25

Available Versions of this Item

Repository Staff Only: item control page