引言 
 RSA密碼系統(tǒng)是較早提出的一種公開(kāi)鑰密碼系統(tǒng)。1978年，美國(guó)麻省理工學(xué)院（MIT）的Rivest,Shamir和Adleman在題為《獲得數(shù)字簽名和公開(kāi)鑰密碼系統(tǒng)的方法》的論文中提出了基于數(shù)論的非對(duì)稱(chēng)(公開(kāi)鑰)密碼體制，稱(chēng)為RSA密碼體制。RSA是建立在“大整數(shù)的素因子分解是困難問(wèn)題”基礎(chǔ)上的，是一種分組密碼體制。 

 介紹公鑰密碼體制（背景） 

 1、對(duì)稱(chēng)密碼體制 

 對(duì)稱(chēng)密碼體制是一種傳統(tǒng)密碼體制，也稱(chēng)為私鑰密碼體制。在對(duì)稱(chēng)加密系統(tǒng)中，加密和解密采用相同的密鑰。因?yàn)榧咏饷苊荑€相同，需要通信的雙方必須選擇和保存他們共同的密鑰，各方必須信任對(duì)方不會(huì)將密鑰泄密出去，這樣就可以實(shí)現(xiàn)數(shù)據(jù)的機(jī)密性和完整性。對(duì)于具有n個(gè)用戶(hù)的網(wǎng)絡(luò)，需要n(n-1)/2個(gè)密鑰，在用戶(hù)群不是很大的情況下，對(duì)稱(chēng)加密系統(tǒng)是有效的。但是對(duì)于大型網(wǎng)絡(luò)，當(dāng)用戶(hù)群很大，分布很廣時(shí)，密鑰的分配和保存就成了問(wèn)題。對(duì)機(jī)密信息進(jìn)行加密和驗(yàn)證隨報(bào)文一起發(fā)送報(bào)文摘要(或散列值)來(lái)實(shí)現(xiàn)。比較典型的算法有DES(Data Encryption Standard數(shù)據(jù)加密標(biāo)準(zhǔn))算法及其變形Triple DES(三重DES)，GDES(廣義DES)；歐洲的IDEA；日本的FEAL N、RC5等。DES標(biāo)準(zhǔn)由美國(guó)國(guó)家標(biāo)準(zhǔn)局提出,主要應(yīng)用于銀行業(yè)的電子資金轉(zhuǎn)帳(EFT)領(lǐng)域。DES的密鑰長(zhǎng)度為56bit。Triple DES使用兩個(gè)獨(dú)立的56bit密鑰對(duì)交換的信息進(jìn)行3次加密，從而使其有效長(zhǎng)度達(dá)到112bit。RC2和RC4方法是RSA數(shù)據(jù)安全公司的對(duì)稱(chēng)加密專(zhuān)利算法，它們采用可變密鑰長(zhǎng)度的算法。通過(guò)規(guī)定不同的密鑰長(zhǎng)度,，C2和RC4能夠提高或降低安全的程度。對(duì)稱(chēng)密碼算法的優(yōu)點(diǎn)是計(jì)算開(kāi)銷(xiāo)小，加密速度快，是目前用于信息加密的主要算法。它的局限性在于它存在著通信的貿(mào)易雙方之間確保密鑰安全交換的問(wèn)題。此外，某一貿(mào)易方有幾個(gè)貿(mào)易關(guān)系，他就要維護(hù)幾個(gè)專(zhuān)用密鑰。它也沒(méi)法鑒別貿(mào)易發(fā)起方或貿(mào)易最終方，因?yàn)橘Q(mào)易的雙方的密鑰相同。另外，由于對(duì)稱(chēng)加密系統(tǒng)僅能用于對(duì)數(shù)據(jù)進(jìn)行加解密處理，提供數(shù)據(jù)的機(jī)密性，不能用于數(shù)字簽名。因而人們迫切需要尋找新的密碼體制。  

 2、非對(duì)稱(chēng)密碼體制  

 非對(duì)稱(chēng)密碼體制也叫公鑰加密技術(shù)，該技術(shù)就是針對(duì)私鑰密碼體制的缺陷被提出來(lái)的。在公鑰加密系統(tǒng)中，加密和解密是相對(duì)獨(dú)立的，加密和解密會(huì)使用兩把不同的密鑰，加密密鑰(公開(kāi)密鑰)向公眾公開(kāi)，誰(shuí)都可以使用，解密密鑰(秘密密鑰)只有解密人自己知道，非法使用者根據(jù)公開(kāi)的加密密鑰無(wú)法推算出解密密鑰，顧其可稱(chēng)為公鑰密碼體制。如果一個(gè)人選擇并公布了他的公鑰，另外任何人都可以用這一公鑰來(lái)加密傳送給那個(gè)人的消息。私鑰是秘密保存的，只有私鑰的所有者才能利用私鑰對(duì)密文進(jìn)行解密。公鑰密碼體制的算法中最著名的代表是RSA系統(tǒng)，此外還有:背包密碼、McEliece密碼、Diffe_Hellman、Rabin、零知識(shí)證明、橢圓曲線(xiàn)、EIGamal算法等。公鑰密鑰的密鑰管理比較簡(jiǎn)單,并且可以方便的實(shí)現(xiàn)數(shù)字簽名和驗(yàn)證。但算法復(fù)雜,加密數(shù)據(jù)的速率較低。公鑰加密系統(tǒng)不存在對(duì)稱(chēng)加密系統(tǒng)中密鑰的分配和保存問(wèn)題，對(duì)于具有n個(gè)用戶(hù)的網(wǎng)絡(luò)，僅需要2n個(gè)密鑰。公鑰加密系統(tǒng)除了用于數(shù)據(jù)加密外，還可用于數(shù)字簽名。公鑰加密系統(tǒng)可提供以下功能：A、機(jī)密性（Confidentiality）：保證非授權(quán)人員不能非法獲取信息，通過(guò)數(shù)據(jù)加密來(lái)實(shí)現(xiàn)；B、確認(rèn)（Authentication）：保證對(duì)方屬于所聲稱(chēng)的實(shí)體，通過(guò)數(shù)字簽名來(lái)實(shí)現(xiàn)；C、數(shù)據(jù)完整性（Data integrity）：保證信息內(nèi)容不被篡改，入侵者不可能用假消息代替合法消息，通過(guò)數(shù)字簽名來(lái)實(shí)現(xiàn)；D、不可抵賴(lài)性（Nonrepudiation）：發(fā)送者不可能事后否認(rèn)他發(fā)送過(guò)消息，消息的接受者可以向中立的第三方證實(shí)所指的發(fā)送者確實(shí)發(fā)出了消息，通過(guò)數(shù)字簽名來(lái)實(shí)現(xiàn)?？梢?jiàn)公鑰加密系統(tǒng)滿(mǎn)足信息安全的所有主要目標(biāo)。 

 RSA公鑰密碼體制的優(yōu)勢(shì)（意義） 

1 解決大規(guī)模網(wǎng)絡(luò)應(yīng)用中密鑰的分發(fā)和管理問(wèn)題 

 采用分組密碼、序列密碼等對(duì)稱(chēng)密碼體制時(shí)，加解密雙方所用的密鑰都是秘密的，而且需要定期更換，新的密鑰總是要通過(guò)某種秘密渠道分配給使用方，在傳遞的過(guò)程中，稍有不慎，就容易泄露。 

 公鑰密碼加密密鑰通常是公開(kāi)的，而解密密鑰是秘密的，由用戶(hù)自己保存，不需要往返交換和傳遞，大大減少了密鑰泄露的危險(xiǎn)性。同時(shí)，在網(wǎng)絡(luò)通信中使用對(duì)稱(chēng)密碼體制時(shí)，網(wǎng)絡(luò)內(nèi)任何兩個(gè)用戶(hù)都需要使用互不相同的密鑰，只有這樣，才能保證不被第三方竊聽(tīng)，因而N個(gè)用戶(hù)就要使用N（N–1）/2個(gè)密鑰。在大型網(wǎng)絡(luò)中，如果有100萬(wàn)個(gè)用戶(hù)，則要使用4950萬(wàn)個(gè)密鑰，密鑰量太大，難以管理，而且使用起來(lái)非常麻煩。采用公鑰密碼體制，N個(gè)用戶(hù)只需要產(chǎn)生N對(duì)密鑰。仍以100萬(wàn)個(gè)用戶(hù)為例，只需100萬(wàn)對(duì)密鑰，需要秘密保存的僅100萬(wàn)個(gè)私鑰，二者相差近50倍，數(shù)量大大減少，而且分發(fā)簡(jiǎn)單，安全性好。由此可見(jiàn)，只有公鑰密碼才能方便、可靠地解決大規(guī)模網(wǎng)絡(luò)應(yīng)用中密鑰的分發(fā)和管理問(wèn)題。 

 2 實(shí)現(xiàn)網(wǎng)絡(luò)中的數(shù)字簽名機(jī)制 

 對(duì)稱(chēng)密鑰技術(shù)由于其自身的局限性，無(wú)法提供網(wǎng)絡(luò)中的數(shù)字簽名。這是因?yàn)閿?shù)字簽名是網(wǎng)絡(luò)中表征人或機(jī)構(gòu)的真實(shí)性的重要手段，數(shù)字簽名的數(shù)據(jù)需要有惟一性、私有性，而對(duì)稱(chēng)密鑰技術(shù)中的密鑰至少需要在交互雙方之間共享，因此，不滿(mǎn)足惟一性、私有性，無(wú)法用做網(wǎng)絡(luò)中的數(shù)字簽名。相比之下，公鑰密碼技術(shù)由于存在一對(duì)公鑰和私鑰，私鑰可以表征惟一性和私有性，而且經(jīng)私鑰加密的數(shù)據(jù)只能用與之對(duì)應(yīng)的公鑰來(lái)驗(yàn)證，其他人無(wú)法仿冒，所以，可以用做網(wǎng)絡(luò)中的數(shù)字簽名服務(wù)。 

 具體而言，一段消息以發(fā)送方的私鑰加密之后，任何擁有與該私鑰相對(duì)應(yīng)的公鑰的人均可將它解密。由于該私鑰只有發(fā)送方擁有，且該私鑰是密藏不公開(kāi)的，所以，以該私鑰加密的信息可看做發(fā)送方對(duì)該信息的簽名，其作用和現(xiàn)實(shí)中的手工簽名一樣有效而且具有不可抵賴(lài)性。 

 一種具體的做法是：認(rèn)證服務(wù)器和用戶(hù)各持有自己的證書(shū)，用戶(hù)端將一個(gè)隨機(jī)數(shù)用自己的私鑰簽名后和證書(shū)一起用服務(wù)器的公鑰加密后傳輸?shù)椒?wù)器；使用服務(wù)器的公鑰加密保證了只有認(rèn)證服務(wù)器才能進(jìn)行解密，使用用戶(hù)的密鑰簽名保證了數(shù)據(jù)是由該用戶(hù)發(fā)出；服務(wù)器收到用戶(hù)端數(shù)據(jù)后，首先用自己的私鑰解密，取出用戶(hù)的證書(shū)后，使用用戶(hù)的公鑰進(jìn)行解密，若成功，則到用戶(hù)數(shù)據(jù)庫(kù)中檢索該用戶(hù)及其權(quán)限信息，將認(rèn)證成功的信息和用戶(hù)端傳來(lái)的隨機(jī)數(shù)用服務(wù)器的私鑰簽名后，使用用戶(hù)的公鑰進(jìn)行加密，然后，傳回給用戶(hù)端，用戶(hù)端解密后即可得到認(rèn)證成功的信息。 

 介紹RSA公鑰密碼體制 

 RSA是Rivest,Shamir,Adleman提出基于數(shù)論的非對(duì)稱(chēng)密鑰體制。RSA是建立在大整數(shù)分解的困難上的,是一種分組密碼體制。它是以推廣的歐拉定理為基礎(chǔ)的（見(jiàn)下）： 

 定理1 若(a,n)=1, 則 ＝(mod n) ,其中φ(n) 表示不超過(guò)n與n互素的正整數(shù)個(gè)數(shù)。 
 定理2 若(m1,m2)=1，則φ(m1 • m2)=φ(m1) • φ(m2)。 
 定理3 若p為素?cái)?shù)，則φ(p)=p-1。  
 RSA建立方法如下:  
 •首先隨機(jī)選兩個(gè)大素?cái)?shù)p,q , 計(jì)算n=p • q； 
 •計(jì)算歐拉函數(shù) φ(n)=(p-1)(q-1)； 
 •任選一個(gè)整數(shù)e為公開(kāi)加密密鑰，由e求出秘密解密密鑰d：d • e＝ 1 mod φ(n)＝ k  
 'φ(n) +1 
 •加密/解密： 
 將明文分成長(zhǎng)度小于 位的明文塊m， 
 加密過(guò)程是：c = E(m，e) = mod n 
 解密過(guò)程是：m = D(c，d) = mod n 
 在RSA體制下： D(d, E(m，e)) o = o m mod n 
 E(e, D(d,m)) o = o m mod n  

 e,d可以互換。在用于數(shù)字簽名時(shí),發(fā)送方只須用己方的解密密鑰d先 "加密"即可, 因?yàn)橹挥邪l(fā)送方自己知道自己的d, 收方只有用對(duì)應(yīng)的e "解密"  
 才能知道明文, 同時(shí)也驗(yàn)證了發(fā)方的身份。 

 RSA公鑰密碼體制的安全性分析 

 RSA的安全性依賴(lài)于大整數(shù)的因式分解問(wèn)題。實(shí)際上，人們推測(cè)RSA的安全性依賴(lài)于大整數(shù)的因式分解問(wèn)題，但誰(shuí)也沒(méi)有在數(shù)學(xué)上證明從c和e計(jì)算m需要對(duì)n進(jìn)行因式分解?？梢韵胂罂赡軙?huì)有完全不同的方式去分析RSA。然而，如果這種方法能讓密碼解析員推導(dǎo)出d，則它也可以用作大整數(shù)因式分解的新方法。最難以令人置信的是，有些RSA變體已經(jīng)被證明與因式分解同樣困難。甚至從RSA加密的密文中恢復(fù)出某些特定的位也與解密整個(gè)消息同樣困難。另外，對(duì)RSA的具體實(shí)現(xiàn)存在一些針對(duì)協(xié)議而不是針對(duì)基本算法的攻擊方法。 

 攻擊者對(duì)RSA系統(tǒng)攻擊的目標(biāo)可以分為三類(lèi)： 

 設(shè)計(jì)RSA系統(tǒng)的注意事項(xiàng) 

 1經(jīng)過(guò)對(duì)RSA安全性的分析，可以得出使用RSA時(shí)應(yīng)該注意的事項(xiàng)： 
 •隨機(jī)選擇足夠大素?cái)?shù)（目前應(yīng)在512位以上）； 
 •在使用RSA的通信網(wǎng)絡(luò)協(xié)議中，不應(yīng)該使用公共模（使用者知道f(n)）； 
 •不要讓攻擊者得到原始的解密結(jié)果； 
 •解密密鑰d相對(duì)模數(shù)n來(lái)說(shuō)不應(yīng)過(guò)??； 
 •應(yīng)該或者加密密鑰大；或者被加密的信息m總是大而且m不能是一些已知值的乘積，后面一種情況可以在加密前對(duì)m填充隨機(jī)值實(shí)現(xiàn)。 
 •相關(guān)的消息不能用同樣的密鑰加密，加密前對(duì)消息進(jìn)行隨機(jī)值填充破壞消息之間的代數(shù)聯(lián)系及相關(guān)性，但是要注意填充算法的選擇；  
 •應(yīng)該使獲得對(duì)任意值的原始簽名不可能。 
 •被簽名的消息應(yīng)該與模數(shù)差不多大，而且不是一些已知值的乘積； 
 •使用平均解密時(shí)間和混亂(blinding)等方法使時(shí)間攻擊中使用的統(tǒng)計(jì)手段失效； 
 •如果有條件，采用規(guī)模差別比較大的質(zhì)因子p,q來(lái)提高系統(tǒng)的安全性； 

 2 RSA系統(tǒng)的參數(shù)選擇 

 RSA系統(tǒng)是第一個(gè)將安全性植基于因子分解的系統(tǒng)。很明顯地，在公開(kāi)密鑰（e,N）中，若N能被因子分解，則在模N中所有元素價(jià)的最小公倍數(shù)（即所謂陷門(mén)）T=φ(N)=(p-1)(q-1)即無(wú)從隱藏。使得解密密鑰d不再是秘密，進(jìn)而整個(gè)RSA系統(tǒng)即不安全。雖然迄今人們尚無(wú)法“證明”，破解RSA系統(tǒng)等于因子分解。但一般“相信”RSA系統(tǒng)的安全性，等價(jià)于因子分解。即：若能分解因子N，即攻破RSA系統(tǒng)； 

 若能攻破RSA系統(tǒng)，即分解因子N（相信，但未證明） 

 因此，在使用RSA系統(tǒng)時(shí)，對(duì)于公開(kāi)密鑰N的選擇非常重要。必須使得公開(kāi)N后，任何人無(wú)法從N得到T。此外，對(duì)于公開(kāi)密鑰e與解密密鑰d，亦需有所限制。否則在使用上可能會(huì)導(dǎo)致RSA系統(tǒng)被攻破，或應(yīng)用在密碼協(xié)議上不安全。 
 經(jīng)過(guò)分析，我們知道RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系，X.931標(biāo)準(zhǔn)對(duì)此提出以下幾點(diǎn)： 
 •如果公鑰e是奇數(shù)，e應(yīng)與p-1，q-1互質(zhì)； 
 •如果公鑰e是偶數(shù)，e必須與(p-1)/2,(q-1)/2互質(zhì)，且poq mod 8不成立； 
 •模數(shù)的長(zhǎng)應(yīng)該為1024+256x，x=0,1• • • • • • ； 
 •質(zhì)數(shù)p，q應(yīng)通過(guò)質(zhì)數(shù)檢測(cè)，使出錯(cuò)的概率小于 ； 
 •p-1,q-1,p+1,q+1應(yīng)有大質(zhì)數(shù)因子； 
 •gcd(p-1,q-1)應(yīng)該小； 
 •p/q不應(yīng)靠近兩個(gè)小整數(shù)比值，且 ； 
 •|p-q|應(yīng)有大質(zhì)數(shù)因子。 

 RSA公鑰密碼體制的應(yīng)用 

 1數(shù)字簽名 

 長(zhǎng)期以來(lái)的日常生活中，對(duì)于重要的文件，為了防止對(duì)文件的否認(rèn)，偽造，篡改等等的破壞，傳統(tǒng)的方法是在文件上手寫(xiě)簽名。但是在計(jì)算機(jī)系統(tǒng)中無(wú)法使用手寫(xiě)簽名，而代之對(duì)應(yīng)的數(shù)字簽名機(jī)制。數(shù)字簽名應(yīng)該能實(shí)現(xiàn)手寫(xiě)簽名的作用，其本質(zhì)特征就是僅能利用簽名者的私有信息產(chǎn)生簽名。因此，當(dāng)它被驗(yàn)證時(shí)，它也能被信任的第三方（如法官）在任一時(shí)刻證明只有私有信息的唯一掌握者才能產(chǎn)生此簽名。  
 數(shù)字簽名具有以下特點(diǎn)： 
 •簽名是可信的； 
 •簽名是不能偽造的； 
 •簽名是不可重用的； 
 •簽名后的文件是不能更改的； 
 •簽名是不能否認(rèn)的。 
 由于非對(duì)稱(chēng)密碼體制的特點(diǎn)，對(duì)于數(shù)字簽名的實(shí)現(xiàn)比在對(duì)稱(chēng)密碼體制下要有效和簡(jiǎn)單的多。 

 2 RSA公鑰簽名技術(shù) 

 數(shù)字簽名可以用秘密密鑰利，也可用公開(kāi)密鑰。但采用秘密密鑰是建立在有一個(gè)眾人信任的中間機(jī)構(gòu)的基礎(chǔ)上，而采用公鑰加密法進(jìn)行數(shù)字簽名則不受此限制，收發(fā)兩方之間不需要任何可信賴(lài)機(jī)構(gòu)。假定公開(kāi)密鑰加密和解密算法除了滿(mǎn)足D（E（P））=P外，還能滿(mǎn)足E（D（P））=P（RSA滿(mǎn)足這兩個(gè)條件，所以這個(gè)假定并不是不現(xiàn)實(shí)的）。那么發(fā)方A就可以通過(guò)EB（DA（P））的轉(zhuǎn)換，將一條簽名的明文信息P發(fā)給收方B。注意，A知道自己的私有解密密鑰DA，還知道B的公開(kāi)密鑰EB，所以建立這條信息的工作應(yīng)由A來(lái)做。 

 當(dāng)B收到這條消息后，他象往常一樣用自己的私有密鑰將它解密，得到DA（P），如圖所示。他將這條信息放在一個(gè)安全的地方，然后用EA解密，得到初始的明文。 

 要了解這種簽名是如何工作的，現(xiàn)在假設(shè)A后來(lái)否認(rèn)曾經(jīng)發(fā)送消息P給B。當(dāng)案子上了法庭，B能夠出示P和 DA(P)。法官只要使用一下EA，就能輕易地證明B確實(shí)有一條用DA加密的有效信息。由于B不知道A的私有密鑰，B能得到用它加密的唯一途徑就是A發(fā)送過(guò)來(lái)的。 

 需要說(shuō)明的是，雖然使用公開(kāi)密鑰加密法進(jìn)行數(shù)字簽名的是一個(gè)很好的方法，但仍有一些問(wèn)題存在于它們所應(yīng)用的環(huán)境而不是算法。只有當(dāng)  
DA保密時(shí)，B才能證明某條信息是A發(fā)送來(lái)的。如果A公開(kāi)了它的私有密鑰，那么證據(jù)就不成立了，因?yàn)槿魏稳税˙都可以發(fā)送這條消息。 

 網(wǎng)絡(luò)技術(shù)的發(fā)展使得，電子商務(wù)正在廣泛開(kāi)展，電子郵件也被普遍使用，數(shù)字簽名技術(shù)越來(lái)越重要。RSA雖然有算法復(fù)雜，速度慢的缺點(diǎn)，但目前還是被廣泛的應(yīng)用于數(shù)字簽名中。隨著計(jì)算機(jī)技術(shù)的發(fā)展及對(duì)RSA的深入研究，目前RSA正在走向?qū)嵱没?，商業(yè)化,可以預(yù)見(jiàn)在網(wǎng)絡(luò)安全中，基于RSA的網(wǎng)絡(luò)安全系統(tǒng)的設(shè)計(jì)將會(huì)廣泛使用。