簡易檢索 / 詳目顯示

研究生: 李庚儒
Li, Geng-Ru
論文名稱: 區塊Lanczos演算法應用於RSA
Block Lanczos Algorithm for RSA
指導教授: 黃柏嶧
Huang, Po-Yi
學位類別: 碩士
Master
系所名稱: 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年: 2021
畢業學年度: 109
語文別: 英文
論文頁數: 22
中文關鍵詞: RSAQuadratic SieveBlock Lanczos Standard Lanczos
外文關鍵詞: Block Lanczos , RSA, Quadratic Sieve, Standard Lanczos
相關次數: 點閱:102下載:7
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • RSA是一個是非對稱加密系統將內文加密後傳送經由解密後得知內文,當要破譯RSA可以使用其中一種演算法Quadratic sieve來將兩個質數拆解出來,當金鑰很大時使用Quadratic sieve需要解大矩陣。Standard Lanczos演算法可以解稀疏對稱大矩陣的空向量,但這個演算法使用於實數上, 而要解的大矩陣在 mod(2)的環境下運算所以經由推倒與假設,將Standard Lanczos經由推導與假設改變演算法結構並運算於GF(2)也就是Block Lanczos。

    RSA is an asymmetric cryptographic system, the system is easy to encrypt and decrypt but difficult to find the key. Quadratic sieve algorithm is a way to factor two multiply prime integers(RSA). When the primes are too large, we have to solve null vectors of an enormous sparse matrix. The Standard Lanczos algorithm can solve sparse symmetric matrix over R, Using framework of Standard Lanczos extend Block Lanczos. Block Lanczos can solve sparse symmetric matrix over GF(2).

    1 Introduction 1 2 Factoring Method 3 2.1 Quadratic Sieve 3 2.2 Quadratic Sieve Algorithm 4 2.3 General Number Field Sieve 5 3 Standard Lanczos 7 3.1 Lanczos Algorithm 7 3.2 Lanczos over R 9 4 Block Lanczos 11 4.1 Orthogonal Subspaces over GF(2) 11 4.2 Predigest Block Lanczos 14 4.3 Block Lanczos over GF(2) 16 4.4 Choosing Si and Wi Algorithm 19 5 Conclusion 20 References 22

    M. Briggs. (1998).An Introduction to the General Number Field Sieve

    Peter L. Montgomery (1995).A Block Lanczos Algorithm for Finding Dependencies. over GF(2)

    Laurence T. Yang, Li Xu, Sang-Soo Yeo, Sajid Hussain. (2010)An integrated parallel GNFS algorithmfor integer factorization based on Linbox Montgomery block Lanczos method over GF(2), Computersand Mathematics with Applications,338-346

    Pomerance C. (1985).The Quadratic Sieve Factoring Algorithm.169-182

    M.E. Briggs. (1998).An introduction to the general number field sieveVirginia Polytechnic Instituteand State University.

    C. Lanczos. (1952).Solutions of linread equations by minimized iterations

    Odlyzko A.M. (1985).Discrete logarithms in finite fields and their cryptographic significance. In:Beth T., Cot N., Ingemarsson I. (eds) Advances in Cryptology. EUROCRYPT 1984. Lecture Notes inComputer Science, vol 209. Springer, Berlin, Heidelberg.

    下載圖示 校內:立即公開
    校外:立即公開
    QR CODE