2) RSA算法舉例

下面通過一個例子說明RSA算法加密和解密的過程。 l、選擇兩個素數(shù)，p=4.7和q=61。

2、計算n=pq=47×61=2867。

3、計算≯(,z)=(p -l)(q -1)=46x 60 - 2760.

4、選擇e使其與鼬）= 2760互素且小于/(n)，這里選擇e=1223。 5、確定攤芝得de=l mod 2760，d-167。

通過以上計算可以得到RSA的公鑰為(e，n}={1223，2867)，私鑰{d，n}={167，2867}。

假設輸入明文“RSA ALGORITHM”，把明文用兩位二進制數(shù)字表示，空格=00，

A=Ol，B=02，…，2=26，把明文表示成一串十進制數(shù)的數(shù)據(jù)塊，每塊的值不超過11-1，得到：1819 0100 0112 0715 1809 2008 1300。

利用加密變換，對每一數(shù)據(jù)塊進行加密產(chǎn)生相應的密文塊，如C =18191223 mod 2867=18191024. 1819128. 181964. 18194. 18192. 1819'mod2867 = 2756

類似的，經(jīng)過加密變換后可以得到整個密文： 2756 2001 0542 0669 2347 0408 1815

解密過程對每一密文塊計算M= Cd modn，此處不再贅述。 3) RSA的安全性

密碼分析者攻擊RSA算法的關(guān)鍵點在于如何分解l。若分解成功使n=pq，則可以算出中(n)：（p-1）（q-l），然后由公開的e，解出秘密的d。攻破RSA與分解n是多項式等價

的。因此產(chǎn)生密鑰時，需要考慮兩個大素數(shù)p、q的選取，以及e的選取和d的計算。

n=pq在體制中是公開的，因此為了防止敵手通過窮舉搜索發(fā)現(xiàn)p、q，這兩個素數(shù)是在一 個足夠大的整數(shù)集合中選取的大數(shù)。尋找大素數(shù)時一般是先隨機選取一個大的奇數(shù)，然后用索性檢驗算法檢驗這一奇數(shù)是否為素數(shù)，如果不是則選取另一個大奇數(shù)，重復這一過程，直到找到素數(shù)為止。RSA算法從提出后，密碼分析學家對其進行了大量抗攻擊性分析。其中：

80年代末，Rivest、Shamir和Adleman找到了一個129位數(shù)(428bits)的兩個素數(shù)的乘積，稱為RSA-129，設計了一套密鑰向世界挑戰(zhàn)。

1994年3月，由Lenstra領(lǐng)導的一組數(shù)學家及世界各地600多個愛好者使用了1600臺機器，

花費了8個月的時間，他們就分解出了這個數(shù)的兩個素數(shù)因子，其中一個長64位，另一個長65位。

1999年，阿姆斯特丹的國家數(shù)學與計算機科學研究所( CWI)屬下的一個國際密碼研究小組宣布，他們在破譯RSA公鑰密碼系統(tǒng)使用的155位RSA密鑰的競賽中榮獲冠軍，他們使用了一臺克雷900-16超級計算機、300臺個人計算機以及專門設計的軟件。2009年12月，RSA一 768被分解（232位的密鑰）。