七、RSA算法的可靠性

回顧上面的密鑰生成步驟，一共出現(xiàn)六個(gè)數(shù)字：

　　p
　　q
　　n
　　φ(n)
　　e
　　d

這六個(gè)數(shù)字之中，公鑰用到了兩個(gè)（n和e），其余四個(gè)數(shù)字都是不公開的。其中最關(guān)鍵的是d，因?yàn)閚和d組成了私鑰，一旦d泄漏，就等于私鑰泄漏。

那么，有無可能在已知n和e的情況下，推導(dǎo)出d？

　?。?）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

　?。?）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

　?。?）n=pq。只有將n因數(shù)分解，才能算出p和q。

結(jié)論：如果n可以被因數(shù)分解，d就可以算出，也就意味著私鑰被破解。

可是，大整數(shù)的因數(shù)分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發(fā)現(xiàn)別的有效方法。維基百科這樣寫道：

　　"對極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。

　　假如有人找到一種快速因數(shù)分解的算法，那么RSA的可靠性就會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。

　　只要密鑰長度足夠長，用RSA加密的信息實(shí)際上是不能被解破的。"

舉例來說，你可以對3233進(jìn)行因數(shù)分解（61×53），但是你沒法對下面這個(gè)整數(shù)進(jìn)行因數(shù)分解。

　　12301866845301177551304949
　　58384962720772853569595334
　　79219732245215172640050726
　　36575187452021997864693899
　　56474942774063845925192557
　　32630345373154826850791702
　　61221429134616704292143116
　　02221240479274737794080665
　　351419597459856902143413

它等于這樣兩個(gè)質(zhì)數(shù)的乘積：

　　33478071698956898786044169
　　84821269081770479498371376
　　85689124313889828837938780
　　02287614711652531743087737
　　814467999489
　　　　×
　　36746043666799590428244633
　　79962795263227915816434308
　　76426760322838157396665112
　　79233373417143396810270092
　　798736308917

事實(shí)上，這大概是人類已經(jīng)分解的最大整數(shù)（232個(gè)十進(jìn)制位，768個(gè)二進(jìn)制位）。比它更大的因數(shù)分解，還沒有被報(bào)道過，因此目前被破解的最長RSA密鑰就是768位。