使用蒙哥馬利次方梯和混沌亂數產生器的RSA密碼系統

An RSA Cryptosystem Based on Montgomery Powering Ladder and Chaos-based Random Number Generator

陳勇志(Yung-Chih Chen)

指導教授 ： 張錫嘉

國立交通大學/電機學院/電子工程系所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00170

摘要

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

關鍵字

RSA密碼系統 ； 蒙哥馬利次方梯 ； 混沌亂數產生器

並列摘要

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.

並列關鍵字

RSA cryptosystem ； Montgomery powering ladder ； Chaos-based random number generator

參考文獻

[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.

[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.

[15] M. Jessa, “The period of Sequences Generated by Teni-Like Maps,” IEEE Trans. On CAS-part I, vol. 49, no. 1, Jan 2002.