適用於RSA公匙密碼系統之高效能Montgomery模組

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：36

、訪客IP：3.149.230.44

姓名

呂誌忠(Chih-Chung Lu) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

適用於RSA公匙密碼系統之高效能Montgomery模組
(Design Methodology of Booth-encoded Montgomery Module Design for RSA Cryptosystem)

相關論文

★ 適用於通訊系統之李德所羅門軟性智慧財產模組自動產生器	★ 適用於非對稱數位用戶迴路系統之有效率的時域等化器演算法
★ 以改良式向量旋轉器為核心的遞迴式傅立葉模組設計	★ 第二代高速數位用戶迴路中維特比解碼器之FPGA實現
★ 一個高速╱低複雜度旋轉方法的統一設計架構：角度量化的觀點

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(英)

In this thesis, a design methodology for Booth-encoded Montgomery’’s modular multiplication algorithms is proposed. The new design methodology helps us to re-duce the required iteration number in the Encryption/Decryption of RSA cryptosys-tem. With application of pipelining and folding/unfolding techniques to the design of Montgomery’’s modular multiplication module, we construct the processing element (PE) called M-cell. With the M-cell’’s, we can easily reconfigure the RSA chip. It is very convenient to reconfigure the RSA chip for different specification by cascade different number of M-cells and reuse them. The final optimized Montgomery’’s modular multiplication module is a digit-serial, pure-systolic, and scalable architec-ture with 100% utilization of all PE modules. The simulation result shows that we can not only reduce the required iteration number from 2n^2 to n^2 using H algorithm, hard-ware complexity is also simplified. The efficiency (time-area product) of our design is improved about a factor of 2.5. The simulation results show that the maximum speed-performance of single RSA chip can be up to 476kbit/sec.

關鍵字(中)

★ 密碼

關鍵字(英)

★ cryptography
★ cryptosystem
★ RSA
★ Montgomery
★ modular multiplication
★ modular exponentail

論文目次

1. INTRODUCTION1
1.2 INTRODUCTION OF RSA CRYPTOGRAPHY2
1.3 IMPLEMENTATION ISSUE OF RSA CRYPTOGRAPHY4
1.4 PROPOSED DESIGN APPROACHES4
1.5 THESIS ORGANIZATION5
2. COMPARISON OF MODULAR EXPONENTIAL ALGORITHMS6
2.1 EXPONENTIAL ALGORITHM7
2.2 COMPARISON OF EXPONENTIAL ALGORITHMS12
3. BOOTH-ENCODED MONTGOMERY'S MODULAR MULTIPLICATION ALGORITHMS14
3.1 REVIEW OF MONTGOMERY'S MODULAR MULTIPLICATION ALGORITHM14
3.2 PROPOSED DESIGN METHODOLOGY16
3.3 COMPARISON OF MONTGOMERY'S MODULAR MULTIPLICATION ALGORITHMS20
3.4 MODIFIED MODULAR EXPONENTIAL ALGORITHM21
4. ARCHITECTURAL DESIGN OF MONTGOMERY MODULE23
4.1 APPLY OPTIMIZATION TECHNIQUE FOR MONTGOMERY MODULE23
4.2 FULLY PIPELINED DIGIT-SERIAL ARCHITECTURE26
4.3 IMPROVED MODULE UTILIZATION30
4.4 DESIGN OF CONTROL UNIT30
4.5 RSA PROCESSOR DESIGN33
5. COMPARISON AND SIMULATION RESULT38
5.1 COMPARISON OF EFFICIENCY FOR MONTGOMERY'S MODULAR MULTIPLICATION ALGORITHMS38
5.2 COMPARISON OF HARDWARE ARCHITECTURE40
5.3 SIMULATION RESULT41
5.3.1 GENERATE RSA KEY FOR TESTING PROPOSE41
5.3.2 VERIFICATION OF OUR ARCHITECTURE42
5.3.3 OTHER TESTING CASES44
6. CONCLUSIONS47
REFERENCES48

參考文獻

[1] S.C. Pohlig and M.E. Hellamn, "An Improved Algorithm for Computing Loga-rithms if GF(p) and Its Cryptographic Significance," IEEE Transactions on Infor-mation Theory, v. 24, n. 1, pp.106-111, Jan 1978.
[2] R.L. Rivest, A. Shamir, and L.M. Adleman, "A Method for Obtaining Digital Sig-natures and Public-Key Cryptosystems," Communications of the ACM, v. 21, n. 2, pp. 120-126, Feb 1978.
[3] R.L. Rivest, A. Shamir, and L.M. Adleman, "On Digital Signatures and Public Key Cryptosystems," MIT Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212, Jan 1979.
[4] Bruce Schneier, "Applied Cryptography; Protocols, Algorithms, and Source Code in C," John Wiley & Sons, Inc., 1994
[5] M.O. Rabin, "Digital Signatures and Public-Key Functions as Intractable as Fac-torization," MIT Laboratory for Computer Science, Technical Report, MIT/LCS/TR212, Jan 1979.
[6] Ching-Chao Yang, Tian-Sheuan Chang, and Chein-Wei Jen, "A New RSA Crypto-system 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.
[7] P. Adrain Wang, Wei-Chang Tsai, and C. Bernard Shung, "New Vlsi Architectures of RSA Public-Key Cryptosystem," in IEEE International Symposium on Circuit and System, June 9-12, 1997.
[8] Jen-Shiun Chiang, and Jian-Kao Chen, "An efficient VLSI architecture for RSA public-key cryptosystem," Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on Volume: 1, Page(s): 496 -499 vol.1, 1999.
[9] Jia-Lin Sheu, Ming-Der Shieh, Chien-Hsing Wu, and Ming-Hwa Sheu, "A Pipe-lined Architecture of fast modular multiplication for RSA cryptography," in Proc. of the IEEE International Symposium on, Vol. 2, pp.121-124. Vol. 2, 1998.
[10] Zhang, C.N.; Xu, Y.; Wu, C.C.,"A bit-serial systolic algorithm and VLSI imple-mentation for RSA" Communications, Computers and Signal Processing. 10 Years PACRIM 1987-1997 - Networking the Pacific Rim. 1997 IEEE Pacific Rim Con-ference on, vol. 2, pp. 523-526. Vol.2, 1997.
[11] Keshab K. Parhi, "A Systematic Approach for Design of Digit-Serial Signal Processing Architecture," IEEE Transactions on Circuits and Systems, Vol. 38, No.4, April 1991.
[12] M. Shand and J. Vuillemin, "Fast implementations of RSA cryptography," in Proc. 11th Symp. On Computer Arithmetic, pp. 252-259, 1993.
[13] P. L. Montgomery, "Modular multiplication without trial division," Math. Com-put., vol. 44, pp.519-521, Apr. 1985.
[14] H. Orup, "A 100Kbits/s single chip modular exponentiation processor," in HOT Chips VI, Symp. Rec., pp. 53-59, 1994.
[15] S. Ishii, K. Ohyama, and K. Yamanaka, "A single-chip RSA processor imple-mented in a 0.5 um rule gate array," in Proc. 7th Annu. IEEE Int. ASIC Conf. Ex-hibit, pp. 433-436, 1994.
[16] P. S. Chen, S. A. Hwang, and C. W. Wu, "A systolic RSA public key cryptosys-tem," in Proc. IEEE International Symposium on Circuit and Systems, vol. 4, pp. 408-411, 1996.
[17] Jyh-Huei Guo, Chin-Liang Wang, and Hung-Chin Hu, "Design and Implemen-tation of an RSA Public-key Cryptosystem," in Proc. IEEE International Sympo-sium on Circuit and Systems, vol. 1, pp. 504-507, 1999.
[18] R. Katti, "A modified Booth algorithm for high radix fix-point multiplication," IEEE Transactions on Very Large Scale Integration Systems, vol. 1, no. 2, pp. 164-167, Jane 1993.
[19] Jye-Jong Leu and A.-Y. Wu, "A Scalable Low-Complexity Bit-Serial VLSI Ar-chitecture for RSA Cryptosystem," in IEEE Workshop on Signal Processing Sys-tems (SiPS-99), pp. 586-595, Taipei, Oct. 1999.
[20] Jye-Jong Leu, and An-Yeu Wu, "Design Methodology For Booth-Encoded Montgomery Module Design For RSA Cryptosystem," To appear ISCAS 2000.
[21] R. Katti, "A modified Booth algorithm for high radix fix-point multiplication," IEEE Transactions on Very Large Scale Integration Systems, vol. 1, no. 2, pp. 164-167, Jane 1993.

指導教授

吳安宇(An-Yeu Wu)

審核日期

2000-7-11

推文