跳到主要內容

臺灣博碩士論文加值系統

(44.221.70.232) 您好!臺灣時間:2024/05/29 10:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:謝瑞鴻
研究生(外文):Jui-Hung Hsieh
論文名稱:針對RSA的有效率模指數及模乘法運算
論文名稱(外文):Efficient Modular Exponentiation and Modular Multiplication for RSA Public-Key Cryptosystem
指導教授:葉經緯
指導教授(外文):Ching-Wei Yen
學位類別:碩士
校院名稱:國立中正大學
系所名稱:電機工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:改良式的Montgomry演算法迴圈開展功率消秏公開金鑰密碼系統混合式2n H-演算法
外文關鍵詞:modified Montgomry's algorithmloop unfoldingpower consumptionpublic-key cryptosystemhybrid 2n H-algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:319
  • 評分評分:
  • 下載下載:34
  • 收藏至我的研究室書目清單書目收藏:2
隨著對網路及通訊產品的需求日益增加,而相對的安全性問題也愈來愈受重視,由Rivest, Shamir, 及Adleman於1978所提的RSA密碼系統是目前資料加解密及數位簽證的主流之一。在RSA密碼系統中,模指數及模乘法為其核心算術運算,而如何發展出一個運算快速且低功率消秏的模指數及模乘法演算法及電路設計,就是本論文探討的重點。
在本論文中,我們提出一個“以四為基底”的改良式Montgomery演算法來執行模乘法的運算,並與“以二為基底”及“以八為基底”之改良式的Montgomery演算法作比較。採用本實驗室的0.35µm SPQM CCU35A元件庫在125Mhz工作頻率下,由EPIC公司所提供的PowerMill軟體作功率的分析,我們可以很清楚的看到“以四為基底”改良式的Montgomery演算法可獲得最佳的功率延遲積。為了更進一步達到低功率消秏的目的,本論文亦打破過去文獻中對模指數運算所採用2-ary H-演算法及L-演算法,而改採用混合式2n H-演算法,此演算法可以減少模乘法的次數,進而達到低功率消耗的設計。

With the increasing needs of networking and the product of communication, meanwhile, the opposed problem of security has been watched. In 1978, RSA was proposed by Rivest, Shamir, and Adleman and is the fashion of encryption and decryption of data and digital signature. In RSA cryptosystem, modular exponentiation and modular multiplication is the core arithmetic operation and how to develop a high speed and low power consumption algorithm and circuit design of modular exponentiation and modular multiplication is the major discussion of this thesis.
In the thesis, we propose a “radix-4” modified Montgomery algorithm to execute the operation of modular multiplication and comparison with “radix-2” and “radix-8” modified Montgomery algorithm. Adopting 0.35µm SPQM CCU35A cell library of our laboratory and at working frequency of 125Mhz, meanwhile, analysis of power with the software of PowerMill which is proposed by the company of EPIC. We can clearly see that “radix-4” modified Montgomery algorithm can achieve the optimal power-delay product. In order to forward achieve the goal of low power consumption, the thesis adopt hybrid 2n H-algorithm and also break the past literature which adopt 2-ary H-algorithm and 2-ary L-algorithm. The proposed algorithm and reduce the numbers of multiplication and achieve the design of low power consumption.

第一章 導論……………………………………………………………...1
1-1 簡介…………………………………………………………………………..1
1-2 研究方向及動機……………………………………………………………..1
1-3 章節的安排…………………………………………………………………..2
第二章 RSA密碼系統與相關研究……………………………………..3
2-1 密碼系統的基本功能………………………………………………………..3
2-2 RSA密碼系統……………………………………………………………….4
2-3 RSA模數運算演算法……………………………………………………….6
2-3.1 二元法、m-ary法及混合式2n H-演算法之模指數演算法……………6
2-3.2 模乘法演算法…………………………………………………………..11
第三章 低功率RSA演算法的分析與硬體設計………………………17
3-1 低功率積體電路設計的觀念………………………………………………17
3-1.1演算法層面的功率減小……...…………………………………………..17
3-1.2架構層面的功率減小…………………………………………………….19
3-1.3邏輯層面的功率減小…………………………………………………….20
3-2 基底二改良式的Montgomery演算法推導、證明及相對應之硬體架構分析………………………………………………………….………………….21
3-2.1基底二改良式的Montgomery演算法……………………………………22
3-2.2基底二改良式的Montgomery演算法之相對硬體架構………………..23
3-3基底四改良式的Montgomery演算法推導、證明及相對應之硬體架構分析.…………………………………..………………………………………..28
3-3.1基底四改良式的Montgomery演算法…………………………………...28
3-3.2基底四改良式的Montgomery演算法之相對硬體架構……………….34
3-4基底八改良式的Montgomery演算法推導、證明及相對應之硬體架構分析……………………………………………………………………………..41
3-4.1基底八改良式的Montgomery演算法………………………………….41
3-4.2基底八改良式的Montgomery演算法之相對硬體架構………………..44
第四章 低功率RSA演算法的模擬與討論……………………………50
4-1 設計流程…………………………………………………………………….50
4-2 功率消秏及主要路徑延遲的分析………………………………..…………52
4-2.1基底二演算法的功率消秏及主要路徑延遲…………….………………52
4-2.2基底四演算法的功率消秏及主要路徑延遲…………….………………54
4-2.3基底八演算法的功率消秏及主要路徑延遲………….…………………56
4-3 實驗數據………………………………………………………………….….58
4-3.1延遲數據比較…………………………………………………………….58
4-3.2電晶體數目比較…………………………..……………………………...63
4-3.3功率消秏分析………………………………….…………………………64
第五章 結論與未來研究及發展方向…………………………………65
參考文獻………………………………………………………………..66

[1] D. E. Knuth, The Art of Computing, vol. 2, Seminumerical Algorithms, Addison-Wesley, New York, 1981.
[2] R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signature and Public-Key Cryptosystems,” Com. of the ACM, vol. 21, pp. 120-126, Feb. 1978.
[3] P. L. Montgomery, “Modular Multiplication without Trial Division,” Math. of Computation, vol. 44, pp.519-512, Apr. 1985.
[4] Colin D. Walter, “Systolic Modular Multiplication,” IEEE Trans. on Computers, vol. 42, pp.376-378, March. 1993.
[5] Stephen E. Eldridge and Colin D. Walter, “Hardware Implementation of Montgomery’s Modular Multiplication Algorithm,” IEEE Trans. on Computers, vol. 42, pp.693-699,1993.
[6] P. Adrian Wang, Wei-Chang Tsai, C. Bernard Shung, “New VLSI Architectures of RSA Public-Key Cryptosystem,” IEEE International Symposium on Circuits and System, pp.2040-2043, 1997.
[7] Thomas Blum, Christof Paar, “Montgomery Modular Exponentiation on Reconfigurable Hardware,” 14th IEEE Symposium on Computer Arithmetic, pp.70-77, 1999.
[8] Min-Sup Kang, Done-Wook Kim, “Systolic Array Based on Fast Modular Multiplication Algorithm for RSA Cryptosystem,” Proceedings of the IEEE Region 10 Conference TENCON 99, vol.1 , pp.305-308, 1999.
[9] Ching-Chao Yang, Tian-Sheuan Chang, Chein-Wei Jen, “A New RSA Cryptosystem Hardware Design Based on Montgomery’s Algorithm,” IEEE Transaction on Circuit and System II : Analog and Digital Signal Processing, vol.45, pp.908-913, 1998.
[10] Jin-Hua Hong and Cheng-Wen Wu, “Radix-4 Modular Multiplication and Exponentiation Algorithms for the RSA Public-Key Cryptosystem,” Proceedings of the ASP-DAC 2000 on Design Automation Conference, pp.565-570, 2000.
[11] 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 Very Large Scale Integration (VLSI) Systems, vol.7, pp.280-284, 1999.
[12] A. Vandemeulebroecke, E. Vanzieleghem, T. Denayer, and P. G. A. Jespers, “A New Carry-Free Division Algorithm and its Application to a Single-Chip 1024-b RSA Processor,” IEEE Journal of Solid-State Circuits, vol.25, June 1990.
[13] Jia-Lin Sheu, Ming-Der Shieh, Chien-Hsing Wu, and Ming-Hwa Sheu, “A Pipelined Architecture of Fast Modular Multiplication for RSA Cryptography,” IEEE International Symposium on Circuits and System, vol.2, pp.121-124, 1998.
[14] N. Takagi and S. Yajima, “Modular Multiplication Hardware Algorithms With a Redundant Representation and Their Application to RSA Cryptosystem,” IEEE Trans. Compt., vol 41, pp887-891, July 1992.
[15] S. Sbab, A. J. Al-Kbalili, D. Al-Kalili, “Comparison of 32-bit Multipliers for Various Performance Measures,” Proceedings of the 12th International Conference on Microelectronics , pp.75-80, 2000.
[16] Brian S. Cherkauer and Eby G. Friedman, “A Hybrid Radix-4/Radix-8 Low Power Signed Multiplier Architecture,” in IEEE Trans. on Circuit and Systems, pp.656-659, 1997.
[17] Brian Millar, Philip E. Madrid, and Earl E. Swaltzlander , “A Fast Hybrid Multiplier Combining Booth and Wallace/Dadda Algorithm,” in IEEE Trans. on Circuit and Systems, pp.158-165, 1992.
[18] Anantha P. Chandrakasan, Robert W. Brodersen, “Low Power Digital CMOS Design,” in Chapter 7 of Minimizing Switched Capacitance, Kluwer Academic Publishers, May 1995. ISBN 0-7923-9576-X.
[19] Abdellatif Bellaouar, and Mohamed I. Elmasry, “Low-Power Digital VLSI Design : Circuit and Systems,” in Chapter 7 of VLSI CMOS SUBSYSTEM DESIGN, and in Chapter 8 of LOW-POWER VLSI DESIGN METHODOLOGY, Kluwer Academic Publishers, May 1995. ISBN 0-7923-9587-5.
[20] W. A. Chren, Jr., and C. H. Brogdon, “RSA Decryption Using The One-Hot Residue Number System,” IEEE 39th Midwest symposium on Circuits and Systems, vol.1, pp.551-554, 18-21 Aug , 1996.
[21] T. Callaway and E. Swartzlander, Jr., “Optimizing Arithmetic Elements for Signal Processing,” VLSI Signal Processing V, pp.91-100, IEEE Special Publications, 1992.
[22] M. Annaratine and W. Z. Shen, “The Design of a Booth Multiplier: NMOS vs. CMOS Technology,” in Proceeding of International Symposium on VLSI Technology, Systems, and Applications, pp.324-328, 1985.
[23] 王進賢,VLSI電路設計,高立圖書有限公司。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 周宏室(民82):我國未來體育課程走向。臺灣體育,65期,2-4頁。
2. 施登堯(民89):九年一貫「健康與體育」領域分段能力指標之探討。學校體育,10卷1期,19-27頁。
3. 計惠卿(民84):教師資訊素養需求分析之研究設計建議。視聽教育學報,1期,279-294頁。
4. 計惠卿(民84):教師資訊素養需求分析之研究設計建議。視聽教育學報,1期,279-294頁。
5. 施登堯(民89):九年一貫「健康與體育」領域分段能力指標之探討。學校體育,10卷1期,19-27頁。
6. 施登堯(民89):九年一貫「健康與體育」領域分段能力指標之探討。學校體育,10卷1期,19-27頁。
7. 周宏室(民82):我國未來體育課程走向。臺灣體育,65期,2-4頁。
8. 周宏室(民82):我國未來體育課程走向。臺灣體育,65期,2-4頁。
9. 沈亞梵(民89):後現代媒體資源整合與發展。教學科技與媒體,50期,20-30頁。
10. 沈亞梵(民89):後現代媒體資源整合與發展。教學科技與媒體,50期,20-30頁。
11. 沈亞梵(民89):後現代媒體資源整合與發展。教學科技與媒體,50期,20-30頁。
12. 李榮哲(民88):電腦多媒體於運動學習的運用。國民體育季刊,28卷2期,27-35頁。
13. 李榮哲(民88):電腦多媒體於運動學習的運用。國民體育季刊,28卷2期,27-35頁。
14. 李榮哲(民88):電腦多媒體於運動學習的運用。國民體育季刊,28卷2期,27-35頁。
15. 李勝富(民85b):科技與教育改革。教育資料與研究,12期,50-56頁。