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

RSA算法概述

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

公私匙生成算法

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

（1）隨機(jī)地選擇兩個(gè)大素?cái)?shù)p和q，而且保密；

（2）計(jì)算n=pq，將n公開；

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

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

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

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

加密算法

實(shí)體B的操作如下：

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

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

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

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

解密算法

實(shí)體A接收到密文C，使用自己的私鑰d計(jì)算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。對(duì)于所選的e=7，解方程7×d=1 mod 20，可以得到d=3。因此公鑰為(7，33)，私鑰為(3，33)。 在我們的例子中，由于所選的p和q太小，破譯當(dāng)然很容易，我們的例子只是用來(lái)說(shuō)明此算法的原理。對(duì)于明文SUZANNE，RSA的加密和解密過(guò)程如下表所示。