臺灣博碩士論文加值系統

本篇論文提出了一個新的模乘數演算法，我們稱之為 Bit-Oriented Split Modular Multiplication Radix-4（BSR4），此亦為整個 RSA 密碼系統的核心，並基於此演算法設計整個硬體架構。藉由 BSR4 演算法，我們不但將效能提升為傳統演算法的兩倍，更進一步降低了硬體的複雜度。此外，我們同時針對各部分電路做最佳化，以達到提升運算速度、降低消耗功率、以及降低整體面積的目的。最後，在 0.18um 製程下實現的硬體，可達到 586kbps @ 450MHz 的效能，並且消耗功率為 830mW。

This paper presents an RSA hardware design based on a new algorithm known as Bit-Oriented Split Modular Multiplication Radix-4 (BSR4), which is the core of RSA cryptosystem. By BSR4, we not only boost the performance double than the traditional algorithm but also simplify the complexity of hardware. Besides, we optimize all parts of circuit for speed-up, low-power, and small-area at the same time. The complete hardware has been implemented using cell-based 0.18um CMOS technology and delivers an average performance of 586kbps at 450MHz with 830mW power consumption.

第一章 序論 3
1-1 研究動機 3
1-2 研究方向 4
1-3 論文概述 4
第二章 RSA 密碼系統及演算法 5
2-1 RSA 密碼系統 5
2-2 模數運算的基本概念 7
2-3 基本模指數演算法 8
2-3.1 2-ary H-Algorithm 8
2-3.2 2-ary L-Algorithm 9
2-4 模乘法與模指數演算法 11
2-4.1 Montgomery’s Algorithm 11
2-4.2 Chen’s Modified Montgomery Algorithm 14
2-4.3 Bit-Oriented Split Modular Multiplication Radix-2 演算法（BSR2） 15
2-4.4 N-Oriented Radix-4 演算法（NR4） 18
2-4.5 Bit-Oriented Split Modular Multiplication Radix-4 演算法（BSR4） 20
第三章 RSA 硬體設計與比較 25
3-1 BSR2 硬體架構 25
3-1.1 整體架構 25
3-1.2 乘法和平方單元 27
3-1.3 Montgomery Module 30
3-2 NR4 硬體架構 31
3-3 BSR4 硬體架構 34
3-3.1 整體架構 34
3-3.2 Multiplier & Squarer 36
3-3.3 Modular Reduction Module 40
3-3.4 Carry Propagation Adder 41
3-4 數據分析與比較 42
3-4.1 運算迴圈數的分析與比較 42
3-4.2 硬體花費的分析與比較 44
第四章 電路的最佳化 47
4-1 效能的優化 47
4-1.1 Critical Path 的修改 47
4-1.2 其他效能的優化 50
4-2 面積和功率消耗的降低 51
4-2.1 使用 Gated Clock 技術 51
4-2.2 部分 Register 替換為 SRAM 52
4-2.3 部分 Register 替換為 Latch 53
4-2.4 Carry/Sum Register 架構的改善 54
4-2.5 Low-Power Flip-Flop Design 55
4-2.6 MUX-Adder Design 56
4-2.7 Adder4_2 Design 59
4-3 修改前後數據比較 60
第五章 硬體實現與測試 62
5-1 設計流程 62
5-1.1 Pin 腳定義 63
5-1.2 邏輯合成 65
5-1.3 Gate Level Simulation 67
5-1.4 Place & Route 69
5-1.5 Pre-Simulation 72
5-1.6 Post-Simulation 72
5-2 測試考量 73
5-2.1 Sub-Module Test 73
5-2.2 On Chip Clock Generator 74
5-2.3 On Chip Pattern Generator 75
5-3 測試流程 76
5-3.1 測試 Constant Register 和 Exponent Register 77
5-3.2 測試 Plaintext Register 和 Multiplier 78
5-3.3 測試 Squarer 78
5-3.4 測試 Modulus Register 與 R4MR 78
5-3.5 測試 CPA 79
5-3.6 測試整個 RSA Chip 的功能和運算時間 79
5-3.7 測試 RSA Chip 最高運算速度 79
5-3.8 測試 RSA Chip 的功率消耗 80
第六章 結論 81
6-1 相關作品的比較 81
6-1.1 學術界作品的比較 81
6-1.2 業界實做晶片的比較 82
6-2 研究總結 84
參考文獻 85

[1] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signature and public-key cryptosystems,” Com. of the ACM, vol.32, pp.120-126, Feb. 1978.
[2] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, 44(170):519-521, April 1985.
[3] Po-Song Chen, Shih-Arn Hwang, and Cheng-Wen Wu, “A systolic RSA public key cryptosystem,” Proc. IEEE Int. Symp. Circuits and Systems (ISCAS), pp. 408-411, May 1996.
[4] 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.
[5] 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.
[6] Jin-Hua Hong and Cheng-Wen Wu, “Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified Booth’s algorithm,” IEEE Trans. VLSI System, 2003.
[7] R. K. Kolagotla and W. R. Griescbach, “VLSI implementation of a 350MHz 0.35um 8-bit merged squarer,” Electron. Lett., vol.34, pp.47-48, Jan.1998.
[8] J. S. Wang et al, “An Ultra Low Power, Fast Lock-in, Small Jitter, All Digital Delay Locked Loop,” Proc. IEEE ISSCC, 2005, paper 22.7.
[9] H. T. Bui, Y. Wang, and Y. Jiang, “Design and Analysis of Low-Power 10-Transistor Full Adders Using Novel XOR-XNOR Gates,” IEEE Transaction on Circuit and System, vol. 49, January 2002.
[10] Oscal T. -C. Chen, and Robin Buey-Sin Sheen, “A Power-Efficient Wide-Range Phase-Locked Loop,” IEEE Solid-State Circuits, Vol. 37, No. 1, Jan. 2002.