以General Number Field Sieve (GNFS) 程式實作分解大整數, 檢驗現今廣泛使用之公開金鑰密碼系統RSA的安全性

計畫名稱:以General Number Field Sieve (GNFS) 程式實作分解大整數, 檢驗現今廣泛使用之公開金鑰密碼系統RSA的安全性

所屬單位:數學系

研究團隊:數學/資訊/電機

計畫主持人:陳君明

資源需求:Compiler: xlc, Library: GMP, OpenMP

使用期間:2007/08~

研究主題:
以General Number Field Sieve (GNFS) 程式實作分解大整數, 檢驗現今廣泛使用之公開金鑰密碼系統RSA的安全性

研究內容概述:
GNFS演算法可分為四大步驟:
1. 多項式選取 (Polynomial Selection)
2. 篩法 (Sieving)
3. 矩陣化簡 (Matrix Reduction)
4. 開平方根 (Square Root)
其中前兩步驟可高度平行化, 適合在HP cluster執行. 第三步驟則適合在IBM p595或Cray等大型主機上執行. 目前已公開的最新分解紀錄為RSA-640, 由德國團隊以超級電腦與數百臺PC, 耗時半年完成. 網路上的公開原始程式碼GGNFS可分解至RSA-400, 我們以其為基礎, 研究演算法並改寫上萬行的程式. 目標為以合理時間與運算資源分解RSA-512, 迎頭趕上國際先進技術.

詳細計畫內容 研究成果 回到上一頁