臺灣博碩士論文加值系統

RSA密碼系統是一個非常著名的公開金匙密碼系統，其可以應用在需要加密的文件當中，也可用來對文件做簽署的動作，例如：電子銀行與網路交易的認證。另外，也可做為管理祕密金匙密碼系統中的金匙交換機制，這些都是RSA的應用範圍。本論文提出了一個可變動長度的指數架構，用以實現RSA公開金匙密碼系統。此指數架構可以去除RSA密碼系統在加密時不必要的乘法運算以提高執行效率。此RSA系統架構使用了一個由Montgomery演算法經過改良後的模乘法運算器，因為此運算器有平行運算的特性，所以搭配最簡單的二元法快速指數運算(Binary)，使得在不需額外的記憶體之下，即可達到高速的運算能力。
整個改良後的RSA加解密系統，在其演算法經由軟體模擬驗證無誤後，利用Verilog硬體描述語言將整個硬體架構實現。同時在”ModelSim-Altera Version 5.4e”的硬體模擬器也驗證無誤後，再經由”Quartus II 1.0”將其合成在APEX-20KEFC-1X的系列晶片上。512位元的RSA系統架構經合成後，其工作頻率可高達85MHz。若使用32位元長度的公開金匙來執行加密的動作，則平均每秒可加密1185K位元的資料，且若使用512位元長度的秘密金匙來執行解密的動作，則平均每秒可對81K位元資料完成解密的動作。

The famous RSA public key cryptosystem can be applied to many fields such as electronic bank and E-Commerce on Internet. The RSA system can encrypt and sign the data to hide and authenticate, respectively, and can be the key exchange system for secrete key systems, such as DES and AES. In this thesis, an adaptive exponential architecture is proposed. The architecture can remove the redundant exponential computations to obtain the higher efficiency in RSA cryptosystem, especially for data encryption. A pipeline modular multiplication, which is based on a modified Montgomery algorithm, is involved in the RSA system architecture. The simplest exponential algorithm Binary is proposed. This combinational architecture can achieve the best performance without any more additional memory.
The modified architecture is verified with the software on PC and no error happened. The implementation of the whole RSA system is accomplished with Verilog HDL code and confirmed by simulation with the tool ”ModelSim-Altera Version 5.4e”. And then synthesized to the Altera series chips, APEX-20KEFC, by using the tool ”Quartus II 1.0”. For 512 bits RSA architecture, the frequency is up to 85 MHz. The data rate for encryption with 32 bits public key is 1185 K-bits per second, and for decryption with 512 bits secrete key is 81 K-bits per second.

Acknowledgements ………………………………………………I
摘 要 ……………………………………………………………II
Abstract …………………………………………………………III
Contents …………………………………………………………IV
List of Figures ………………………………………………VI
List of Tables …………………………………………………VII
Chapter 1. Introduction ……………………………………1
Chapter 2. Cryptography and RSA Cryptosystem …………4
2.1Private Key Cryptosystem ……………6
2.2Public Key Cryptosystem …………… 6
2.3Mathematical Fundamental for RSA Algorithm 7
2.4RSA Public Key Cryptosystem ……… 9
2.4.1RSA Scheme …………………10
2.4.2Encryption and Decryption10
2.4.3Signature and Verification 11
2.4.4RSA Attacked ………………13
Chapter 3. The Fast Exponential Operation for RSA Cipher 14
3.1Binary Method …………………………15
3.2The Yacobi algorithm ………………… 18
3.3The Sliding Window Technique………19
3.4The Experiment Results with above Algorithms 22
Chapter 4. The Modular Multiplication, Montgomery … 24
4.1The Montgomery Algorithm ……………24
4.2The Modified Montgomery Algorithm 26
Chapter 5. Hardware Implementation of RSA Cipher …29
5.1The Modified Montgomery Multiplier Architecture … 30
5.2The Adaptive Exponential Architecture … 34
5.3The Modified Exponential Algorithm 36
5.4RSA System Architecture …………… 37
5.5Implementation and Simulation Results … 40
Conclusion and Further Work ………………………………48
Reference ………………………………………………………49
Appendix A ………………………………………………………51
A.1 Proof of Montgomery Algorithm ……………51
A.2 Mont(a,b) is an integer ……………………54

[1] R. Rivest, A. Shamir, and L. Adleman, “A method for
obtaining digital signatures and public-key
cryptosystems”, Commun, ACM, 1978, 21, pp. 120-126.
[2] HUI, L. C. K. and LAM, K. Y., “Fast square-and-multiply
exponentiation for RSA”, Electron Lett., 1994, Vol. 31,
No. 17, pp. 1396 -1397.
[3]賴溪松, 韓亮和張真誠, “近代密碼學及其應用”, 松崗,
1998.11, 二版.
[4] P. L. Montgomery, “Modular multiplication without trial
division”, Math. Comp., Apr. 1985, Vol.44, No.170, pp.519-
521.
[5] C. D. Walter, “Montgomery exponentiation needs no final
subtractions”, Electronics Letters, 14th October 1999,
Vol. 35, No. 21.
[6] Jyh-Huei Guo, Chin-Liang Wang, and Hung-Chih Hu, “Design
and Implementation of an RSA Public-Key Cryptosystem”,
IEEE, 1999, I-504.
[7] Y. Yacobi, “Exponentiating Faster with Addition Chains,”
Advances in Eurocypt’90, New York, Springer-Verlag, 1990,
pp. 222-229.
[8] S. C. Pohlig and M. E. Hellman, “An Improved for Computing
Logarithms in GF(p) and Its Cryptographic Significance“,
IEEE Transactions on Information Theory, Vol. 24, No. 1,
pp. 106-111, Jan. 1978.
[9] YEN. S. M. and LAIH. C. S., “Common-multiplicand
multiplication and its applications to public key
cryptography”, Electron Lett., 1993, Vol. 29, No. 17, pp.
1583-1584.
[10] C. W. Chiou, “Parallel Implementation of the RSA Public-
key Cryptosystem”, International Journal of Computer
Mathematics, 1993, Vol. 48, pp. 153-155.
[11] CHEN. C. Y., CHANG. C. C. and YANG. W. P. “Hybrid method
for modular exponentiation with precomputation”, Electron
Lett., 14th March 1996, Vol. 32, No. 6, pp. 540-541.
[12] C. C. Yang, T. S. Chang and C.W. Jen, “A new RSA
cryptosystem hardware design based on Montgomery’s
algorithm”, IEEE Trans. Circuits and Systems, July 1998,
vol. CAS-45, pp. 908-913.
[13] 楊吳泉, “現代密碼學入門與程式設計”, 全華, 1998.11, 初版.
[14] C. C. Lin, J. H. Jeng, Member IEEE and T. K. Truong,
Fellow IEEE, “Fast exponentiation for RSA Cipher”, 17th
Workshop on Combinatorial Mathematics Computation Theory,
Apr. 2000, pp. 146-149.