Multifunction Residue Architectures for Cryptography

A design methodology for incorporating Residue Number System (RNS) and Polynomial Residue Number System (PRNS) in Montgomery modular multiplication in GF(p) or GF(2n) respectively, as well as VLSI architecture of a dual-field residue arithmetic Montgomery multiplier is presented in this paper. An analysis of input/output conversions to/from residue representation, along with the proposed residue Montgomery multiplication algorithm, reveals common multiply-accumulate data paths both between the converters and between the two residue representations. A versatile architecture is derived that supports all operations of Montgomery multiplication in and, input/output conversions, Mixed Radix Conversion (MRC) for integers and polynomials, dual-field modular exponentiation and inversion in the same hardware.