| 在RSA公鑰密碼系統中，每個使用者都擁有兩把鑰匙─公鑰與私鑰。公鑰公布給所有的人知道，私鑰則由自己秘密保存著，若甲方想要把訊息送給乙方且不想讓其他人知道訊息的內容，甲方可以用乙方的公鑰將訊息加密後送出，加密過的訊息只有擁有私鑰的人才能解開讀到真正的內容。在正常的情形下，只有乙方一人知道這把解密的鑰匙。 公鑰密碼系統的安全性在於幾乎無法由公鑰計算推導出私鑰，也就是靠這種計算不可行性( computational infeasibility)才得以保密。假如藉計算推導確實不易取得私鑰，那麼我們可以稱這系統是安全的。 RSA密碼系統就是利用大數分解相當困難的這個事實來製造公鑰與私鑰。因為大家公認分解一個大的數字是困難的，所以說RSA系統可說是相當安全的。 到底我們要取多大的數字才會讓RSA不可能被破解？八０年代初期，人們認為100位的數字便足夠安全，但現在的電腦已經有足夠的計算能力可以分解。1977年 RSA的三位發明者Rivest、Shamir、Adleman於Scientific American提出著名的129-digit RSA 挑戰題，預言需要四億億年才可分解出來。但在1994年，有人在Internet上用二次篩選分解法只花了八個月便完成這項工作。1996年四月更有人以十倍快的一般代數體篩選分解法，成功地解決130-digit RSA 挑戰題。現在，很多人是用155-digit數字來保護他們重要的資料。 最直接的大數分解法就是試除法(The trial division method)，即對整數n，用2, 3, …, 去試除，來分解大數。這個簡單的方法對20左右的數就要耗費很多時間。在四十年代電子計算機出現以前，儘管發明了許多大數分解的方法，但因需要手算，故即使十幾位數也需好幾天的時間，而對更大的數更是無能為力。隨著電子計算機的發明，人們開始利用這些歷史上留下來的方法並創造新的方法。到了七十年代隨著大數分解在密碼學上有了重大的價值，數論學家與計算機專家們已深入地研究這個問題，而且得到了許多有效的方法。目前著名的演算法有 1.Rho分解法(The rho factorization method) 2.因數基集分解法(The factor base factorization method) 3.連分數分解法(The continued fraction factorization method) 4.二次篩選分解法(The quadratic sieve factorization method) 5.p-1分解法(The p-1 factorization method) 6.橢圓曲線分解法(The elliptic curve factorization method) 7.代數體篩選分解法(The number field factorization method) |