臺灣博碩士論文加值系統

隨著攜帶式電子產品的普及化，晶片的面積以及功率消耗勢必要降低，因此我們提出了一個以32位元核心實現的可變式RSA加解密系統晶片。我們的設計在保密性以及計算時間上面提出了取捨的方法。如果覺得保密性重要的話，我們就採用較長的金鑰來做加解密以取得較高的保密性；如果保密性比較不重要，我們可以採用較短的金鑰來做加解密以降低運算時間。
本論文的晶片是使用Cadence、Synopsys以及TSMC 0.35um元件庫來做模擬以及實現。平均而言我們設計的RSA核心完成一筆512位元的運算需要2.55M個時脈週期，關鍵路徑的延遲為3.2 ns，晶片面積為1.81mm x 1.81mm。由於我們使用32位元核心，我們的晶片有更小的面積。

With the popularity of the portable electronic devices, the chip area and power consumption must be reduced, and because of this, we propose a scalable RSA cryptosystem chip, which is implemented with a 32-bit core. Our design provides the trade-off between security and computation time. If the security is more important, we can choose longer key to get higher security. Otherwise, the shorter key could be chosen to reduce the computation time.
To realize the chip of this design, we used Cadence, Synopsys and TSMC 0.35um cell library to simulate and implement. The RSA core takes 2.55M clocks to finish a 512-bit modular exponentiation in average and the critical path delay is only 3.2 ns. The chip area is 1.81mm x 1.81mm. Since a 32-bit core is adopted, our chip has smaller area.

ABSTRACT ( In Chinese )………………………………………………………………I
ABSTRACT ( In English )………………………………………………………………II
ACKNOWLEDGMENTS…………………………………………………………………………III
CONTENTS……………………………………………………………………………………IV
LIST OF FIGURES…………………………………………………………………………VI
LIST OF TABLES……………………………………………………………………………VIII

Chapter 1 Introduction……………………………………………………………………1
1.1 Introduction……………………………………………………………………………1
1.2 Organization……………………………………………………………………………2

Chapter 2 RSA Cryptosystem………………………………………………………………3
2.1 Cryptography……………………………………………………………………………3
2.2 Secret key cryptosystem……………………………………………………………4
2.3 Public key cryptosystem……………………………………………………………5
2.4 RSA Cryptosystem………………………………………………………………………6
2.4.1 Number Theory………………………………………………………………………8
2.4.2 Encryption and Decryption Method………………………………………………9
2.4.3 The Key Generation…………………………………………………………………9
2.4.4 The Security of RSA………………………………………………………………10

Chapter 3 Algorithm……………………………………………………………………………………13
3.1 Montgomery’s Algorithm……………………………………………………………13
3.2 Yang’s Modified Montgomery’s Algorithm………………………………………16
3.3 Modified Modular Exponentiation Algorithm……………………………………16
3.4 Modular Exponentiation Algorithm…………………………………………………19

Chapter 4 Hardware Design and Implementation………………………………………21
4.1 Systolic Array…………………………………………………………………………21
4.2 C-testable Methodology………………………………………………………………23
4.3 Scalable Block-Interleaved RSA Cryptosystem…………………………………24
4.3.1 Bit-Sequential Modular Multiplier……………………………………………25
4.3.2 Scalable Bit-Sequential Modular Multiplier…………………………………33
4.3.3 Block-Interleaved RSA Cryptosystem……………………………………………38
4.4 Chip Implementation…………………………………………………………………39
4.5 Simulation Result……………………………………………………………………41
Chapter 5 Conclusion………………………………………………………………………44
Reference……………………………………………………………………………………46

[1] Whitfield Diffie and Martin E. Hellman, “New Direction in Cryptography,” IEEE Transaction on Information Theory, vol. IT-22, no. 6, pp. 644-654, 1976.
[2] R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, vol. 21, pp. 120-130, February 1978.
[3] Brickell, “A First Modular Multiplication Algorithm with Application to Two Key Cryptography,” in Advance in Cryptology (Proceeding of CRYPTO ’82), pp. 51-60, Academic Press, 1983.
[4] P. L. Montgomery, “Modular multiplication without trial division,” Math. Computation, vol. 44, pp. 519-521, 1985.
[5] Koc and C. Y. Hung, “Bit-level Systolic Array for Modular Multiplication,” Journal of VLSI Signal Processing, vol. 3, pp. 215-223, 1991.
[6] Stephen E. Eldridge and C. D. Walter, “Hardware Implementation of Montgomery’s Modular Multiplication Algorithm,” IEEE Transaction on Computers, vol. 42, no. 6, pp. 693-699, June 1993.
[7] Colin D. Walter, “Systolic Modular Multiplication,” IEEE Trans. Computers, vol. 42, no. 3, March 1993.
[8] Po-Song Chen, Shih-Arn Hwang, and Cheng-Wen Wu, “A Systolic RSA Public Key Cryptosystem,” in Proc. IEEE Int. Symp. Circuits and Systems (ISCAS), vol. 4, (Atlanta), pp. 408-411, May 1996.
[9] Jin-Hua Hong and Chen-Wen Wu, “Radix-4 Modular Multiplication and Exponentiation Algorithms for the RSA Public-Key Cryptosystem,” in Proc. Asia and South Pacific Design Automation Conf. (ASP-DAC), (Yokohama), pp. 565 -570, 2000.
[10] Jin-Hua Hong and Chen-Wen Wu, “RSA public key crypto-processor core design and hierarchical system test using IEEE 1149 family,” PhD Thesis, National Tsing-Hua University, Taiwan, June 2000.
[11] Ching-Chao. Yang, Tian-Sheuan Chang, and Chein-Wei Jen, “A New RSA Cryptosystem Hardware Design Based on Montgomery’s Algorithm,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 45, no. 7, pp. 908-913, July 1998.
[12] Fang Yingli, Gao Zhiqiang, “A New RSA Cryptosystem Hardware Implementation Based on High-Radix Montgomery’s Algorithm,” 4th International ASIC conf., pp. 348 -351, 2001.
[13] Y.-H. Hsieh, “Design and Implementation of an RSA Encryption /Decryption Processor on IC Smart Card,” Master’s Thesis, National Taiwan University, Taiwan, June 1999.
[14] Ming-Cheng Sun; Chih-Pin Su; Chih-Tsun Huang; Cheng-Wen Wu, ” Design of a scalable RSA and ECC crypto-processor,” Design Automation Conference, 2003. Proceedings of the ASP-DAC 2003. Asia and South Pacific 21-24 Jan. 2003
[15] Jin-Hua Hong, Bin-Yan Tsai, Liang-Te Lu, Shao-Hui Shieh, “A novel radix-4 bit-level modular multiplier for fast RSA cryptosystem,” Circuits and Systems, 2004. (ISCAS) '04. Proceedings of the 2004 International Symposium on Volume 2, 23-26 May 2004
[16] Chih-Pin Su, Chen-Hsing Wang; Kuo-Liang Cheng; Chih-Tsun Huang; Cheng-Wen Wu,＂Design and test of a scalable security processor,＂Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific　Volume 1, 18-21 Jan. 2005
[17] P. Ribenboim, “The New book of Prime Number Records,“ New York: Springer-Verlag, 1996.
[18] B. Kaliski, and M. Robshaw, “The Secure Use of RSA,” CryptoBytes, Autumn 1995.
[19] Michael J. Wiener, “Cryptanalysis of Short RSA Secret Exponents.” IEEE Transactions on Information Theory, vol. 36, 1990.
[20] P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other System.” Proceedings, Crypto ’96, August 1996; published by Springer-Verlag.
[21] Jye-Jong Leu, and An-Yeu Wu, “Design Methodology for Booth-Encoded Montgomery Module Design for RSA Cryptosystem,” in Proc. IEEE International Symposium on Circuit and Systems, vol. 5, pp. 357-360, 2000.
[22] Jin-Hua. Hong, and Chen-Wen Wu, “Cellular-Array Modular Multiplier for Fast RSA Public-Key Crypto-system Based on Modified Booth’s Algorithm,” IEEE Transactions on VLSI Systems, vol. 11, no. 3, pp. 474-484, June 2003.
[23] Chih-Yuang Su, Shih-Arn Hwang, Po-Song Chen, and Cheng-Wen Wu, “An Improved Montgomery’s Algorithm for High-Speed RSA Public-Key Cryptosystem,” IEEE Transactions on VLSI Systems, vol. 7, no. 2, pp. 280-284, June 1999.
[24] S. Y. Kung, “VLSI Array Processors, Englewood Cliffs,” New Jersey: Prentice-Hall Inc., 1988.
[25] Keshab K. Parhi, “VLSI Digital Signal Processing Systems,” John Wiley & Sons, INC. 1999 Chap. 7 pp. 189-192
[26] Cheng-Wen Wu, Peter R. Cappello, “Easily Testable Iterative Logic Arrays,” IEEE Transactions on Computers, vol. 39, no. 5, pp.640-652, May 1990.
[27] Sandeep Bhatia, Alexander Albicki, “Testing of Iterative Logic Arrays,” IEEE Transactions on Circuits and Systems, vol. 1, pp.243-246, August 1990.
[28] Tsu-Wei Ku, Mani Soma, “Minimal Overhead Modification of Iterative Logic Arrays for C-testability,” IEEE International Test Conference, pp.964-968, 1990.
[29] Shyue-Kung Lu, Jen-Chuan Wang, Cheng-Wen Wu, “C-Testable Design Techniques for Iterative Logic Arrays,” IEEE Transactions on VLSI Systems, vol. 3, no. 1, pp.146-152, March 1995.