Montgomery modular multiplication and exponentiation in the residue number system
W.L. Freking, Keshab K. Parhi · 2003
Modular exponentiation and its constituent operation, modular multiplication, are fundamental to numerous public-key cryptography schemes including RSA. Efficient hardware implementations via ASIC or coprocessor approaches are essential to high-performance and low-power applications. New techniques are developed to aid in the design of both sequential and parallel implementations in the residue number system (RNS). A new sequential modular multiplication method suitable for smart cards is proposed which achieves the best known operation count for an all-modular-arithmetic approach. Furthermore, a new technique is introduced to address the Montgomery (1985) scale factor in fully-parallel RNS implementations.