Bipartite modular multiplication with twice the bit-length of multipliers

摘要

This paper presents a new technique to compute 2f-bit bipartite multiplications with l-bit bipartite multipli_cation units. Low-end devices such as smartcards are usually equipped with crypto-coprocessors for accelerating the heavy computation of modular multiplications; however, security standards such as NIST and EMV have declared extending the bit length of RSA cryptosystem to resist mathematical attacks, making the multiplier quickly outdated. Therefore, the double-size techniques have been studied this decade to extend the life expectancy of such multipliers. This paper pro_poses new double-size techniques based on the multipliers implementing either classical or Montgomery modular mul_tiplications, or even both simultaneously (bipartite modular multiplication), in which case one can potentially compute modular multiplications twice faster. Furthermore, in order to get a more realistic estimation than the other works, this paper considers not only the cost of the multiplication, but also the cost of the other arithmetic instructions. In our estimation, the proposal provides comparable results for classical mul_tiplier and Montgomery multiplier, and is the only available method for the bipartite multiplier.