Efficient Elliptic Curve Point Multiplication using Digit Serial Binary Field Operations

Additional material for published paper

In this page you can found the VHDL codes, additional figures and more experimental data of the article:

Gustavo Sutter, Jean-Pierre Deschamps, José Luis Imaña, Fast Elliptic Curve Point Multiplication using Digit Serial Galois Field Operations. in IEEE Transactions on Industrial Electronics Jan 2013 (DOI: 10.1109/TIE.2012.2186104) (Link to IEEExplore)

Summary

Abstract—This paper details the design of a new high-speed point multiplier for elliptic curve cryptography (ECC) using either field-programmable gate-array (FPGA) or ASIC technology. Different levels of digit serial computation were applied to the data path of Galois Field (GF) multiplication and division to explore the resulting performances and find out an optimal digit size. We provide results for the five NIST (National Institute of Standards and Technology) recommended curves, outperforming the previous published results. In GF(2^163 ) we achieve a point multiplication in 19.38 ns in a Xilinx Virtex-E. Using the modern Xilinx Virtex-5 the point multiplication time in GF(2^m ), for m=163, 233, 283, 409 and 571 are 5.5, 17.8, 33.6, 102.6 and 384 ns respectively, which are the fastest figure reported to date.

Index Terms— Public key cryptography, elliptic curve cryptography (ECC), field-programmable gate array (FPGA), digit serial computation.

VHDL codes:

The naive implementation using projective coordinates and bit serial GF multiplication and GF division

* The top level  design (Montgomery_projective.vhd). The data path instantiating the multiplier, divider, squarer and addition (Montgomery_projective_data_path.vhd). The simple GF multiplier (interleaved_mult.vhd). The binary algorithm implementation for division (binary_algorithm_polynomials.vhd). A simple squarer (classic_squarer.vhd). A do fail to test the design (test_point_mult.do). 

The proposed architecture using three digit serial multiplier and one digit serial divider.

* The top level  design including the control FSM (Montgomery_projective3M.vhd). The data path instantiating 3 multipliers and one divider (Montgomery_projective3M_data_path.vhd). The efficient digit serial GF multiplier (interleaved_adv_mult.vhd). The advanced digit serial divider (kh_divider_adv.vhd). A simple squarer (classic_squarer.vhd). A simpel VHDL test bench file for GF(2^163) (test_trivial_K163_point_mult.vhd).

Please contact us for more information and the codes of avaneced versions.

More Finite field circuits

You can find more finite field circuits from the example page of Hardware Implementation of Finite-Field Arithmetic (Deschamps/Imaña/Sutter, 2009). ISBN 978-0-0715-4581-5 - McGrawHill (Book examples page)

Additional Figures:

*Data path of Basic Algorithm for point Multiplication (Algorithm 2). (Algorithm 2 Data Path.pdf)

* NIST recommended polynomials (NIST recommended polynomials.pdf)

* Figures of area-delay for point multiplication using different amount of multipliers and dividers. for GF(2^163), GF(2 ^233), GF(2^283), GF(2^409), GF(2^571)

More Experimental Data:

Modular Multiplication for GF(2^163), GF(2^233), GF(2^273), GF(2^409), and GF(2^571) (Digit Serial Multiplication Area and Delay for the 5 NIST Polinomials.pdf)

Modular  Dividers for GF(2^163), GF(2^233), GF(2^273), GF(2^409), and GF(2^571) (Digit Serial Divider Area and Delay for the 5 NIST Polinomials.pdf)

Point multiplication area time trade off using different multipliers and dividers for GF(2^163) in Virtex5 (Point Multiplication area-time for  m163.pdf), the corresponding figures (Figure for point multiplication area-time for  m163.pdf)

Point multiplication area time trade off using different multipliers and dividers for GF(2^233) in Virtex5 (Point Multiplication area-time for  m233.pdf), the corresponding figures (Figure for point multiplication area-time for  m233.pdf)

Point multiplication area time trade off using different multipliers and dividers for GF(2^283) in Virtex5 (Point Multiplication area-time for  m283.pdf), the corresponding figures (Figure for point multiplication area-time for  m283.pdf)

Point multiplication area time trade off using different multipliers and dividers for GF(2^409) in Virtex5 (Point Multiplication area-time for  m409.pdf), the corresponding figures (Figure for point multiplication area-time for  m409.pdf)

Point multiplication area time trade off using different multipliers and dividers for GF(2^571) in Virtex5 (Point Multiplication area-time for  m571.pdf), the corresponding figures (Figure for point multiplication area-time for  m571.pdf)