Dual-field Modular Multiplication Algorithm and Modular Inversion Algorithm with VLSI Implementation
双有限域模乘和模逆算法及其硬件实现

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.