RAS算法是基于數(shù)論原理的公開密鑰密碼體制，是目前最有效的公開密鑰加密算法之一，RAS算法的安全依賴于大數(shù)分解的困難性，已廣泛地應(yīng)用于網(wǎng)絡(luò)和數(shù)據(jù)安全性系統(tǒng)的加密、數(shù)字簽名和身份認證等需許多領(lǐng)域。

RAS算法的安全性依賴于大數(shù)分解，如果破譯分析者能夠分解大數(shù)n，那么做多只要試探2次就你按構(gòu)造本算法相同的方法求出解密密鑰，從而破譯出明文。但大整數(shù)n的素因子分解問題是一個極為困難的問題。目前已知的做好的算法需要進行?e^{√1nn1n(1nn)}次算數(shù)運算。如果用一臺每秒10⁸次運算的計算機來分解一個160位的十進制數(shù)，所需時間（年）有如下的計算：

由以上計算可知，增加n的位數(shù)，分解他所需時間將更長，這就大大地提高了RAS的安全性。雖然并沒有從理論上證明破譯RAS的難度與大數(shù)分解難度是等價的，但從提出到現(xiàn)在已近30年，RAS經(jīng)歷了各種攻擊的考驗。

關(guān)于素數(shù)的選擇

攻擊者破譯RAS算法的步驟為：

1、分解n，求出p、q
2、由Φ(n)=(p-1)(q-1),求出Φ(n)。
3、由ed=1modΦ（n）,求出d。

為了更好地防范分解，在選擇p、q時，一是注意p和q在位數(shù)上要相差極為數(shù)字；二是(p-1)和(q-1)都應(yīng)含有大的素數(shù)因子，以增加攻擊者猜算出Φ(n)的困難性；三是gcd(p-1，q-1)應(yīng)當小。滿足這些條件的素數(shù)稱作安全素數(shù)。

實際上，所謂攻擊者破譯RAS算法，指的是由已知的e和n來推算d和Φ(n)。為了密碼算法的安全，必須使p*q乘積的結(jié)果盡量大，這又使計算量將呈指數(shù)增長，算法實現(xiàn)的難度增大，實用性降低。RAS公開密鑰算法的矛盾難點就在于計算存儲容量和計算運行速度，位數(shù)減少，則速度變快，難度降低，安全性變差。

事實上，所有的應(yīng)用算法都是基于這樣一個合理的假設(shè)，當破譯一個算法的花費遠大于它的收益時，這種算法就是安全的。

ice

收藏 海報分享