回顧上面的密鑰生成步驟,一共出現六個數字:
> p
> q
> n
> φ(n)
> e
> d
這六個數字之中,公鑰用到了兩個(n和e),其余四個數字都是不公開的。其中最關鍵的是d,因為n和d組成了私鑰,一旦d泄漏,就等于私鑰泄漏。
那么,有無可能在已知n和e的情況下,推導出d?
> (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。
>
> (2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
>
> (3)n=pq。只有將n因數分解,才能算出p和q。
結論:如果n可以被因數分解,d就可以算出,也就意味著私鑰被破解。
可是,大整數的因數分解,是一件非常困難的事情。目前,除了暴力破解,還沒有發現別的有效方法。維基百科這樣寫道:
> "對極大整數做因數分解的難度決定了RSA算法的可靠性。換言之,對一極大整數做因數分解愈困難,RSA算法愈可靠。
>
> 假如有人找到一種快速因數分解的算法,那么RSA的可靠性就會極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止,世界上還沒有任何可靠的攻擊RSA算法的方式。
>
> 只要密鑰長度足夠長,用RSA加密的信息實際上是不能被解破的。"
舉例來說,你可以對3233進行因數分解(61×53),但是你沒法對下面這個整數進行因數分解。
> 12301866845301177551304949
> 58384962720772853569595334
> 79219732245215172640050726
> 36575187452021997864693899
> 56474942774063845925192557
> 32630345373154826850791702
> 61221429134616704292143116
> 02221240479274737794080665
> 351419597459856902143413
它等于這樣兩個質數的乘積:
> 33478071698956898786044169
> 84821269081770479498371376
> 85689124313889828837938780
> 02287614711652531743087737
> 814467999489
> ×
> 36746043666799590428244633
> 79962795263227915816434308
> 76426760322838157396665112
> 79233373417143396810270092
> 798736308917
事實上,這大概是人類已經分解的最大整數(232個十進制位,768個二進制位)。比它更大的因數分解,還沒有被報道過,因此目前被破解的最長RSA密鑰就是768位。