臺灣博碩士論文加值系統

公開金鑰密碼系統中，RSA被認為具有安全、實用性之演算法，其產生金鑰方式為秘密挑選兩質數p與q，相乘得到一可公開的大數n，若成功分解n、將其還原為p、q，此謂大數分解，RSA的安全性即建立於大數分解的困難度上。大數分解演算法可分為兩類：運算執行時間主要與分解對象n大小有關的演算法，如：MPQS；運算執行時間主要與n之因子p大小有關的演算法，橢圓曲線屬於此類演算法中被視為較佳者，亦為本研究的著眼所在。
現行的大數分解工具，大部分執行平台限於Linux，操作方式也以命令列模式為主，不符合目前為大多數使用者所習於的Windows圖形環境。因此，本研究首先設計一套適用於Windows作業系統、具有圖形化介面的大數分解工具，內建多演算法。
另一方面，鑑於大數分解的複雜度至今仍屬於指數問題，非單一電腦即可破解，本研究利用網際網路的發達及連結性，利用Cluster架構設計出具備主控台與多節點的分散式大數分解程式，主控台電腦給予圖形化介面設計，並負責指令的發送及結果的顯示，節點電腦則執行GMP-ECM此大數分解軟體之指令。

Among public key cryptosystems, RSA is considered a secure and practical cryptosystem. The way to generate keys in RSA is to pick two primes, p and q, and to multiply p by q to produce n which is public while p and q are private. Factoring n or finding the factors of n is called integer factorization. The security of RSA depends on the difficulty of integer factorization.
Integer factorization algorithms can be divided into two categories. One is that the complexity depends on the size of n, and the other is that the complexity depends on the size of the factor found; ECM, which is highlighted in this thesis, is the best known method in the second category.
Most of current factorization tools are console programs on the Linux environment, which does not correspond to the Windows graphical environment accepted by most users. Therefore, two factorization tools are implemented in this thesis. GFactor, the first one, is a GUI tool with multiple factorization algorithms on the Windows and Linux platform.
Since the integer factorization is the problem of exponential complexity, a big number is hardly factored by any individual computer. Thus, the second tool of a distributed system with cluster architecture—ECMcontroller is provided. ECMcontroller sends commands to all nodes; nodes perform GMP-ECM command respectively and return results back to the controller as if just one computer were at work.

Chapter 1. Introduction 1
1.1. Background and Motivation 2
1.2. Objectives 3
Chapter 2. Related Works 5
2.1. RSA 5
2.2. Integer Factorization Algorithms 6
2.3. Integer Factorization Tools 14
Chapter 3. Design of the Tools 23
3.1. GFactor 23
3.2. ECMcontroller 33
Chapter 4. Imeplementation of the Tools 43
4.1. GFactor 43
4.2. ECMcontroller 54
Chapter 5. Conclusions and Future Works 61
5.1. Conclusions 61
5.2. Future Works 61
Bibliography 63

Aoki, K. (2006). R311 Is Factored by ECM. Symposium on Cryptography and Information Security, Hiroshima, Japan.
Aoki, K., Ueda, H., Kida, Y., Shimoyama, T., Sonoda, Y. (2004). A trial of GNFS implementation (Part I) — Summary. Symposium on Cryptography and Information Security, Sendai, Japan.
Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. American Mathematical Society (AMS), 46(2), 203-213.
Brent, Richard. P. (2000). Recent Progress and Prospects for Integer Factorisation Algorithms (pp.3-22). LNCS 1858. Springer-Verlag.
Bressoud, D. M. (1989). Factorization and Primality Testing. New York: Springer-Verlag.
Dixon, B., Lenstra, A. K. (1992). Massively parallel elliptic curve factoring (pp. 183-193). LNCS 658. Springer-Verlag.
Glade. (1998). Retrieved September 30, 2005, from the World Wide Web: http://glade.gnome.org/
GMP-ECM. (n.d.). Retrieved August 17, 2005, from the World Wide Web: http://www.komite.net/laurent/soft/ecm/ecm-6.0.1.html
GTK+. (n.d.). Retrieved September 23, 2005, from the World Wide Web: http://www.gtk.org/
MIRACL. (2000). Retrieved July 18, 2005, from the World Wide Web: http://indigo.ie/~mscott/
MinGW. (2004). Retrieved September 24, 2005, from the World Wide Web: http://www.mingw.org/
MSYS. (2004). Retrieved September 24, 2005, from the World Wide Web: http://www.mingw.org/
Landquist, Eric. (2001). The Quadratic Sieve Factoring Algorithm. MATH 488: Cryptographic Algorithms.
Lenstra, A. K., Manasse, M. S. (1991). Factoring with two large primes(Extended Abstract) (pp. 72-82). LNCS 473. New York: Springer-Verlag.
Lenstra, H. W. (1987). Factoring integers with elliptic curves. Annals of mathematics 126.
Silvermanm, R. D. (1991). Massively distributed computing and factoring large integers. Communications of the ACM, 34(11), 95-103.
Stallings, W. (2004). Cryptography and Network Security: Principles and Practices (3rd ed.). Upper Saddle River, NJ: Prentice Hall.
The ECMNET Project. (1999). Retrieved August 17, 2005, from the World Wide Web: http://www.loria.fr/~zimmerma/records/ecmnet.html
Weisstein, Eric W. (n.d.). Trial Division. Retrieved October 20, 2005, from the World Wide Web: http://mathworld.wolfram.com/ TrialDivision.html