臺灣博碩士論文加值系統

由於現今科技愈來愈發達，資訊技術發展迅速且普及，「網路」已成為我們生活中不可或缺的一部分，無論是網路上的交易、訊息的傳遞、資料的存取…等，都離不開網路，也因此資訊安全愈來愈受到重視。而為了使資料傳輸時具有足夠的安全性，必須有一套完整的系統來保護資料不被竊取，這也顯示出了密碼系統的重要性。
在眾多的密碼系統中，RSA公開金鑰密碼系統(public-key cryptosystems)是目前使用最廣泛的密碼系統之一，但其密碼系統的金鑰長度通常為1024位元或2048位元以上，才能夠達到相當程度的安全性。若在如此龐大的位元數下，以軟體方式進行RSA加解密運算則無法達到即時處理的要求。為了有效降低運算時間，本論文採用硬體的方式實現RSA加解密。在RSA密碼系統中有大量的模數指數運算與模數乘法運算，而其中模數乘法運算占整體大部分運算時間，而為了使其更易於在硬體上實現，本論文採用了蒙哥馬利演算法，將原本在硬體上難以實現的除法，可以利用一連串加法和右移來取代並實現。
但在如此大的位元數運算下，訊號線會有大量扇出(fanout)的問題，所以我們採用字組式設計來降低扇出數，一方面可以達到節省面積，另一方面也更利於可調式設計，並再結合高基數與布斯(Booth)編碼來增加效能。本論文除了引用上述幾種方法之外，還採用單一個處理單元的設計，把模數乘法運算中全部運算整合成一個處理單元，並將其進行管線化排程。如此一來，可大幅降低硬體面積，來達到本論文所提出的低成本可調式高基數字組式蒙哥馬利模數乘法運算設計概念。

Nowadays, communication technology has developed rapidly and become more and more common. “Internet” has become an essential part in our daily life, and we cannot live without it for online trading, message transmission, data access and so on. Therefore, people have paid more attention to information security than before. In order to ensure the safety of data transmission sufficiently, there must be a complete system to protect data from being stolen, and it shows the importance of cryptosystem.
Among numerous cryptosystems, RSA public-key cryptosystems is one of the most widespread cryptosystems currently. However, its key length is usually more than 1024 or 2048 bits to be able to reach a certain degree of safeness. If we execute RSA encryption and decryption with software, we cannot meet the request of real-time processing. Therefore, to decrease computing time efficiently, we execute RSA encryption and decryption with hardware in this thesis. There are plenty of modular exponentiation and modular multiplication in RSA cryptosystems, and modular multiplication occupies most of the computing time. In order to make it more possible to be accomplished on hardware, we adopt Montgomery Algorithm to make division, which is originally difficult to be accomplished on hardware, be replaced by a series of addition and shift right to work.
However, under the computation with such a large number of bits, there might be the problem of many fan-outs of signal lines. Thus, we adopt word-based design to lower the number of fan-outs. It can not only save the areas but also make a scalable design easily. What''s more, it increases the performance by combining with high-radix and Booth multiplier. In addition to the methods mentioned above, this thesis also adopts the architecture of a single processing element, which contains all computation of Montgomery modular multiplier, and makes it into pipeline. Therefore, we can decrease hardware area significantly to accomplish the design of a low-cost and scalable high-radix word-based Montgomery modular multiplier.

論文提要 iii
摘要 iv
Abstract v
目錄 vii
圖目錄 ix
表目錄 xi
第一章 緒論 1
1.1 研究動機 1
1.2 論文大綱 3
第二章 研究背景 4
2.1 RSA密碼系統 4
2.2 模數指數演算法 6
2.2.1 H模數指數演算法 7
2.2.2 L模數指數演算法 8
2.3 蒙哥馬利演算法 9
2.4 進位節省蒙哥馬利演算法 12
2.4.1 5-to-2 CSA蒙哥馬利演算法及架構 12
2.4.2 4-to-2 CSA蒙哥馬利演算法及架構 15
第三章 高基數字組式蒙哥馬利乘法器 17
3.1 字組式蒙哥馬利演算法及架構 17
3.1.1 字組式蒙哥馬利演算法 17
3.1.2 字組式蒙哥馬利架構 20
3.1.3 字組式蒙哥馬利演算法的資料相依性 21
3.2 高基數蒙哥馬利演算法 23
3.2.1 傳統高基數蒙哥馬利演算法 23
3.2.2 傳統高基數蒙哥馬利之乘法省略演算法 25
3.2.3 傳統高基數蒙哥馬利之加法省略演算法 26
3.2.4 傳統高基數蒙哥馬利之商數管線化演算法 28
3.3 蒙哥馬利演算法之省略比較與減法 29
3.4 Radix-4 布斯乘法器 30
第四章 提出的演算法及硬體架構設計 33
4.1 可調式設計與效能分析 33
4.2 提出的低成本可調式高基數字組式蒙哥馬利模數乘法演算法 35
4.3 提出的低成本可調式高基數字組式蒙哥馬利模數乘法器架構 39
4.4 管線化排程 46
4.5 採用H模數指數演算法及PE功能結合 50
第五章 實驗結果 51
5.1 實驗步驟與方法 51
5.2 實驗數據 53
第六章 結論與未來研究方向 57
6.1 結論 57
6.2 未來研究方向 57
參考文獻 58

[1]R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signature and public-key cryptosystems,”Communications of the ACM, vol. 21, pp. 120-126, Feb. 1978.
[2]P. L. Montgomery, “Modular multiplication without trial division,” Mathmatics Computation, vol. 44, pp. 519-521, Apr. 1985
[3]C. Walter, “Systolic Modular Multiplication,” IEEE Trans. Computers, vol. 35, no. 1, pp. 1-12 Jan, 1986.
[4]P. Kornerup, “High-Radix Modular Multiplication for Cryptosystems,” Proc. IEEE Symp. Computer Arithmetic, pp. 277-283, Jun 1993.
[5]Holger Orup, “ Simplifying Quotient Determination in High-Radix Modular
Multiplication, ” IEEE Symp. Computer Arithmetic, pp. 193-199, Jul. 1995.
[6]T. Blun and C. Paar, “Montgomery Modular Exponentiation on Reconfigurable Hardware,” Proc. 14th IEEE Symp. Computer Arithmetic, pp. 70-77, Apr. 1999
[7]C. D. Walter, “Montgomery exponentiation needs no final subtractions,” Elextron. Lett., vol. 32, no. 21, pp. 1831-1832, Oct. 1999.
[8]T. W. Kwon, C. S. You, W. S. Heo, Y. K. Kang, and J. R. Choi, “Two implementation methods of a 1024-bit RSA cryptoprocessor based on modified Montgomery algorithm,” Proc. IEEE Int. Symp. Circuits Syst., vol. 4, pp. 650-653, May 2001.
[9]A. F. Tenca and C. K. Koc, “A scalable architecture for modular multiplication based on Montgomery’s algorithm,” IEEE Tans. Computers, vol. 52, no. 9, pp. 1215-1221, Sept. 2003.
[10]A. F. Tenca and A. Tawalbeh, “An efficient and Scalable Radix-4 Modular Modular Multiplier Design Using Recoding Techniques,” Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 1445-1450, Nov. 2003.
[11]TSMC 0.90-μm (CL090G) Process 1.2-Volt SAGE-XTM Standard Cell Library Databook, Artisan Components, Sunnyvale, CA, Jan. 2004.
[12]A. Cilardo, A. Mazzeo, L. Romano, and G. P. Saggese, “Carry-save Montgomery modular exponentiation on reconfigurable hardware,” Proc. Des., Autom. Test Eur. Conf. Exhibition, vol. 3, pp.206-211, Feb. 2004.
[13]C. McIvor, M. McLoone, and J. V. McCanny, “Modified Montgomery modular multiplication and RSA exponentiation techniques,” IEE Proc. Computers and Digital Techniques, vol. 151, no. 6, pp. 402-408, Nov. 2004.
[14]D. Harris, R. Krishnamurthy, S. Mathew, and S. Hsu, “An improved unified scalable radix-2 Montgomery multiplier,” IEEE Symp. Computer Arithmetic, pp. 1196-1200, Jan. 2005.
[15]R. V. Kamala and M. B. Srinivas, “High-Throughput Montgomery Modular Multiplication,” IFIP International Conference on Very Large Scale Integration, pp. 58-62, Oct. 2006.
[16]N. Pinckney and D. Harris, “Parallelized radix-4 scalable Montgomery multipliers,” J. Integrated Circuits and Syst., vol. 3, no. 1, pp. 39-45, Mar. 2008.
[17]P. Amberg, N. Pinckney, and D. M. Harris, “Parallel High-Radix Montgomery Multipliers,” Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 772-776, Oct. 2008.
[18]CIC Referenced Flow for Cell-based IC Design, National Chip Implementation Center, Hsinchu, Taiwan, 2008.
[19]M. D. Shieh and W. C. Lin. “Word-Based Montgomery Modular Multiplication Algorithm for Low-Latency Scalable Architecutures,” IEEE Trans. Computers, vol. 59, no. 8, pp. 1145-1151, Aug. 2010.
[20]G. Sassaw, C.J. Jimenez, and M. Valencia, “High Radix Implementation of
Montgomery Multipliers with CSA,” International Conference on
Microelectronics (ICM), pp. 315-318, Dec. 2010.
[21]M. Huang, K. Gaj, and T. El-Ghazawi, “New Hardware Architectures for Montgomery Modular Multiplication Algorithm,” IEEE Trans. Computer, vol. 60, no. 7, pp. 923-936, July 2011.
[22]S. H. Wang, W. C. Lin, J. H. Ye, and M. D. Shieh, “Fast Scalable Radix-4 Montgomery Modular Multiplier,” IEEE International Symposium Circuits and Systems, pp. 3049-3052, May 2012.
[23]張凱程, “適用於RSA加解密系統之高效能低功率可調式模數乘法器,” 國立中山大學, 碩士論文, July 2010.
[24]許桓偉, “適用於RSA 加解密系統之高效能低功率模數乘法器,” 國立中山大學, 碩士論文, 2011.
[25]許弘譯, “適用於RSA 密碼系統的高效能基數-4 蒙哥馬利模數乘法器,” 國立中山大學, 碩士論文, 2011.
[26]余其坤, “適用於低功率應用的多重模式浮點乘加器,” 國立中山大學, 碩士論文, 2011
[27]陳佳妏, “低耗能多重字組模數乘法器之設計,” 國立中山大學, 碩士論文, July 2012
[28]邱昶騰, “高效能高基數蒙哥馬利模數乘法器,” 國立中山大學, 碩士論文, July 2013.
[29]蔡嘉和, “高效能基數四之字組式蒙哥馬利模數乘法器,” 國立中山大學, 碩士論文, July 2014.
[30]呂仁堯 , “高效能高基數之字組式蒙哥馬利模數乘法器,“ 國立中山大學, 碩士論文, 2014
[31]陳俊吉,“高基數字組式蒙哥馬利乘法器之通用化設計方法, ” 國立中山大學, 碩士論文, 2015.
[32]陳彥儒,“基於混合式基數字組式蒙哥馬利模數乘法演算法之RSA密碼演算法硬體架構, ” 國立中山大學, 碩士論文, 2016.
[33]李柏翰,“快速RSA加解密系統之低成本模指數架構, ” 國立中山大學, 碩士論文, 2017.
[34]A. Miyamoto, N. Homma, T. Aoki, and A. Satoh, “Systematic Design of RSA Processors Based onHigh-Radix Montgomery Multipliers,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 7, pp. 1136-1146, July. 2011