臺灣博碩士論文加值系統

隨著網際網路的普及，密碼系統變得越來越重要。如果我們想要確保每一次通信都能夠保持高度安全性，我們必須使用密碼系統。
密碼系統可分為兩種主要的類型。一種稱為公鑰(Public key)的密碼系統；另一個是私鑰(Secret key)的密碼系統。最著名的公開鍵密碼系統是RSA密碼系統。
在RSA密碼系統中，模數的數值很大。蒙哥馬利(Montgomery)提出了新的演算法。 這種演算法能夠設計出相對應的硬體且能有效地執行RSA運算。許多人改進原始的蒙哥馬利演算法以得到更好的硬體使用率和較佳的效能。
在本文中，介紹了模組化的加解密處理器設計。該設計是陳氏演算法的改進版本。每一個基本單元可以處理128位元的蒙哥馬利運算。
我們合併這些基本模組單元及加上適當的控制線路以便處理更大位元的RSA運算。有許多的方法可以改進我們的設計。如中國餘式定理(CRT)即為一個好辦法，但是這需要更多安全保護。

Combined with the widely used electrical communication, cryptosystem becomes more and more important. If we want to keep each communication in high secret, we must apply cryptosystem. There exist two main types of cryptosystems. One is the public-key cryptosystem; the other is the secret-key cryptosystem.
The most famous public-key cryptosystem is RSA cryptosystem. In a RSA cipher system, the bit length of the modulus is very big. Montgomery suggested a new algorithm, which can be implemented into hardware efficiently. So many people modified the original Montgomery's algorithm to achieve better hardware usage and less operation time. Chen and Yang are the most famous ones.
In this Thesis, a modular encryption/decryption processor is introduced. This is a modified version of the systolic array Montgomery processor. Each basic unit is with 128 bits, but we can combine these units to build a large-bit RSA cryptosystem.

中文部分
第一章 密碼系統簡介1
第二章 RSA密碼系統簡介3
第三章 RSA演算法6
第四章 硬體設計9
第五章 結論 11
英文部份
CHAPTER 1 INTRODUCTION TO CRYPTOSYSTEM1
1.1 Definitions1
1.2 Some of the Most Popular Techniques in Cryptography2
1.3 Applications of Cryptography5
CHAPTER 2 INTRODUCTION TO RSA CRYPTOSYSTEM7
2.1 RSA Cipher System7
2.2 Background Knowledge of RSA Cipher System.7
2.3 Procedures in an RSA Cipher Algorithm9
CHAPTER 3 RSA ALGORITHMS 13
3.1 Traditional Modular Exponential Algorithm 13
3.2 Montgomery’s Algorithm 15
3.3 Chen’s Algorithms 16
3.4 Yang’s Algorithm 19
CHAPTER 4 HARDWARE DESIGN 22
4.1 Hardware Structure 22
4.2 Systolic Array 24
4.3 Multiplier and Modular Unit Design 27
4.3.1 Multiplier Unit Design 27
4.3.2 Modular Unit Design 35
4.4 Controller Design 35
4.5 Advantages of our Design 40
4.6 Discussion 40
4.7 Comparison 42
CHAPTER 5 CONCLUSION 44
APPENDIX A 46
Verilog Simulation Result 1 46
Verilog Simulation Result 2 47
Verilog Simulation Result 3 48
REFERENCES 49

[1] RSA Laboratories, Frequently Asked Questions About Today’s Cryptography, Version 4.0, pp.1-101, 1999.
[2] Jennifer Seberry, Josef Pieprzyk, Cryptography, An Introduction to Computer Security, pp.1-130, Prentice Hall, 1989.
[3] R.L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol.21, No.2, pp.120-126, Feb. 1978.
[4] Kenneth H. Rosen, Elementary Number Theory And Its Applications, Second edition, pp.61-237, Addison-Wesley Publishing Company, 1988.
[5] W.T. Penzhorn, “Fast algorithms for the generation of large primes for the RSA cryptosystem,” Proceedings of the 1992 South African Symposium on Communications and Signal Processing, COMSIG '92, pp.169 —172, 1992.
[6] M.J.B. Robshaw, “Security estimates for 512-bit RSA,” Conference record of Microelectronics Communications Technology Producing Quality Products Mobile and Portable Power Emerging Technologies, WESCON '95, pp-409, 1995.
[7] J. Hastad, M. Naslund, “The security of individual RSA bits,” Proceedings of 39th Annual Symposium on Foundations of Computer Science, pp.510 -519, 1998.
[8] M. Shand, J. Vuillemin, “Fast implementations of RSA cryptography,” Proceedings of 11th IEEE Symposium on Computer Arithmetic, pp.252-259, 1993.
[9] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, Vol.44, No.170, pp.519-521, Apr. 1985.
[10] S.E. Eldridge, C.D. Walter, “Hardware Implementation of Montgomery’s Modular Multiplication Algorithm,” IEEE Transaction on Computers, Vol.42, No.6, pp.693-699, Jun. 1993.
[11] C.D. Walter, “Systolic modular multiplication,” IEEE Transactions on Computers, Vol.42, No.3, pp.376-378, Mar. 1993.
[12] A.A. Tiountchik, “Systolic nodular exponentiation via Montgomery algorithm,” Electronics Letters, 30th, Vol.34, No.9, pp.874-875, Apr. 1998.
[13] Po-Song Chen, Shih-Arn Hwang, Cheng-Wen Wu, “A systolic RSA public key cryptosystem,” IEEE International Symposium on Circuits and Systems, ISCAS '96, Connecting the World, Vol.4, pp.408-411, 1996.
[14] Ching-Chao Yang, Chein-Wei Jen, Tian-Sheuan Chang, “The IC design of a high speed RSA processor,” Proceedings of IEEE Asia Pacific Conference on Circuits and Systems ‘96, pp.33-36, 1996.
[15] Ching-Chao Yang, Tian-Sheuan Chang, Chien-Wei Jen, “A new RSA cryptosystem 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, Jul. 1998.
[16] Neil H.E. Weste, Kamran Eshraghian, Principles Of CMOS VLSI DESIGN, A System Perspective, Second Edition, Addison-Wesley Publishing Company, pp.465-624, 1993.
[17] von Volker Schindler, “High Speed RSA Hardware Based on Low-Power Pipelined Logic,” Doctor’s dissertation, Technische University at Graz, Austria, Jan. 1997.
[18] N. Takagi, “A radix-4 modular multiplication hardware algorithm for modular exponentiation,” IEEE Transactions on Computers, Vol.41, No.8, pp.949-956, Aug. 1992.
[19] C.D. Walter, “Space/Time Trade-offs for Higher Radix Modular Multiplication Using Repeated Addition,” IEEE Transactions on Computers, Vol.46, No.2, pp.139-141, Feb. 1997.
[20] S.Y. Kung, VLSI ARRAY PROCESSORS, Prentice Hall, pp.197-268, 1988.
[21] K. F. Lin, "Design and Implementation of an Encryption/Decryption Coprocessor", master thesis, 1998.