臺灣博碩士論文加值系統

本論文提出了在RSA密碼系統上可擴展的實作方法。這項設計的架構採用改良的蒙哥馬利模數乘法器以及蒙哥馬利次方梯演算法。可支援4096位元以下的所有長度。本論文提出的演算法比較傳統的模數指數運算設計有更快的速度。在RSA加密運算中，針對1024位元、2048位元、4096位元公鑰的運算時間分別需要3.5ms、13.7ms、106ms。
另外我們改進了混沌映射基礎下的亂數產生器。在sp800-22測試下，此設計比較傳統設計有更高的通過率。此設計嵌入在RSA密碼系統中抵抗SPA和DPA攻擊而不用增加額外乘法運算的時間。

This thesis introduces a scalable hardware implementation of RSA cryptosystem. The architecture of this work is modified by the Montgomery modular multiplier and it based on Montgomery powering ladder algorithm. It can work in any length less than 4096-bit. This proposed algorithm provides a shorter latency on modular exponentiation operations than other works. It takes 3.5 ms, 13.7 ms, and 106 ms to complete a 1024-bit, 2048-bit, and 4096-bit key length of RSA calculation time respectively.
Furthermore, we modify random number generator based on chaotic map. Testing by SP800-22, this work has higher passing rate than previous work. This embedded in RSA cryptosystem for against SPA and DPA without extra cycle for processing multiplications.

1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Thesis Organization 4
2 RSA Cryptosystem and Random Number Generator 5
2.1 Mathematics Foundation 5
2.1.1 Number Theory 5
2.1.2 Montgomery Method 8
2.2 RSA Algorithm 10
2.2.1 RSA Scheme 10
2.2.2 R-L and L-R Algorithm 12
2.2.3 Montgomery Powering Ladder 13
2.3 Power Analysis 14
2.3.1 Simple Power Attack (SPA) 15
2.3.2 Differential Power Attack (DPA) 16
2.4 Random Number Sequence 17
3 Proposed RSA Architecture 19
3.1 Word-based Montgomery Multiplication 19
3.1.1 Proposed Word-based Montgomery Multiplication Architecture I 21
3.1.2 Proposed Word-based Montgomery Multiplication Architecture II 22
3.2 Architecture of Proposed Montgomery Multiplier 26
3.2.1 Processing Unit 26
3.2.2 Number of Processing Unit Size of Word 27
3.2.3 Montgomery Multiplier with Flexible Length 28
3.3 Random Bit Generator 29
3.3.1 Random Bit Generator from Chaotic Map 29
3.3.2 Proposed Dynamic Random Bit Generator 31
3.4 Proposed RSA Crypto-core with RNG 32
4 Implement Result and Comparison 36
4.1 RNG Testing 36
4.2 Implement with Cell Base Design 38
5 Conclusion 41
Bibliography 42

[1] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. IT-22, no. 6, pp. 644-654,1976.
[2] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.
[3] T. E. Gamal, “A public key cryptosystem and a signature scheme based on discrete alogarithms,” in Proceedings of CRYPTO 84 on Advances in cryptology. New York, NY, USA: Springer-Verlag New York, Inc., 1985, pp. 10–18.
[4] PKCS#1: RSA Cryptography, RSA Laboratories Std. 800-57, 2002.
[5] Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry - RSA digital signature technique, ANSI Std. X9.31, 1998.
[6] K. Koc, “High-speed RSA implementation,” tech. rep., RSA Laboratories, 1994.
[7] M. Joye, and S-M. Yen, “The Montgomery Powering Ladder”, CHES 2002, LNCS 2523, pp. 291–302, Springer-Verlag, 2003
[8] Sung-Ming Yen and Chi-Sung Laih. Common-multiplicand multiplication and its application to public-key cryptography. Electronics Letters, 29(17):1583–1584, August 1993v
[9] P. Kocher, “Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems,” in Proceedings of Advances in Cryptology-CRYPTO ’96. Springer-Verlag, 1996, pp. 104–113.
[10] P. Kocher, J. Jaffe, and B. Jun, “Introduction to differential power analysis and related attacks,” in http://www.cryptography.com/dpa/technical, 1998.
[11] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, “Power analysis attacks of modular exponentiation in smartcards,” in Proceedings of Workshop on Cryptographic Hardware and Embedded Systems. Springer-Verlag, August 1999, pp. 144–157.
[12] S. Tezuka, Uniform random numbers: theory and practice, Kluwer Academic Publishers, 1995
[13] R. David, Random Testing of Digital Circuits: Theory and Application, Dekker Inc., New York, 1998.
[14] Intel Platform Security Division, “The Intel Random Number Generator”, Intel Corporation, 1999.
[15] M. Jessa, “The period of Sequences Generated by Teni-Like Maps,” IEEE Trans. On CAS-part I, vol. 49, no. 1, Jan 2002.
[16] J. Huertas, J. Quintana, M. Valencia, “Chaos from Digital Circuits: Discrete Maps,” Int. Symp. on Networks, Systems and Signal Processing, pp. 391-395, Zagreb, 1989.
[17] R. Mita, G. Palumbo, S. Pennisi, M. Poli, “A Novel Pseudo Random Bit Generator for Cryptography Applications,” ICECS 2001, pp. 489-492, Dubrovnik (croatia), September 2002.
[18] T. Addabbo, M. Alioto, A. Fort, S. Rocchi, V. Vignoli, “Long Period Pseudo Random Bit Generators Derived from a Discretized Chaotic Maps” Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on, Vol. 2, pp 892- 895, 2005.
[19] A. F. Tenca and C¸ etin Kaya Ko¸c, “A scalable architecture for modular multiplication based on Montgomery’s algorithm,” IEEE Transactions on Computers, vol. 52, no. 9, pp. 1215–1221, September 2003.
[20] C. D. Walter, “Precise bounds for montgomery modular multiplication and some potentially insecure rsa moduli,” in Topics in Cryptology-CT-RSA 2002, B. reneel (editor), Lecture Notes in Computer Science, vol. 2271. San Jose, CA, USA: Springer Berlin / Heidelberg, 2002, pp. 30–39.
[21] K. s. Cho, J. H. Ryu, and J. D. Cho, “High-speed modular multiplication algorithm for rsa cryptosystem,” IEEE Industrial Electronics Society (IECON), vol. 1, no. 6, pp. 479-483, 2001.
[22] K. Mukaida, M. Takenaka, N. Torii, and S. Masui, “Design of high-speed and areaefficient montgomery modular multiplier for rsa algorithm,” in IEEE Symp. VLSI Circuits, 2004, pp. 320–323.
[23] C. P. Su, C. H. Wang, K. L. Cheng, C. T. Huang, and C. W. Wu, “Design and test of a scalable security processor,” in Proc. Asia and South Parific Design Automation Conf. (ASP-DAC), vol. 1, pp. 372-375, Jan 2005.
[24] Y.-C. Lin, “A RSA Crypto-core Baesd on Scalable Montgomery Multiplication with DPA and SPA Resistance,” Master’s thesis, National Chiao Tung University, 2008.
[25] Y.-L. Chen, “Design and implementation of reconfigurable rsa cryptosystems,” Master’s thesis, National Chiao Tung University, 2006.
[26] SP800-22, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications,” U.S. Department of commerce, NIST, 2008.
[27] http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
[28] Sung-Ming Yen and Chi-Sung Laih, "Fast Algorithms for the LUC Digital Signature Computation," IEE Proceedings: Computers and Digital Techniques, Vol.142, No.2, pp.165-169, March 1995.
[29] M. D. Shieh, J. H. Chen, H. H. Wu, and W. C. Lin, “A new modular exponentiation architecture for efficient design of rsa cryptosystem,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems archive, vol. 16, no. 9, pp. 1151–1161, September 2008.
[30] M. D. Shieh, and W. C. Lin, “Word-Based Montgomery Modular Multiplication Algorithm for Low-Latency Scalable Architectures,” IEEE Transactions on Computers, vol. 59, no. 8, pp. 1145–1151, August 2010.