跳到主要內容

臺灣博碩士論文加值系統

(3.236.110.106) 您好!臺灣時間:2021/07/27 19:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:金家豪
研究生(外文):Chia-Hao Chin
論文名稱:通用型數域篩選因數分解法之參數探討
論文名稱(外文):A study of parameter tuning for General Number Field Sieve
指導教授:顏嵩銘顏嵩銘引用關係
指導教授(外文):Sung-Ming Yen
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程學系碩士在職專班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:58
中文關鍵詞:整數分解數域篩選因數分解法通用型數域篩選因數分解法
外文關鍵詞:General Number Field SieveFactorizationNumber Field Sieve
相關次數:
  • 被引用被引用:1
  • 點閱點閱:214
  • 評分評分:
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
由於網際網路的興起,許多重要的資料開始經由網路傳輸,但如何保護傳輸資料不被他人竊取,便成為一個相當重要的議題。傳統的對稱式加密系統已不能滿足網際網路環境的需求,這使得公開金鑰密碼系統的需求日增。目前主流的公開金鑰密碼系統為 RSA,而 RSA 的理論安全性是建構在因數分解的難度上。因此, RSA 中的大數到底需要多大才算安全,自然就成為 RSA 系統安全的研究重點。到目前為止,分解 100 位數以上的 RSA 數最有效率的分解法為通用型數域篩選因式分解法。在本篇論文中,我們在一台 Linux Server 上實作該分解法,並藉由觀察參數調整的結果,以作為改進分解效能的建議。
With the explosive growth rate of the Internet, there are more and more data transferred by Internet. Therefore, the ability to conduct electronic communications and transactions securely has become an issue of vital concern. The public key cryptosystem arises because the conventional secret-key cryptosystem can not meet the needs of distribution application. RSA is a very popular public key cryptosystem and its security relies on the difficulty of factoring a large number. Because of the popularity of this algorithm, much research has gone into this problem. As we know, the General Number Field Sieve(GNFS) is the asymptotically fastest factoring algorithm for large integers. In this thesis, we will implement this algorithm on a Linux server and discuss how to tune its parameters to get better performance.
目 次

第1章 緒論...............................................................1
1.1 前言..............................................................1
1.2 研究動機..........................................................1
1.3 論文架構..........................................................3

第2章 RSA密碼系統及相關數論介紹..........................................4
2.1 RSA 密碼系統簡介..................................................4
2.2 基礎數論..........................................................7
2.2.1 二次剩餘(Quadratic Residue)..................................7
2.2.2 雷建德符號(Legendre Symbol)..................................8
2.2.3 加寇比符號(Jacobi Symbol)....................................8
2.2.4 Smooth Number................................................9

第3章 因數相關分解演算法................................................10
3.1 試除法(Trial division)...........................................10
3.2 費馬因數分解法(Fermat's factorization method)....................11
3.3 Pollard's rho 因數分解法.........................................14
3.4 Pollard's P-1 因數分解法.........................................16
3.5 橢圓曲線因數分解法...............................................17

第4章 因數無關分解演算法................................................20
4.1 Dixon因數分解法(Dixon's factorization method)....................20
4.2 連分數因數分解法(Continued fraction factorization method)........22
4.3 二次篩選因數分解法(Quadratic Sieve)..............................27
4.4 多多項式二次篩選因數分解法(Multiple Polynomial Quadratic Sieve)..33
4.5 數域篩選因數分解法(Number Field Sieve)...........................37

第5章 通用型數域篩選因數分解法(General Number Field Sieve)..............38
5.1 選取多項式.......................................................39
5.2 篩選數對.........................................................40
5.2.1 選取有理數分解基底(Rational Factor Base)....................41
5.2.2 選取代數數分解基底(Algebraic Factor Base)...................41
5.2.3 選取二次特徵基底(Quadratic Character Base)..................42
5.2.4 檢驗數對....................................................43
5.3 組成完全平方數...................................................45
5.4 計算平方根.......................................................47

第6章 實驗結果與分析....................................................51
6.1 實作環境.........................................................51
6.1.1 硬體環境.......................................................51
6.1.2 軟體環境.......................................................51
6.2 系統架構.........................................................51
6.3 實驗參數.........................................................53
6.4 實驗結果.........................................................53
6.5 數據分析.........................................................55

第7章 結論..............................................................56
[1] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the theory of NP-Completeness, W.H. freeman and Co., 1979.
[2] R.P. Brent, Primality Testing and Integer Factorization, Proceeding of Australian Academy of Science Annual General Meeting Symposium on the Role of Mathematics in Science, Canberra, 1991, 14-26
[3] Song Y. Yan, Number Theory for Computing, 2nd ed., Springer-Verlag, Berlin, 2002
[4] Hans Riesel, Prime numbers and computer methods for factorization, Birkh�黷ser, Boston 1985, 2nd ed. 1994
[5] David M. Bressoud, Factorization and primality testing, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1989.
[6] J. M. Pollard, A Monte Carlo method for factorization, BIT. V15(3), 1975 , pp. 331-334
[7] J. M. Pollard, Theorems on factorization and primality testing, Proc. Camb. Phil. Soc., v76(2) , 1974 , pp 521-528
[8] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Math., v126(3), 1987, pp.649-673
[9] J. Dixon, Asymptotically fast factorization of integers, Mathematics of computation, vol. 36, no. 153, pp. 255-260, 1981
[10] M. A. Morrison, J. Brillhard, A method of factoring and factorization of F7, Math of Comp., v29, 1975, pp. 183-205
[11] C. Pomerace, The quadratic sieve factoring algorithm, Advances in Cryptology: Proceedings of EUROCRYPT 84(1984), pp. 169-182.
[12] R.D. Silverman, The multiple polynomial Quadratic Sieve, Mathematics of Computation 48 (1987), pp329- 339
[13] Brandt Kurowski, The Multiple Polynomial Quadratic Sieve, http://brandt.kurowski.net/projects/mpqs/paper/mpqs.ps
[14] P. L. Montgomery, A survey of modern integer factorization algorithms, CWI Quarterly 7 (1994), pp337-366.
[15] Matthew E. Briggs, An introduction to the general number field sieve, M.S. Thesis, Virginia Polytechnic Institute, Blacksburg, Virginia, 1998.
[16] Michael Case, A Beginner's Guide To The General Number Field Sieve, http://islab.oregonstate.edu/koc/ece575/03Project/Case/paper.pdf
[17] David Stephenson, Factoring Very Large Numbers, http://citeseer.nj.nec.com/stephenson96factoring.html
[18] Joel Dreibelbis, Implementing the General Number Field Sieve, http://www.cs.rit.edu/~jdd5747/msPaper.ps.gz
[19] Franke, J. , RSA576, Privately circulated email reposted to primenumbers Yahoo! Group, http://groups.yahoo.com/group/primenumbers/message/14113
[20] Eric W. Weisstein, RSA Number, From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RSANumber.html
[21] 賴溪松、韓亮、張真誠,近代密碼學及其應用,松崗書局,2000
[22] 趙文敏,數論淺談,協進,1985
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top