Instruction set extensions for the acceleration of finite field arithmetic

Existing hardware and software solutions are not sufficient to address the need for high-performance, low power and cost efficient mobile computing. Elliptical curve cryptography and linear block error correcting codes are two important disciplines for modern communication protocols. The primary roadblock to implementing an efficient design is the need for finite field arithmetic. Extending an instruction set by providing finite field arithmetic units is the best solution for current and future demand. Extensions allow backward compatibility and software can incrementally adopt the new feature set. This will also accelerate the adoption of strong cryptography to mainstream markets. Today's processors do not support any specific enhancements to deal with either the finite field types or arithmetic governing them. Instruction set extensions are a novel way to provide increased performance for existing microprocessors and by accelerating finite field arithmetic rather than a particular protocol, standard changes require only software updating. This research develops a complete finite field arithmetic instruction set and demonstrates its integration within an embedded processing framework. The development of the Finite Field Unit (FFU) serves as research vehicle to accelerate design space exploration of finite field instructions and their associated function units. Both Xilinx MicroBlaze and MIPS DLX processors are integrated with the FFU to examine the benefits of the instructions as well as develop high performance arithmetic functions. This work led to the development of an efficient Auxiliary Processing Unit (APU) that is an interface between the processor and FFU. Integrating the MicroBlaze embedded processor with the FFU proved to offer substantial performance improvements to both error correcting and elliptical curve algorithms. Overall, the FFU provides more than a 200x speed-up to finite field multiplication in GF(2163). The FFU demonstrates a more than 325x speed-up versus its non-accelerated self and 8.79x versus a Pentium IV when performing scalar point multiplication.