HTMMM: Novel Hybrid Truncated Montgomery Modular Multiplication Algorithm and Hardware Architecture

Modular multiplication is one of the key operations in modern public-key cryptography. Montgomery Modular Multiplication (MMM) is a mainstream method to avoid modulo operations, which contains one variable multiplication and two constant multiplications. In this paper, for high performance, a novel Hybrid Truncated Montgomery Modular Multiplication (HTMMM) algorithm and its hardware architecture are proposed, which achieves state-of-the-art Area-Time-Product (ATP) and throughput. We propose an error-free high-part truncated multiplication for the first time, which solves the problem that conventional methods cannot be applied to MMM due to the introduced error, and reduces the complexity to the same level as low-part truncated multiplication. Besides, a hybrid multiplication based on Toom-Cook and Karatsuba is proposed to optimize variable multiplication, Non-Adjacent Form (NAF) encoding is adopted with truncated multiplication to optimize constant multiplications. The quantitative analysis of complexity for the integer multipliers with different schemes are illustrated to find the optimal multiplier under various cases. Based on these, we took the bit width N = 1024 as an example to introduce the hardware architecture in detail and gave the implementation results of N = 256 and N = 1024 in different processes. The experimental results demonstrate that compared with the best existing design, the throughput and ATP of our proposed design are improved by 1.25× and 2.22×, respectively.