Architectural Support for Arithmetic in Optimal Extension Fields

Johann Großschädl, Sandeep S. Kumar, Christof Paar

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Abstract

Public-key cryptosystems generally involve computation-intensive arithmetic operations, making them impractical for software implementation on constrained devices such as smart cards. In this paper we investigate the potential of architectural enhancements and instruction set extensions for low-level arithmetic used in public-key cryptography, most notably multiplication in finite fields of large order. The focus of the present work is directed towards a special type of finite fields, the so-called Optimal Extension Fields FG(p^m) where p is a pseudo-Mersenne (PM) prime of the form p = 2^n - c that fits into a single register. Based on the MIPS32 instruction set architecture, we introduce two custom instructions to accelerate the reduction modulo a PM prime. Moreover, we show that multiplication in an Optimal Extension Field can take advantage of a multiply/accumulate unit with a wide accumulator so that a certain number of 64-bit products can be summed up without overflow. The proposed extensions support a wide range of PM primes and allow a reduction modulo 2^n - c to complete in only four clock cycles when n ≤ 32.
Original languageEnglish
Title of host publicationProceedings of the 15th IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP 2004)
Place of PublicationLos Alamitos, CA, USA
PublisherIEEE Computer Society Press
Pages111-124
ISBN (Print)0-7695-2226-2
DOIs
Publication statusPublished - 2004
Event15th IEEE International Conference on Application-Specific Systems, Architecture and Processors: ASAP 2004 - Galveston, TX, United States
Duration: 27 Sept 200429 Sept 2004

Conference

Conference15th IEEE International Conference on Application-Specific Systems, Architecture and Processors
Abbreviated titleASAP 2004
Country/TerritoryUnited States
CityGalveston, TX
Period27/09/0429/09/04

Treatment code (Nähere Zuordnung)

  • Application
  • Experimental

Fingerprint

Dive into the research topics of 'Architectural Support for Arithmetic in Optimal Extension Fields'. Together they form a unique fingerprint.

Cite this