跳到主要內容

臺灣博碩士論文加值系統

(44.200.27.215) 您好!臺灣時間:2024/04/15 04:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳牧恩
研究生(外文):Mu- En Wu
論文名稱:短CRT指數RSA密碼系統之研究
論文名稱(外文):A Study of RSA with Small CRT-Exponent
指導教授:傅恆霖 孫宏民
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學系所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
畢業學年度:93
語文別:中文
論文頁數:56
中文關鍵詞:RSA密碼系統CRT解密短CRT指數中國餘式定理連分數攻擊格子點攻擊
外文關鍵詞:RSA cryptosystemCRT decryptionsmall CRT-exponentChinese Remainder Theoremcontinuous fraction attacklattice attack
相關次數:
  • 被引用被引用:0
  • 點閱點閱:373
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
RSA是目前最被為廣泛使用的公開金鑰密碼系統,此密碼系統主要是植基於大數因數分解的困難度上,所以具有相當高的安全性。然而,由於其加密與解密的過程,需要做大指數模乘法的運算,這使得在使用RSA密碼系統時,加解密花費過長的時間成為其最大的缺點。因此,如何改善RSA加密與解密的運算速度,一直是許多密碼學家研究的重要問題。一般的方法都是選擇較短位元數的公鑰或私鑰指數。可惜的是,在傳統的RSA演算法裡,並不能同時選擇短指數的公鑰與私鑰,兩者只能取其一。1982年,Quisquater和Couvreur提出一種快速RSA解密的辯讀方法,這樣的技巧主要是基於中國餘式定理(CRT),我們稱之為CRT解密。其解密速度比傳統RSA密碼系統的解密速度約快了四倍。隨後在1990年,Wiener建議可以使用基於短CRT指數作解密的RSA密碼系統,我們稱之為短CRT指數RSA密碼系統。CRT指數即私密金鑰指數d模掉p-1 或q-1 後的餘數。而這樣的技巧可以更加提升解密的速度,且能防止短私鑰指數的攻擊;但相對的卻不能控制公開金鑰指數的長度,反而使得加密的時間變得較費時。

有鑑於之前的發展,本論文首先提出在CRT指數被洩漏情況下的三種攻擊方法。另一方面,本論文欲利用歐幾里得演算法,設計新的短CRT指數RSA密碼系統。在我們的密碼系統下,加密可比Wiener所提出的短CRT指數RSA密碼系統快了一倍,而解密仍然是利用短CRT指數的特性作解密動作。在參數方面,我們的RSA模數p跟q分別為平衡狀態的512位元、公開金鑰指數e為512位元、私鑰的CRT指數為160位元。我們並將所提出的密碼系統與傳統的RSA密碼系統作比較,包括加密與解密所使用的模乘法數,加密與解密所花費的單位時間估計等等…。另外,我們並分析目前短指數攻擊法及短CRT指數攻擊法對其所造成的安全性問題。
第一章 導論 1
1.1 前言 1
1.2 研究動機與目的 4
1.3 論文編寫方式 5
第二章 RSA介紹 6
2.1 公開金鑰密碼系統與RSA的起源 6
2.2 RSA密碼系統介紹 6
2.2.1 背景知識: 6
2.2.2 RSA演算法: 7
2.2.3 參數選擇與安全性分析: 9
2.3 RSA密碼系統的相關發展 11
2.3.1 RSA密碼系統的數位簽章: 11
2.3.2 CRT解密: 12
2.3.3 Wiener建議的短CRT指數RSA密碼系統: 14
第三章 RSA密碼系統上的攻擊 16
3.1 因數分解 16
3.2 短指數的RSA攻擊 17
3.2.1 連分數攻擊: 17
3.2.2 Boneh和Durfee的格子點攻擊(Lattice attack): 20
3.3 不平衡模數底下的短CRT指數攻擊 26
3.3.1 模數p的方法: 27
3.3.2 模數e的方法: 28
第四章 短CRT指數的選擇分析 30
4.1 短CRT指數的下界限制 30
4.2 洩漏單一短CRT指數的攻擊方法 32
4.2.1 指數暴力攻擊法: 32
4.2.2 因數分解攻擊法: 32
4.2.3 平滑數(smooth number)的機率估計: 33
4.3 洩漏兩個CRT指數的攻擊方法 34
第五章 新的短CRT指數RSA密碼系統 36
5.1 密碼系統的設計與分析 36
5.1.1 建構方法流程說明: 37
5.1.2 簡單範例: 38
5.2 安全性分析 39
5.2.1 連分數攻擊和格子點攻擊: 40
5.2.2 短CRT指數的格子點攻擊: 41
5.2.3 立方攻擊: 41
5.3 複雜度分析 42
5.3.1 建構方法步驟五的機率分析: 42
5.3.2 指數乘法的計算: 44
5.3.3 加密與解密的乘法數: 45
5.4 比較相關的RSA密碼系統 45
第六章 結論與未來發展 49
參考文獻: 52
附錄 A:新的短CRT指數RSA密碼系統之實例 56
[1] D. Boneh, R. Venkatesan, “Breaking RSA may not be equivalent to factoring. in Proceedings Eurocrypt '98, 1998, LNCS, Vol. 1233, Springer-Verlag, pp. 59-71.

[2] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private expo-nent ,” EUROCRYPT’99, 1999, LNCS 1592, Sprin- ger-Verlag, pp. 1-11.

[3] D. Boneh, “Twenty Years Attacks on the RSA Cryptosystem,” No-tices of the American Mathematical Society, 1999, vol. 46:2, pp. 203-213.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Intro-duction to Algorithm-Chapter31,” McGraw-hill Book Company.

[5] D. Coppersmith, “Finding a small root of a univariate modular equation,” in Proceedings of EUROCRYPT’96, 1996, LNCS 1070, Springer-Verlag, pp. 155-165.

[6] D.Coppersmith, M. Franklin, J. Patarin, and M. Reiter, “Low-Exponent RSA with related message. In EUROCRYPT ’96, 1996, LNCS 1070, Springer-Verlag, pp. 1-9.

[7] D. Coppersmith, “Small solutions to polynomial equations, and low exponent RSA vulnerabilities,” Journal of Cryptology, 1997, vol. 10, pp.233-260, 1997.

[8] C. Coupé, P. Nguyen, and J. Stern, “The Effectiveness of Lattice Attacks Against Low-Exponent RSA,” Public Key Cryptogra-phy’99.

[9] R. Crandall and C. Pomerance, Prime numbers: a computational perspective, Springer-Verlag, New York, 2001.

[10] W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Transaction on Information Theory, 1976, Vol.IT-22, No.6, pp. 644-654, Nov.

[11] G. Durfee, P. Q. Nguyen, “Cryptanalysis of the RSA Schemes with Short Secret Exponent form Asiacrypt ’99,” in Proceedings of Asia-crypt '00, 2000, LNCS, IACR, Springer-Verlag, Berlin, pp. 1-11.

[12] J. Hasted, “On Using RSA with Low Exponent in a Public Key Network,” in Proceedings of CRYPTO’85, 1986, Springer-Verlag, pp. 403-408.

[13] N. Howgrave-Graham, “Finding small roots of univariate modular equations revisited. in proceedings Cryptography and Coding, 1997, LNCS, vol. 1355, Springer-Verlag, pp. 131-142.

[14] B. S. Kaliski and M. Robshaw, “Secure use of RSA,” CRYP-TOBYTES, 1995, vol. 1 (3), pp. 7-13.

[15] A. Lenstra, H. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients.” Mathematische Annalen, 1982, vol. 261, pp. 515-534.

[16] L. Lovász, “An algorithmic theory of numbers, graphs, and convex-ity,” SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, 1986, vol. 50.

[17] H. W. Lenstra, “Factoring integers with elliptic curves,” Annals of Mathematiche, 1987, vol. 126, pp. 649-673.

[18] A. K. Lenstra and H. W. Lenstra, “The development of the number field sieve,” Lecture Notes in Mathematics, 1991 vol. 1554, Springer.

[19] A. J. Menezes, P.C. van Oorschot, and S. A Vanstone, “Handbook of applied Cryptography,” CRC Press, 1996.

[20] G. J. Miburn, “The Feynman Processor: Quantum Entanglement and the Computing Revolution,” Allen and Unwin Pty Ltd, 1998, Aust- ralia.

[21] A. May, “Cryptanalysis of Unbalanced RSA with Small CRT - Ex-ponent,” in Proceedings of Crypto’02, 2002, LNCS 2442, pp.242-256.

[22] I. Niven, H. S. Zuckerman, “An Introduction to the Theory of Num-ber,” John Wiley and Sons Inc.

[23] J. J. Quisquater, C. Couvreur, “Fast decipherment algorithm for RSA public key cryptosystem,” Electronic Letters, 1982, vol. 18, pp. 905-907.

[24] R. Rivest, A. Shamir and L. Aldeman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communica-tions of the ACM, 1978, Vol.21, No.2, pp. 120-126.

[25] R. Rivest and R. D. Silverman, “Are ‘strong’ primes needed for RSA,” the 1997 RSA Laboratories Seminar Series, Seminars Pro-ceedings, 1997.

[26] P. W. Shor, “Algorithms for Quantum Computation: Discrete Loga-rithms and Factoring,” IEEE Computer Society Press, Santa Fe, NM, November 20-22, 1994, pp. 124-134.

[27] A. Shamir, “RSA for paranoids,” CryptoBytes, Vol. 1, 1995, pp. 1, 3-4.

[28] H.-M. Sun, W.-C. Yang and C.-S. Laih., “On the Design of RSA with Short Secret Exponent,” in Proceedings of Asiacrypt '99, 1999, LNCS 1716, pp. 150-164.

[29] T. Takagi, “Fast RSA-Type Cryptosystem Modulo in Advances in Cryptography,” in Proceedings of CRYPTO 1998, 1998, LNCS 1462, pp. 318-326.

[30] T. Takagi, “Fast RSA-Type Cryptosystems Using N-Adic Expan-sion in Advances in Cryptography,” in Proceedings of CRYPTO 1997, 1997, LNCS 1294, pp. 372-384.

[31] E. Verheul and H. van Tilborg, “Cryptanalysis of less short RSA secret exponents,” Applicable Algebra in Engineering, Communica-tion and Computing, Springer-Verlag, Vol. 8, 1997, pp. 425-435.

[32] M. J. Wiener, “Cryptanalysis of short RSA secret exponents,” IEEE Transactions on information Theory, 1990, IT-36, pp. 553-558.

[33] 華羅更, “數論導引-第五章 素數分佈之概況;第十章 漸進法與連分數,”凡異出版社,

[34] D. Boneh and H. Shacham, “Fast Varients of RSA,” CryptoBytes, 2002, Vol 5, No. 1, Springer 2002.

[35] M. Ciet, F. Short, F. Laguillaumie and J-J Quiaquater, “Short Pri-vate Exponent Attacks on Fast Varient of RSA,” UCL Crypto Group Technical Series, 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top