Efficient design of Elliptic Curve Point Multiplication based on fast Montgomery modular multiplication

摘要

In Elliptic Curve Cryptography (ECC), Elliptic Curve Point Multiplication (ECPM) is one of the most critical operations. In this paper, based on RNS Montgomery modular multiplication, an optimized ECPM architecture is proposed. The proposed architecture encompasses fast RNS to RNS converter with choosing appropriate moduli sets. The proposed RNS bases in first moduli set employs the basis with small Hamming weight based on the work reported in literature and the moduli set {2^n+β, 2ⁿ − 1,2ⁿ + 1,2ⁿ − 2^(n+1)/2 + 1,2ⁿ + 2ⁿ⁺¹/2} + 1, 2ⁿ⁻¹ +1} in the second base, with efficient reverse converter is employed. To design the fast RNS to RNS converter, delay of binary to residue converter from first to second basis is improved. Hardware design for critical moduli in second bases which is the moduli 2ⁿ + 2^(n+1)/2 + 1 is done. Based on achieved hardware for reduction in moduli 2ⁿ + 2^(n+1)/2 + 1, the delay requirements of the new converter is shown to be less than another reported converter. Compared to state-of-the-art implementations in the literature, the results shows that the proposed ECPM architecture achieves speed increase of 4%, 42%, 35% and 38% for p =160, 192, 224 and 256 bits respectively.