Iterative modular division over GF(2(m)): Novel algorithm and implementations on FPGA
(2006) 2nd International Workshop on Reconfigurable Computing — Location: Delft Univ Technol, Delft (Netherlands) (1.March.2006)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 493.61 KB
Details
- Authors
- Abstract
- Public key cryptography is a concept used by many useful functionalities such as digital signature, encryption, key agreements, For those needs, elliptic curve cryptography is an attractive solution. Cryptosystems based on elliptic curve need a costly modular division. Depending on the choice of coordinates, this operation is requested at each step of algorithms, during a precomputation phase or at the end of the whole computation. As a result, efficient modular division implementations are useful for both area constrained designs working in affine coordinates and high-speed processors. For that purpose, this work highlights the most efficient iterative modular, division algorithm and explores different time and area tradeoffs on FPGA. First, thanks to a novel algorithm, the computational time is divided by two with an area increase of one half. Second, using the Single-Instruction Multiple-Data feature of the selected algorithm, the area is divided by two with a doubling of the computational time. To the best of our knowledge, it is the first report about an iterative digit-serial modular division algorithm, the first area and time tradeoff analysis of an iterative algorithm and the best result among the very few implementations on FPGA.
- Affiliations
Citations
de Dormale, G. M., & Quisquater, J.-J. (2006). Iterative modular division over GF(2(m)): Novel algorithm and implementations on FPGA. Lecture Notes in Computer Science, 3985, 370-382. https://doi.org/10.1007/11802839_45 (Original work published 2006)