Iterative modular division over GF(2/sup m/): novel algorithm and implementations on FPGA

De Dormale, G. Meurice;Quisquater, Jean-Jacques
(2006) Reconfigurable Computing: Architectures and Applications Second International Workshop, ARC 2006. Revised Selected Papers — Location: Delft, Netherlands (1.March.2006)

Files

No attached file found for this publication.

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 paper 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

  • APA
  • Chicago
  • FWB

De Dormale, G. M., & Quisquater, J.-J. (2006). Iterative modular division over GF(2/sup m/): novel algorithm and implementations on FPGA. Reconfigurable Computing: Architectures and Applications. SecondInternational Workshop, ARC 2006. Revised Selected Papers. (LectureNotes in Computer Science Vol. 3985), p. 370-382. https://hdl.handle.net/2078.5/219558