淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


系統識別號 U0002-2502201310040300
中文論文名稱 快速大整數模餘計算方法實作之研究
英文論文名稱 The Implementation of Efficient Large Integer Modular Reduction Method
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 101
學期 1
出版年 102
研究生中文姓名 林哲緯
研究生英文姓名 Jhe-Wei Lin
學號 698410254
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2013-01-10
論文頁數 31頁
口試委員 指導教授-黃仁俊
委員-蘇豐富
委員-黃心嘉
委員-黃仁俊
中文關鍵字 蒙哥馬利模餘  巴雷特模餘  實現模餘  Android 
英文關鍵字 Montgomery  Barrett  Implement Modular Reduction  Android 
學科別分類 學科別應用科學資訊工程
中文摘要 大部分的電腦密碼學技術如:RSA、DSA、Diffie-Hellman等在運作過程之均使用到大量的模指數運算;模指數運算包含大量的模餘運算,而這也是整個電腦密碼技術運作過程中最耗時間與系統資源的部分,若能改善模餘運算效能對現今的電腦密碼技術的執行效能將可造成巨大的影響。為了能有效率的進行模餘運算,目前主流的兩個方法是:蒙哥馬利模餘和巴雷特模餘演算法。雖然直觀上以硬體來實作這些運算可能會有較好的效率,但硬體的建置存在缺乏彈性的弱點且一般的行動裝置考量到降低硬體建置成本,幾乎都不會考量納入此特殊硬體,因此一般的行動裝置在運作網路安全協定執行電腦密碼技術時僅以軟體形式運作。本篇論文探討重要的模餘演算法 (Modular Reduction Algorithm) 之原理與實作於Android 平台之方法,並分析比較其計算時間,又計算耗電量情形與計算時間成正比關係,故藉由時間分析結果也可以了解不同模餘方法間造成的耗電差異。
英文摘要 Most of the cryptographies like RSA, DSA and Diffe-Hellman should perform the Modular Exponentiation Operation which includes many Modular Operations. However, this is the most time and resources consuming part of the entire cryptography operating process. If we can improve Modular Operation efficacy then we might make a revolutionary impact on the implementation efficacy of cryptography nowadays. Currently, two principle methods are used to implement modular operation efficiently: Montgomery Reduction and Barrett modular reduction Algorithm. Though it is more efficient to implement these calculations by using hardware, the disadvantage of the lacking of flexibility and the higher cost when establishing hardware are the reasons that why general mobile devices refuse to use these special hardware. As a result, general mobile devices only operate in software forms when operating network security protocols. This paper explores the theorem and the methods of implementing important Modular Reduction Algorithm on Android platform. We analyze and compare the calculation time and find that it is directly proportional to the power consumption. With these results of time analysis, we are able to understand the variations of power consumption by using different modular operations.
論文目次 目 錄
第一章 緒論………………………………………………………………1
第二章 背景相關知識……………………………………………………3
2.1 Original-Montgomery………………………………………………3
2.2 Variant-Montgomery………………………………………………4
2.3 Barrett modular reduction…………………………………………5
2.4 Multiple-precision division…………………………………………6
第三章 研究方法與實測環境……………………………………………8
3.1 Original-Montgomery 實作探索……………………………………9
3.2 Variant-Montgomery 實作探索……………………………………11
3.3 Barrett modular reduction實作探索………………………………12
3.4 Multiple-precision division實作探索………………………………15
第四章 實測結果的討論與分析…………………………………………17
第五章 結論與未來研究方向……………………………………………22
參考文獻…………………………………………………………………23
Appendix…………………………………………………………………24

表 目 錄
表1. 測試環境平台………………………………………………………17
表2. 手機測試數據………………………………………………………17
表3. 平板測試數據………………………………………………………19
表4. Android模擬器(AVD) 測試數據……………………………………20
參考文獻 [1] P. Barrett, "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor," Proc. CRYPTO'86, pp. 311-323, 1987.
[2] Ho-Liang Chen, "Study on Modular Multiplication Algorithms for Smart Card Applications," M.S. paper, University of National Cheng Kung, Tainan City, Taiwan R.O.C., 2002.
[3] W. Hasenplaugh, G. Gaubatz, V. Gopal, "Fast Modular Reduction," Computer Arithmetic, 2007. ARITH '07. 18th IEEE Symposium on.
[4] A.J. Menezes, P.C. Van Oorschot, S.A. Vanstone, "Handbook of Applied Cryptography," chapter 14. pp. 591 - 634, 1997.
[5] P. L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, Vol. 44, pp. 519 - 521, 1985.
[6] C. Paar, J. Pelzl, "Understanding Cryptography," chapter 6-8. pp. 149 - 238, 2010.
[7] D.S.Phatak, T.Goff, "Fast modular reduction for large wordlengths via one linear and one cyclic convolution," Computer Arithmetic, 2005. ARITH-17 2005. 17th IEEE Symposium on.
[8] Nigel Smart, " Cryptography, An Introduction: Third Edition," chapter 15. pp. 233 - 245, 2004.
[9] 楊吳泉, 現代密碼學入門與程式設計, 台北: 全華科技圖書公司, 1996.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2018-03-07公開。
  • 同意授權瀏覽/列印電子全文服務,於2018-03-07起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信