Title :
Montgomery modular multiplication and exponentiation in the residue number system
Author :
Freking, William L. ; Parhi, Keshab K.
Author_Institution :
Dept. of Electr. & Comput. Eng., Minnesota Univ., Minneapolis, MN, USA
Abstract :
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.
Keywords :
application specific integrated circuits; coprocessors; multiplying circuits; parallel algorithms; public key cryptography; residue number systems; sequential circuits; smart cards; ASIC; Montgomery modular exponentiation; Montgomery modular multiplication; Montgomery scale factor; RSA; all-modular algorithm; all-modular-arithmetic; coprocessor; efficient hardware implementations; fully-parallel RNS implementations; high-performance; low-power applications; operation count; public-key cryptography; residue number system; sequential implementation; sequential modular multiplication method; smart cards; Algorithm design and analysis; Application specific integrated circuits; Arithmetic; Computational complexity; Computer architecture; Coprocessors; Hardware; Public key cryptography; Smart cards;
Conference_Titel :
Signals, Systems, and Computers, 1999. Conference Record of the Thirty-Third Asilomar Conference on
Conference_Location :
Pacific Grove, CA, USA
Print_ISBN :
0-7803-5700-0
DOI :
10.1109/ACSSC.1999.831919
