Hardware Design of a 256-Bit Prime Field Multiplier Suitable for Computing Bilinear Pairings

We present a hardware-oriented architecture able to compute a 256-bit prime finite field multiplication efficiently. Taking advantage of the Karatsuba algorithm, the proposed architecture splits a 256-bit integer multiplication into fourteen 64-bit sub-products plus a number of additions that are performed using parallel and pipelined arrangements. The resulting 512-bit partial product is reduced into a 256-bit integer using a polynomial variant of the Montgomery reduction algorithm. The multiplier architecture presented here can be directly adapted for computing bilinear pairings over Barreto-Naehrig curves. In order to improve the performance of our design, the architecture makes use of twelve DSP48 slices, which are high-performance built-in blocks available in the Xilinx Virtex-6 family of FPGA devices.