Dual-field Modular Multiplication Algorithm and Modular Inversion Algorithm with VLSI Implementation
Chen Guang-hua① Zhu Jing-ming① Liu Ming② Zeng Wei-min①
①(Research and Development Center, Shanghai University, Shanghai 200072, China) ②(Shanghai Key Laboratory of Power Station Automation Technology, Shanghai University, Shanghai 200072, China)
Abstract:Modular multiplication and modular inversion algorithms are the kernel of elliptic curve cryptography. In this paper, a radix-4 dual-filed modular multiplication algorithm which is based on Blakely’s algorithm is proposed. Booth’s algorithm is used to halve the iteration number of the Blakely’s algorithm, and the sign estimation is employed to simplify the modular reduction operation. A dual-field modular inversion algorithm which is derived from extended Euclidean algorithm is presented to avoid magnitude comparison and shift efficiently. Furthermore, a unified hardware structure which can support dual-field modular multiplication and modular inversion operation is designed, and the result of the hardware implementation shows that the circuit can run 68% faster for modular multiplication and 17.4% faster for modular inversion without area increasing than others.