Implementation of elliptic curve cryptosystems over GF(2n) in optimal normal basis on a reconfigurable computer

ABSTRACT

During the last few years, a considerable effort has been devoted to the development of reconfigurable computers, machines that are based on the close interoperation of traditional microprocessors and Field Programmable Gate Arrays. Several prototype machines of this type have been designed, and demonstrated significant speed-ups compared to conventional workstations for computationally intensive problems, such as codebreaking. In this paper, we demonstrate an efficient implementation of Elliptic Curve scalar multiplication over GF(2 n ) in Optimal Normal Basis, using one of the leading reconfigurable computers available on the market, SRC-6E. We show how the hardware architecture and programming model of this reconfigurable computer has influenced the choice of the optimum program partitioning scheme. The detailed analysis of the control, data transfer, and reconfiguration overheads is given in the paper. The end-to-end speed-ups in the range from 895 to 1300 compared to the microprocessor implementation are demonstrated depending on the chosen partitioning scheme.