密碼學(xué) RSA密碼體制

RSA算法概述

RSA加密算法于1977年由美國麻省理工學(xué)院的Ronal Rivest，Adi Shamir和Len Adleman三位年輕教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名為RSA算法。這三位科學(xué)家榮獲2002年度圖靈獎，以表彰他們在算法方面的突出貢獻。該算法利用了數(shù)論領(lǐng)域的一個事實，那就是雖然把兩個大質(zhì)數(shù)相乘生成一個合數(shù)是件十分容易的事情，但要把一個合數(shù)分解為兩個質(zhì)數(shù)的乘積卻十分困難。合數(shù)分解問題目前仍然是數(shù)學(xué)領(lǐng)域尚未解決的一大難題，至今沒有任何高效的分解方法。它無須收發(fā)雙方同時參與加密過程，既可以用于保密也可以用于簽名，因而非常適合于電子郵件系統(tǒng)的加密，互連網(wǎng)和信用卡安全系統(tǒng)。

公私匙生成算法

RSA的公私鑰生成算法十分簡單，可以分為五步：

（1）隨機地選擇兩個大素數(shù)p和q，而且保密；

（2）計算n=pq，將n公開；

（3）計算ф(n)=(p-1)(q-1)，對ф(n)保密；

（4）隨機地選擇一個正整數(shù)e，1<e<ф(n)且(e，ф(n))=1，將e公開；

（5）根據(jù)ed=1 mod ф(n)，求出d，并對d保密。

公開密鑰是由(e，n)構(gòu)成，私有密鑰由(d，n)構(gòu)成。

加密算法

實體B的操作如下：

（1）得到實體A的真實公鑰（e，n）；

（2）把消息表示成整數(shù)m，0＜m≤n－1；

（3）使用平方－乘積算法，計算C = Ek(m) = me mod n；

（4）將密文C發(fā)送給實體A。

解密算法

實體A接收到密文C，使用自己的私鑰d計算m = Dk（C） = Cd mod n。 我們選擇p=3，q=11，得到n=33，ф(n)=(p-1)(q-1)=2×10=20。由于7和20互質(zhì)，故設(shè)e=7。對于所選的e=7，解方程7×d=1 mod 20，可以得到d=3。因此公鑰為(7，33)，私鑰為(3，33)。 在我們的例子中，由于所選的p和q太小，破譯當(dāng)然很容易，我們的例子只是用來說明此算法的原理。對于明文SUZANNE，RSA的加密和解密過程如下表所示。