Fast RNS Implementation of Elliptic Curve Point Multiplication on FPGAs

Elliptic curve cryptography is the second most important public-key cryptography following RSA cryptography. The fundamental arithmetic of elliptic curve cryptography is a series of modular multiplications and modular additions. Usually, Montgomery algorithm is applied for modular multiplications over large integers to reduce the computational complexity. Targeting at fast elliptic curve point multiplication over prime fields a new approach in residue number system is proposed. Compared with other implementations that apply Montgomery ladder for parallel elliptic curve point multiplication, the proposed method uses a residue number system with a wide dynamic range, which supports continuous multiplications and needs only one RNS Montgomery multiplication to bring down the temporary results to valid range. Hardware implementation results demonstrate that the computation time for elliptic curve point multiplication over Fp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_p$$\end{document} can be greatly reduced, and it takes about 0.677 ms to compute one time of elliptic curve point multiplication over 384-bit prime curves in Xilinx XC6VSX475t device, costing an area of 41409 slices, 676 DSPs and 138 Brams.