Skip to main content
Kent Academic Repository

Fast arithmetic for public-key algorithms in Galois fields with composite exponents

Paar, C., Fleischmann, Peter, Soria-Rodriguez, P. (1999) Fast arithmetic for public-key algorithms in Galois fields with composite exponents. IEEE Transactions on Computers, 48 (10). pp. 1025-1034. ISSN 0018-9340. (doi:10.1109/12.805153) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:16426)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://dx.doi.org/10.1109/12.805153

Abstract

This contribution describes a new class of arithmetic architectures for Galois fields GF(2(k)). The main applications of the architecture are public-key systems which are based on the discrete logarithm problem fdr elliptic curves. The architectures use a representation of the field GF(2(k)) as GF((2(n))(m)), where k = n.m. The approach explores bit parallel arithmetic in the subfield GF(2(n)) and serial processing for the extension field arithmetic. This mixed parallel-serial (hybrid) approach can lead to fast implementations. As the core module, a hybrid multiplier is introduced and several optimizations are discussed. We provide two different approaches to squaring. We develop exact expressions for the complexity of parallel squarers in composite fields, which can have a surprisingly low complexity. The hybrid architectures are capable of exploring the time-space trade-off paradigm in a flexible manner. In particular, the number of dock cycles for one field multiplication, which is the atomic operation in most public-key schemes, can be reduced by a factor of n compared to other known realizations. The acceleration is achieved at the cost of an increased computational complexity. We describe a proof-of-concept implementation of an ASIC for multiplication and squaring in GF((2(n))(m)), m variable.

Item Type: Article
DOI/Identification number: 10.1109/12.805153
Uncontrolled keywords: Galois field; multiplication; squaring; VLSI; implementation; cryptography; elliptic curves
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Q Science > QA Mathematics (inc Computing science)
T Technology > TA Engineering (General). Civil engineering (General)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Mathematics, Statistics and Actuarial Science
Depositing User: F.D. Zabet
Date Deposited: 02 May 2009 18:49 UTC
Last Modified: 16 Nov 2021 09:54 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/16426 (The current URI for this page, for reference purposes)

University of Kent Author Information

Fleischmann, Peter.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.