New word-based montgomery algorithm for higher radices

Montgomery algorithm is widely used in public-key cryptosystems. In this paper a new word-based Montgomery algorithm suitable for higher radices has been presented and a new modular multiplication block based on it has been designed. The latency between neighboring processing elements can be reduced to one clock period by deferring the calculation of several bits of each word to the next processing element. The radix 2, 4 and 8 modular multiplication block has been implemented with SMIC 0.13um technology and Xilinx Virtex II series FPGA. The proposed design with radix 2 and 4 achieves area reduction with almost the same performance in speed, compared to other designs of the same radix. And the radix-8 block gains at least 10% time reduction in completing a 1024-bit Montgomery multiplication.