2) RSA算法舉例

下面通過(guò)一個(gè)例子說(shuō)明RSA算法加密和解密的過(guò)程。 l、選擇兩個(gè)素?cái)?shù)，p=4.7和q=61。

2、計(jì)算n=pq=47×61=2867。

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

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

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

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

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

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

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

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

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

的。因此產(chǎn)生密鑰時(shí)，需要考慮兩個(gè)大素?cái)?shù)p、q的選取，以及e的選取和d的計(jì)算。

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

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

1994年3月，由Lenstra領(lǐng)導(dǎo)的一組數(shù)學(xué)家及世界各地600多個(gè)愛(ài)好者使用了1600臺(tái)機(jī)器，

花費(fèi)了8個(gè)月的時(shí)間，他們就分解出了這個(gè)數(shù)的兩個(gè)素?cái)?shù)因子，其中一個(gè)長(zhǎng)64位，另一個(gè)長(zhǎng)65位。

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