平行RSA大數分解

Abstract

目前很多的密碼加密方法都是採用RSA演算法，其安全度是基於對大數作質因數分解的困難度。所有的正整數都可以用唯一的質因數乘積來表示，而且可以很容易證明這樣的質因數分解存在。給定二個以上的質數可以很容易的算出其乘積，但反之，若給定一個大的正整數卻很難將其質因數分解。目前被認為對於129位數以下的大數，最有效率的大數分解方法是二次篩選分解法，而大於130位數以上的大數則以代數體篩選分解法的分解效率較好，基於硬體設備及時間等因素考量，我們以100位數左右的大數為目標，使用二次篩選分解法來分解大數。本論文將實作雙質數多多項式二次篩選分解法，並使用交通大學資訊工程學系英特爾實驗室的設備，設計分散式主從架構環境來完成RSA大數分解。

Many real-world cryptographic applications are based in part on the RSA algorithm, whose security lies in the intractability of factoring large integers. Every positive integer is expressible as a product of prime numbers, in a unique way. Although it is easy to prove that this factorization exists, it is believed very hard to factor in arbitrary integer. It is well known that the best algorithm to factor 129 digits integer is Multiple Polynomial Quadratic Sieve(MPQS), but for more large integer, the Number Field Sieve(NFS) is another best choice. Considering the hardware and time consuming, we use MPQS to factor the integers about 100 digits. The paper will implement the MPQS and design a client-server environment in the IntelLab of CSIE to factor RSA integers.