Scalable hardware implementing high-radix Montgomery multiplication algorithm

摘要

This paper presents a new scalable hardware implementing modular multiplication. A high radix Montgomery multiplication algorithm without final subtraction is used to perform this operation. An alternative proof for the final Montgomery multiplication by 1, removing the condition on the modulus, is given. This hardware fits in any chip area and is able to work with any size of modulus. Unlike other scalable designs only one cell is used. This cell contains standard and well optimized digit multiplier and adder. Time-area trade-offs are also available before hardware synthesis for differents sizes of internal data path. The pipeline architecture of the multiplier component increases the clock frequency and the throughput. Time-area trade-offs are analyzed in order to make the best choice for given time and area constraints. This architecture seems to provide a better time-area compromise than previous scalable hardware. (c) 2006 Elsevier B.V. All rights reserved.