臺灣博碩士論文加值系統

本論文基於修改的蒙哥馬利演算法，我們設計出兩個位元階層的心脈式RSA密碼系統核心，而為了降低測試成本，我們引入了C-testable ILA的設計方法至原本的心脈式RSA加解密系統核心中，設計出兩個具可測試性設計的RSA加解密系統核心；平均而言，使用我們提出的具可測試性設計RSA加解密系統核心，進行一筆512位元的RSA運算僅需0.53M個時脈週期。而藉由管線化的設計，其工作頻率可到達233M Hz；經過我們C-testable的設計後區塊插入RSA密碼系統核心和位元插入RSA密碼系統核心各僅需48及130個測試訊號。

Based on the modified Montgomery’s algorithm, we design two bit-level systolic RSA cryptosystem cores. In order to reduce the testing cost, we introduce the C-testable methodology to the original systolic RSA cryptosystem cores and obtain two testable RSA cryptosystem cores. The testable RSA cryptosystem cores take 0.53M clock cycles to finish a 512-bit RSA operation in average and the clock rate is about 233MHz in pipeline. With the C-testable methodology, it only needs 130 and 48 test patterns to test the testable bit-interleaved and block-interleaved RSA cryptosystem cores respectively.

封面内頁
簽名頁
授權書．．．．．．．．．．．．．．．．．．．．．．．．．iii
中文摘要．．．．．．．．．．．．．．．．．．．．．．．．iv
英文摘要．．．．．．．．．．．．．．．．．．．．．．．．v
誌謝．．．．．．．．．．．．．．．．．．．．．．．．．．vi
目錄．．．．．．．．．．．．．．．．．．．．．．．．．．vii
圖目錄．．．．．．．．．．．．．．．．．．．．．．．．．x
表目錄．．．．．．．．．．．．．．．．．．．．．．．．．xiii

第一章　緒論 ．．．．．．．．．．．．．．．．．．．．．．1
第二章　近代密碼系統．．．．．．．．．．．．．．． ．．．4
2.1密碼系統．．．．．．．．．．．．．．．．．．．4
2.2秘密金鑰密碼系統．．．．．．．．．．．．．．．6
2.3公開金鑰密碼系統．．．．．．．．．．．．．．．8
2.4 RSA公鑰密碼系統．．．．．．．．．．．．．．10
2.4.1 RSA加密/解密的方法 ．．．．．．．．．．10
2.4.2 RSA數學模式分析．．．．．．．．．．．．12
2.4.3 RSA的安全性．．．．．．．．．．．．．．14
第三章　演算法．．．．．．．．．．．．．．．．．．．．．17
3.1以二為基底之模乘法演算法 ．．．．．．．．．．17
3.1.1蒙哥馬利演算法．．．．．．．．．．．．．17
3.1.2 改良的蒙哥馬利演算法 ．．．．．．．．．19
3.2 以二為基底之模指數演算法．．．．．．．．．．21
第四章　VLSI設計及測試理論 ．．．．．．．．．．．．．．23
4.1 心脈式陣列．．．．．．．．．．．．．．．．．23
4.2 連續性邏輯陣列．．．．．．．．．．．．．．．26
4.3 C-testable可測試性設計．．．．．．．．．．．．28
4.3.1 C-testable之原理．．．．．．．．．．．．．．．29
4.3.2建立C-testable ILA 之方法．．．．．．．．．．30
4.3.2.1 C-testable unilateral ILA 設計法 ．．．30
4.3.2.2 C-testable bilateral ILA 設計法．．．．30
第五章　硬體設計及實作．．．．．．．．．．．．．．．．．32
5.1 具可測試性設計之心脈式陣列RSA密碼系統 ．．32
5.1.1位元插入 RSA密碼系統．．．．．．．．．32
5.1.1.1 串並模乘法器 ．．．．．．．．．．32
5.1.1.2 位元插入RSA密碼系統．．．．．．44
5.1.1.2.1 in1控制電路．．．．．．．46
5.1.1.2.2 b控制電路．．．．．．．．47
5.1.1.2.3 SIPO控制電路．．．．．．49
5.1.1.2.4 n控制電路．．．．．．．．50
5.1.1.2.5 feedback控制電路．．．．．51
5.1.1.2.6 fao控制電路．．．．．．．53
5.1.2區塊插入RSA密碼系統 ．．．．．．．．．53
5.1.2.1 位元循序模乘法器．．．．．54
5.1.2.2 區塊插入RSA密碼系統 ．．66
5.2 晶片實作．．．．．．．．．．．．．．．．．．69
第六章　結論與討論．．．．．．．．．．．．．．．．．．．73

[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] 曾希哲, “RSA加解密晶片之設計與分析,” 國立海洋大學, 碩士論文, 1999.
[15] 吳哲漢, “RSA密碼系統之演算法研究與快速硬體實現,” 雲林科技大學, 碩士論文, 1999.
[16] 李政德, “以Montgomery演算法為基礎之RSA密碼系統硬體實作,” 逢甲大學碩士論文, 2001.
[17] 楊吳泉, 現代密碼學入門與程式設計, 全華科技圖書股份有限公司, 1996.
[18] 賴溪松、韓亮、張真誠, 近代密碼學及其應用, 松崗電腦圖書資料股份有限公司, 1995.
[19] 曾志光、巫坤品 譯, William Stallings 著, 密碼學與網路安全原理與實務(第二版), 碁峰資訊股份有限公司, 2001.
[20] 劉尊全, 數為時代密碼技術的現狀與未來, 松崗電腦圖書資料股份有限公司, 2001.
[21] 曾志光、鄭光廷 譯, “Patterson Hennessy 著 計算機組織與設計”, 第二版 pp. 4-57~4-61, 碁峰資訊股份有限公司, 2002.
[22] P. Ribenboim, “The New book of Prime Number Records,“ New York: Springer-Verlag, 1996.
[23] B. Kaliski, and M. Robshaw, “The Secure Use of RSA,” CryptoBytes, Autumn 1995.
[24] Michael J. Wiener, “Cryptanalysis of Short RSA Secret Exponents.” IEEE Transactions on Information Theory, vol. 36, 1990.
[25] P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other System.” Proceedings, Crypto ’96, August 1996; published by Springer-Verlag.
[26] 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.
[27] 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.
[28] 劉奇昌, “高效能RSA密碼系統之硬體設計,” 國立中正大學, 碩士論文, 2000.
[29] 劉俊麟, “以四為基底之高速RSA加解密系統晶片,”大葉大學,碩士論文,2003.
[30] 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.
[31] S. Y. Kung, “VLSI Array Processors, Englewood Cliffs,” New Jersey: Prentice-Hall Inc., 1988.
[32] 蔡秉諺, “以四為基底之心脈式RSA加解密系統晶片,”大葉大學,碩士論文,2004.
[33] Keshab K. Parhi, “VLSI Digital Signal Processing Systems,” John Wiley & Sons, INC. 1999 Chap. 7 pp. 189-192
[34] Cheng-Wen Wu, Peter R. Cappello, “Easily Testable Iterative Logic Arrays,” IEEE Transactions on Computers, vol. 39, no. 5, pp.640-652, May 1990.
[35] Sandeep Bhatia, Alexander Albicki, “Testing of Iterative Logic Arrays,” IEEE Transactions on Circuits and Systems, vol. 1, pp.243-246, August 1990.
[36] Tsu-Wei Ku, Mani Soma, “Minimal Overhead Modification of Iterative Logic Arrays for C-testability,” IEEE International Test Conference, pp.964-968, 1990.
[37] 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.