Architectural Support for Arithmetic in Optimal Extension Fields

Johann Großschädl, Sandeep Kumar, Chris­tof Paar

IEEE 15th International Conference on Application-specific Systems, Architectures and Processors (ASAP) 2004, Galveston, Texas, September 27-29, 2004.


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 ?nite ?elds of large order. The focus of the present work is directed towards a special type of ?nite ?elds, the so-called Optimal Extension Fields GF(p m ) where p is a pseudo-Mersenne (PM) prime of the form p = 2 n?c that ?ts into a single register. Based on theMIPS32 instruction set architecture, we introduce two custom instructions to accelerate the reduction modulo a PM prime. Moreover, we show that the 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 over?ow. 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.