Hardware Architecture for RSA Cryptography Based on Residue Number System*

Abstract：A parallel architecture for efficient hardware implementation of Rivest Shamir Adleman (RSA) cryptog-raphy is proposed. Residue number system (RNS) is introduced to realize high parallelism, thus all the elements under the same base are independent of each other and can be computed in parallel. Moreover, a simple and fast base trans-formation is used to achieve RNS Montgomery modular multiplication algorithm, which facilitates hardware imple-mentation. Based on transport triggered architecture (TTA), the proposed architecture is designed to evaluate the per-formance and feasibility of the algorithm. With these optimizations, a decryption rate of 106 kbps can be achieved for 1 024-b RSA at the frequency of 100 MHz. Keywords：residue number system; RSA cryptography; Montgomery algorithm; computer architecture; parallel algorithm Rivest Shamir Adleman (RSA) has become the most widely used public key algorithm due to its accessi-bility and security. A pioneering work for modular multi-plication was attributed to Montgomery[1]. In Ref. [2], an architecture based on the systolic array for implementing multiple-word radix-2 Montgomery modular multiplica