Hardware architecture for RSA cryptography based on residue number system

Abstract

A parallel architecture for efficient hardware implementation of Rivest Shamir Adleman (RSA) cryptography 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 transformation is used to achieve RNS Montgomery modular multiplication algorithm, which facilitates hardware implementation. Based on transport triggered architecture (TTA), the proposed architecture is designed to evaluate the performance 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

References

[1] Montgomery P. L. Modular multiplication without trial division[J]. Mathematics of Computation, 1985, 44(170): 519 521

[2] Wang D., Bai G. Chen Hongyi. Hardware architecture for the Montgomery multiplication algorithm[J]. Microelectronics and Computer, 2010, 27(5): 1-4.

[3] Hong J., Wu Chengwen. Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified Booth’s algorithm[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2003, 11(3): 474-484.

[4] Nozaki Hanae, Motoyama Masahiko, Shimbo Atsushi et al. Implementation of RSA algorithm based on RNS Montgomery multiplication [C]. In: Cryptographic Hardware and Embedded Systems (CHES). Berlin, Germany, 2001. 364–376.

[5] Kawamura Shinichi, Koike Masanobu, Sano Fumihiko et al. Cox-rower architecture for fast parallel Montgomery multiplication[C]. In: Advances in Cryptology-EUROCRYPT 2000. Bruges, Belgium, 2000. 523–538.

[6] Bajard J.-C., Imbert Laurent. A full RNS implementation of RSA [J]. IEEE Transactions on Computers, 2004, 53(6): 769-774.

[7] Qin B., Li M., Kong Fanyu. Cryptanalysis of a type of CRT-based RSA algorithms [J]. Journal of Computer Science and Technology, 2008, 23(2): 214 221

[8] Cheng W., Gu D., Guo Z., et al. A power analysis attack against RSA-CRT [J]. Communications Technology, 2011, 44(234): 123-128.

[9] Hämäläinen P, Hännikäinen M, Hämäläinen T et al. Implementation of encryption algorithms on transport triggered architectures [C]. In: The 2001 IEEE International Symposium on Circuits and Systems. Sydney, Australia, 2001. 726–729.

[10] Hu Jingwei, Guo Wei, Wei Jizeng et al. A novel architecture for fast RSA key generation based on RNS [C]. In: Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP). Tianjin, China, 2011. 345–349.

[11] Bajard Jean-Claude, Meloni Nicolas, Plantard Thomas. Efficient RNS bases for cryptography [C]. In: World Congress: Scientific Computation Applied Mathematics and Simulation. Paris, France, 2005. 11–15.

[12] Barrett Paul. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor [C]. In: Advances in Cryptology — CRYPTO’ 86. Berlin, Germany, 1987. 311–323.

[13] Liu Qiang, Ma Fangzhen, Tong Dong et al. A regular parallel RSA processor [C]. In: 47th IEEE International Midwest Symposium on Circuits and Systems. Hiroshima, Japan, 2004. 467–470.

[14] Shieh M., Chen J., Wu H., et al. A new modular exponentiation architecture for efficient design of RSA cryptosystem [J]. IEEE Transactions on Very Large Scale Integration(VLSI)Systems, 2008, 16(9): 1151-1161.

[15] Shieh M., Chen J., Lin W., et al. A new algorithm for high-speed modular multiplication design [J]. IEEE Transactions on Circuits and Systems-I, 2009, 56(9): 2009 2019

[16] Shieh M., Lin Wenching. Word-based Montgomery modular multiplication algorithm for low-latency scalable architectures [J]. IEEE Transactions on Computers, 2010, 59(8): 1145 1151

[17] Huang M., Gaj K., EI-Ghazawi Tarek. New hardware architectures for Montgomery modular multiplication algorithm [J]. IEEE Transactions on Computers, 2011, 60(7): 923-936.