兩年后，Ronald L.Rivest，Adi Shamir和Leon：刪Adleman提出了一個(gè)滿足上述要求的算法［Rivest 78］。這個(gè)算法被命名為RSA算法，是目前使用的也通用的非對稱加密算法。它的非常簡單的工作原理立足于大整數(shù)的算術(shù)，兩個(gè)密鑰由兩個(gè)大的素?cái)?shù)產(chǎn)生。加密和解密

　　的過程可用數(shù)學(xué)表示如下：

　　n=公開模數(shù)=p.q    p.q＝兩個(gè)秘密的素?cái)?shù)。

　　在進(jìn)行編碼之前，明文字組的大小必須填補(bǔ)到合適的字組大小，它隨著所用密鑰的長度在RSA算法中的不同而改變。加密的本身是執(zhí)行明文的指數(shù)的模數(shù)運(yùn)算，這一處理的結(jié)果就是密文。如果已知私有鑰密，則只有用它才能解密，解密的過程類似于加密過程。

　　算法的安全性建立在分解大數(shù)因數(shù)的困難之上，用兩個(gè)素?cái)?shù)相乘很容易求得公開的模數(shù)，但要把此模數(shù)分解成兩個(gè)素因數(shù)則非常困難，因?yàn)閷@種運(yùn)算沒有有效的算法。

　　IC卡的RAM容量對于執(zhí)行加密和解密電文時(shí)所需的大數(shù)的指數(shù)運(yùn)算來說是不適用的，因?yàn)樵诮邮苣?shù)運(yùn)算之前這個(gè)數(shù)就已經(jīng)變得很大了。因此，使用了“模數(shù)”的指數(shù)，這就是說計(jì)算的中間結(jié)果，絕不會(huì)超過模數(shù)之值。例如，如果必須計(jì)算x2 mod n，則并不直接去計(jì)算表達(dá)式（x，x）mod n，因?yàn)橹虚g結(jié)果（x，x）在模數(shù)運(yùn)算把它減小之前就已經(jīng)不必要地變得太大了。相反，計(jì)算的是表達(dá)式（（x mod n）·（x mod n））mod n，它可得到相同的數(shù)學(xué)結(jié)果。這樣做的好處是明顯地減少了計(jì)算而存儲(chǔ)量也較小，因?yàn)橹虚g結(jié)果的大小被立即減小了。

　　另一個(gè)提高RSA算法的方法是用中國剩余定理來計(jì)算①。當(dāng)然，使用中國剩余定理的前提是要知道這兩個(gè)秘密素?cái)?shù)P和g，這就是說它只能用于解密（簡而言之，用于簽署）。

　　私有密鑰應(yīng)當(dāng)盡可能地大，因?yàn)檫@樣可阻止破譯的企圖。公開密鑰和私有密鑰可有不同的長度，事實(shí)上通常也是這種情形，因?yàn)轵?yàn)證數(shù)字簽名所需的時(shí)間隨著把公開密鑰盡量減小而明顯地縮短。第4個(gè)Fermat數(shù)經(jīng)常被用來作為公開密鑰。這個(gè)素?cái)?shù)之值為216+1=65 537，而由于它比較小，所以非常適合快速驗(yàn)證數(shù)字簽名，同樣也使用數(shù)字7和17，參見表1。

　　表1  RSA算法的典型的公開密鑰

　　如果一個(gè)攻擊者成功地把公開模數(shù)分解為兩個(gè)素因數(shù)，將能重現(xiàn)整個(gè)加密過程。對于一個(gè)小的數(shù)值，例如l1，分解此模數(shù)是很容易的，但是目前沒有快速的算法可用于大數(shù)。如果能找到兩個(gè)素因數(shù)之值，系統(tǒng)就被攻破，因?yàn)樗接忻荑€已被知道了。②因此。對RSA密鑰的需求是要有足夠長。長度為512位（“字節(jié)），在目前被認(rèn)為是下限。無論如何，768位（96字節(jié)）和1 024位（128字節(jié)）的密鑰都已在使用中。在即將來臨的年月里，2 048位（256字節(jié)）的密鑰將會(huì)投入使用。加密和解密所需的計(jì)算量隨密鑰長度而增加，這種增加不是線性的，相反卻是近似于指數(shù)的。

　　具有8位CPU的智能卡微控制器通常不能在短于數(shù)分鐘的時(shí)間內(nèi)執(zhí)行RSA計(jì)算。然而，現(xiàn)在已經(jīng)特別開發(fā)了具有可以快速求冪的輔助算術(shù)處理器的微控制器。有了它們，就有可能以合理的軟件開銷在可以接受的時(shí)間長度之內(nèi)執(zhí)行RSA計(jì)算。有硬件支持的512位的RSA算法的編碼長度大約為300字節(jié)。對于768位和1024位長的密鑰在智能卡中的匯編代碼長度約有1KB。如果觀察一下表2，將看到即使是一個(gè)512位長的密鑰，其可能的素因數(shù)的數(shù)目也是如此巨大，使得在兩個(gè)不同的密鑰對之間的碰撞永遠(yuǎn)不會(huì)發(fā)生。①

　　表2  典型的RSA密鑰長度和特性參數(shù)
　　（比值NS/NP表明非素?cái)?shù)的數(shù)目與素因數(shù)數(shù)目之間的關(guān)系，它的倒數(shù)就是在數(shù)字空間的一
　　個(gè)隨機(jī)數(shù)是素?cái)?shù)的概率，對于產(chǎn)生一個(gè)RSA密鑰所需要的時(shí)間長度來說這是極其重要的）

　　然而，和DES（舉例）相反，RSA算法的實(shí)力之一在于它的密鑰不限于一個(gè)特定長度，如果需要增加安全性，就可用比較長的密鑰而不需要對算法做任何改變。于是，RSA算法是可縮放的，當(dāng)然必須不能忘記計(jì)算時(shí)間和所需要的存儲(chǔ)空間。在目前，即使5l2位的密鑰也還被認(rèn)為是安全的。對于目前的因子算法，一個(gè)很好的經(jīng)驗(yàn)規(guī)律是密鑰長度每增加15位，計(jì)算量就要增加一倍②。Andrew Odlyzko［Odlyzko 95］對分解因數(shù)和破譯非對稱加密算法二者所需處理量以及在整個(gè)世界上實(shí)際可用的處理量給出了一個(gè)出色的總結(jié)。

　　雖然，RSA算法是非常安全的，但它卻很少用于加密數(shù)據(jù)，因?yàn)橛?jì)算時(shí)間太長了。它主要用在數(shù)字簽名的領(lǐng)域，在這里非對稱處理的好處得到了充分的體現(xiàn)，參見表3。對智能卡來說，RSA算法的缺點(diǎn)是密鑰所需的存儲(chǔ)空間量。在某些情況下，密鑰產(chǎn)生的復(fù)雜性也會(huì)引起一些問題。

　　RSA的普遍應(yīng)用受到在幾個(gè)國家中已經(jīng)申請的的限制，以及包含有這種算法的設(shè)各在進(jìn)出口上的主要限制。具有RSA協(xié)處理器的智能卡受到這些條款的影響，嚴(yán)重地妨礙了它們在國際上的應(yīng)用。

　　RSA算法的密鑰的產(chǎn)生是按照簡單的處理進(jìn)行的，下面是一個(gè)小型的逐步進(jìn)行的例子：

　　（1）首先，選擇兩個(gè)素?cái)?shù)p和g：                       P=3;q=11;

　?。?）其次，計(jì)算公開模數(shù)：                           n=P;q=33

　　（3）計(jì)算用于產(chǎn)生密鑰的中間變量z：                  Z=（P-1）（q-1）

　?。?）計(jì)算滿足條件e<z和gcd（z,e）=1的公開密鑰e（這就是說z和e的公約數(shù)為1）

　　由于有幾個(gè)數(shù)可滿是這些條件選擇其中之一：           e=7

　　（5）計(jì)算私有密鑰d,它應(yīng)滿足條件（d,e）mod z=1;       d=3

　　這樣就完成了密鑰的計(jì)算，現(xiàn)在可用RSA算法對公開和私有密鑰的加密和解密進(jìn)行測試，用數(shù)字例子說明如下：

　?。?）以數(shù)字4為明文X（X＜n）：

　?。?）加密電文：

　?。?）計(jì)算的結(jié)果為密文y：

　　（4）對密文解密：

　　對密文解密的結(jié)果如所預(yù)期，重新得到了明文。

　　表3  作為密鑰長度的函數(shù)的RSA加密和解密計(jì)算時(shí)間的樣例
　?。ㄋo出的數(shù)值的一部分有著明顯的改變，這是因?yàn)樗鼈円蕾?BR>　　密鑰的位結(jié)構(gòu)和采用了中國剩余定理算法，它僅能用于簽署）

　　在實(shí)踐中，產(chǎn)生密鑰是比較辛苦的，因?yàn)闇y試大的數(shù)字以斷定它們是否素?cái)?shù)是極其困難的。的Eratosthenes的篩法在這里不能使用，因?yàn)樗枰嘘P(guān)小于被檢測數(shù)的所有素?cái)?shù)的預(yù)各知識(shí)。對于像有512位這樣大的數(shù)這在實(shí)際上是不可能的。因此，用概率測試來決定所選之?dāng)?shù)是素?cái)?shù)的概率，Miller-Rabin檢測和Solovay-Strassen檢測①是這種檢測的典型例子。為了避免過于經(jīng)常使用這些耗費(fèi)時(shí)間的測試，隨機(jī)產(chǎn)生一個(gè)候選的數(shù)字并首先檢驗(yàn)它是否具有小的素因子。如果這個(gè)隨機(jī)產(chǎn)生的數(shù)字能夠被諸如2、3、5或7這樣的小素?cái)?shù)整除，那么很明顯它本身不是素?cái)?shù)，一旦確定被檢測之?dāng)?shù)沒有任何小的素因子，則可應(yīng)用像Miller-Rabin這樣的檢測。這一檢測的原理已說明在圖1中，而IEEE 1363標(biāo)準(zhǔn)的附錄中則有詳細(xì)描述。②。

　　表4  產(chǎn)生非對稱加密算法RSA的公開和私有密鑰對所需的時(shí)間之例
　　（無法給出準(zhǔn)確的時(shí)間，因?yàn)閷Ξa(chǎn)生密鑰的處理依賴于所產(chǎn)生的隨機(jī)數(shù)是否素?cái)?shù)）

　　產(chǎn)生RSA密鑰的算法具有一特殊的性質(zhì)，即產(chǎn)生一密鑰對（一個(gè)公開密鑰和相應(yīng)之私有密鑰）所需的時(shí)間只能是可統(tǒng)計(jì)預(yù)測的。這就是說，僅能以某個(gè)概率來指出產(chǎn)生密鑰要占用的時(shí)間量。明確的斷言，諸如“要占用笳秒”是不可能的，因?yàn)橐獙﹄S機(jī)數(shù)運(yùn)行素?cái)?shù)測試，執(zhí)行這一測試所需的時(shí)間無法預(yù)先斷定，參見圖2和表4所示。

　　圖1  產(chǎn)生用于智能卡的RSA密鑰的基本過程

　　圖2  產(chǎn)生RSA算法的密鑰對的概率的時(shí)間曲線（縱軸為以確定時(shí)間產(chǎn)
　　生一智能卡的1024位密鑰的概率，曲線所覆蓋的總面積之概率為1）

　　歡迎轉(zhuǎn)載，信息來源維庫電子市場網(wǎng)（m.58mhw.cn）