X-IMM: Mixed-Signal Iterative Montgomery Modular Multiplication

In this paper, we present a mixed-signal implementation of iterative Montgomery multiplication algorithm (called X-IMM) for using in large arithmetic word size (LAWS) computations. LAWS is mainly utilized in security applications such as lattice-based cryptography, where the width of the input operands may be equal to or larger than 1,024 bits. The proposed architecture is based on the iterative implementation of the Montgomery multiplication (MM) algorithm, where some critical parts of the multiplication are computed in the analog domain by mapping them on the memristor crossbar. Using a memristor crossbar reduces the area usage and latency of the modular multiplication unit compared to its fully digital implementation. The devised mixed-signal MM implementation is scalable by cascading the smaller X-IMMs to support dynamically adjustable larger operand sizes at runtime. The effectiveness of the proposed MM structure is assessed in the 45nm technology and the comparative studies show that the proposed 1,024-bit Radix-4 (Radix-16) Montgomery multiplication architecture provides about 13% (22%) higher GOPS/mm2 compared to the state-of-the-art digital ASIC implementations of the iterative MM. Also, owing to analog computing, the proposed structure reduces energy consumption considerably as well.