2) RSA算法舉例

下面通過一個例子說明RSA算法加密和解密的過程。 l、選擇兩個素數，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”，把明文用兩位二進制數字表示，空格=00，

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

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

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

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

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

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

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

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

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

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

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