Efficient architectures for implementing montgomery modular multiplication and RSA modular exponentiation on reconfigurable logic

ABSTRACT

This paper presents a review of some existing architectures for the implementation of Montgomery modular multiplication and exponentiation on FPGA (Field Programmable Gate Array). Some new architectures are presented, including a pipelined architecture exploiting the maximum carry chain length of the FPGA which is used to implement the modular exponentiation operation required for RSA encryption and decryption. Speed and area comparisons are performed on the optimised designs. The issues of targeting a design specifically for a reconfigurable device are considered, taking into account the underlying architecture imposed by the target technology.

REFERENCES

• 1: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 2: P. L. Montgomery. "Modular multiplication without trial division". Math. Computation, 44:519-521, 1985.
• 3: Yong-Jin Jeong , Wayne P. Burleson, VLSI array algorithms and architectures for RSA modular multiplication, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.2, p.211-217, June 1997 [doi>10.1109/92.585224]
• 4: P. Kornerup, A Systolic, Linear-Array Multiplier for a Class of Right-Shift Algorithms, IEEE Transactions on Computers, v.43 n.8, p.892-898, August 1994 [doi>10.1109/12.295851]
• 5: C. D. Walter, Systolic Modular Multiplication, IEEE Transactions on Computers, v.42 n.3, p.376-378, March 1993 [doi>10.1109/12.210181]
• 6: Stephen E. Eldridge , Colin D. Walter, Hardware Implementation of Montgomery's Modular Multiplication Algorithm, IEEE Transactions on Computers, v.42 n.6, p.693-699, June 1993 [doi>10.1109/12.277287]
• 7: C. D. Walter. "Still faster modular multiplication". Electronics Letters, 31:263-264, Feb 1995.
• 8: W. P. Marnane. "Optimised bit serial modular multiplier for implementation on field programmable gate arrays". IEE Electronics Letters, 34(8):738-739, April 1998.
• 9: Taek-Won Kwon, Chang-Seok You, Won-Seok Heo, Yong-Kyu Kang, and Jun-Rim Choi. "Two implementation methods of a 1024-bit RSA cryptoprocessor based on modified montgomery algorithm". IEEE Int. Symp. on Circuits and Systems (ISCAS), pages 650-653, May 2001.
• 10: Thomas Blum, Montgomery Modular Exponentiation on Reconfigurable Hardware, Proceedings of the 14th IEEE Symposium on Computer Arithmetic, p.70, April 14-16, 1999
• 11: Young Sae Kim, Woo Seok Kang, and Jun Rim Choi. Implementation of 1024-Bit Modular Processor for RSA Cryptosystem. The 2nd IEEE Asia Pacific Conference on ASICs, Aug 2000.
• 12: Ching-Chao Yang, Tian-Sheuan Chang, and Chein-Wei Jen. "A new RSA cryptosystem hardware design based on Montgomery's Algorithm". IEEE Trans. Circuits and Systems - II: Analog and Digital Signal Processing, 45(7):908-913, July 1998.
• 13: Jyh-Huei Guo, Chin-Liang Wang, and Hung-Chih Hu. Design and Implementation of an RSA Public-Key Cryptosystem. Proc. IEEE International Symposium on Circuits and Systems, 1:504-507, 1999.
• 14: Xilinx Inc. Website. http://www.xilinx.com.

INDEX TERMS

Keywords:
FPGA, RSA, encryption, exponentiation, modular multiplication, montgomery, public key