Efficient Implementation of a Generic Coprocessor for Elliptic Curve Cryptography on Reconfigurable Hardware
This project is motivated by the need for a flexible and secure ECC implementation on FPGAs at Rohde Schwarz SIT GmbH. The coprocessor shall handle elliptic curves over Fp, p 3, prime with a verifiable pseudo random prime structure, so not only NIST curves should be possible. Different bit lengths of p must be supported. One main task is the use of DSPs for fast arithmetic computations as much as possible to save other resources on the FPGA. Particularly, the modular multiplication was examined more detailed. It is solved with the CIOS algorithm, a Montgomery multiplication algorithm design especially for hardware. The hardware design of the CIOS algorithm implemented in Mentens' PhD thesis was the basis for our design. For secure and efficient implementation of ECC scalar multiplication a special parallelized Montgomery ladder is used which uses projective coordinates in (X Z) representation. The coprocessor must be protected/protectable against all kinds of Side Channel Analysis. Montgomery ladder is used against SPA. Randomized projetive coordinates and prime randomization were supported as a countermeasure against DPA. We implemented the basic design of Mentens and modified it in various ways: First, the 16x16 multiplier has been replaced by a 17x17 multiplier. Then the full capabilities of multipliers on modern FPGAs has been used, i. e. a 17x24 multiplier. The design and implementation produced with various optimizations regarding the number of DSPs used and the number of pipeline stages. The coprocessor designed provides the improved Montgomery multiplication by Walter, modular addition/subtraction as well as modular inversion. The designed coprocessor is faster than Mentens' which is the most comparable design. Comparison with other implementations are not easy because of missing either countermeasures against SCA, implementations for curves over F2m, or approaches that do not allow flexible p.