安全技術(shù)—RSA公鑰密碼體制安全性分析
更新時(shí)間:2007年01月16日 00:00:00 作者:
引言
RSA密碼系統(tǒng)是較早提出的一種公開鑰密碼系統(tǒng)。1978年,美國麻省理工學(xué)院(MIT)的Rivest,Shamir和Adleman在題為《獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法》的論文中提出了基于數(shù)論的非對稱(公開鑰)密碼體制,稱為RSA密碼體制。RSA是建立在“大整數(shù)的素因子分解是困難問題”基礎(chǔ)上的,是一種分組密碼體制。
介紹公鑰密碼體制(背景)
1、對稱密碼體制
對稱密碼體制是一種傳統(tǒng)密碼體制,也稱為私鑰密碼體制。在對稱加密系統(tǒng)中,加密和解密采用相同的密鑰。因?yàn)榧咏饷苊荑€相同,需要通信的雙方必須選擇和保存他們共同的密鑰,各方必須信任對方不會將密鑰泄密出去,這樣就可以實(shí)現(xiàn)數(shù)據(jù)的機(jī)密性和完整性。對于具有n個(gè)用戶的網(wǎng)絡(luò),需要n(n-1)/2個(gè)密鑰,在用戶群不是很大的情況下,對稱加密系統(tǒng)是有效的。但是對于大型網(wǎng)絡(luò),當(dāng)用戶群很大,分布很廣時(shí),密鑰的分配和保存就成了問題。對機(jī)密信息進(jìn)行加密和驗(yàn)證隨報(bào)文一起發(fā)送報(bào)文摘要(或散列值)來實(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)由美國國家標(biāo)準(zhǔn)局提出,主要應(yīng)用于銀行業(yè)的電子資金轉(zhuǎn)帳(EFT)領(lǐng)域。DES的密鑰長度為56bit。Triple DES使用兩個(gè)獨(dú)立的56bit密鑰對交換的信息進(jìn)行3次加密,從而使其有效長度達(dá)到112bit。RC2和RC4方法是RSA數(shù)據(jù)安全公司的對稱加密專利算法,它們采用可變密鑰長度的算法。通過規(guī)定不同的密鑰長度,,C2和RC4能夠提高或降低安全的程度。對稱密碼算法的優(yōu)點(diǎn)是計(jì)算開銷小,加密速度快,是目前用于信息加密的主要算法。它的局限性在于它存在著通信的貿(mào)易雙方之間確保密鑰安全交換的問題。此外,某一貿(mào)易方有幾個(gè)貿(mào)易關(guān)系,他就要維護(hù)幾個(gè)專用密鑰。它也沒法鑒別貿(mào)易發(fā)起方或貿(mào)易最終方,因?yàn)橘Q(mào)易的雙方的密鑰相同。另外,由于對稱加密系統(tǒng)僅能用于對數(shù)據(jù)進(jìn)行加解密處理,提供數(shù)據(jù)的機(jī)密性,不能用于數(shù)字簽名。因而人們迫切需要尋找新的密碼體制。
2、非對稱密碼體制
非對稱密碼體制也叫公鑰加密技術(shù),該技術(shù)就是針對私鑰密碼體制的缺陷被提出來的。在公鑰加密系統(tǒng)中,加密和解密是相對獨(dú)立的,加密和解密會使用兩把不同的密鑰,加密密鑰(公開密鑰)向公眾公開,誰都可以使用,解密密鑰(秘密密鑰)只有解密人自己知道,非法使用者根據(jù)公開的加密密鑰無法推算出解密密鑰,顧其可稱為公鑰密碼體制。如果一個(gè)人選擇并公布了他的公鑰,另外任何人都可以用這一公鑰來加密傳送給那個(gè)人的消息。私鑰是秘密保存的,只有私鑰的所有者才能利用私鑰對密文進(jìn)行解密。公鑰密碼體制的算法中最著名的代表是RSA系統(tǒng),此外還有:背包密碼、McEliece密碼、Diffe_Hellman、Rabin、零知識證明、橢圓曲線、EIGamal算法等。公鑰密鑰的密鑰管理比較簡單,并且可以方便的實(shí)現(xiàn)數(shù)字簽名和驗(yàn)證。但算法復(fù)雜,加密數(shù)據(jù)的速率較低。公鑰加密系統(tǒng)不存在對稱加密系統(tǒng)中密鑰的分配和保存問題,對于具有n個(gè)用戶的網(wǎng)絡(luò),僅需要2n個(gè)密鑰。公鑰加密系統(tǒng)除了用于數(shù)據(jù)加密外,還可用于數(shù)字簽名。公鑰加密系統(tǒng)可提供以下功能:A、機(jī)密性(Confidentiality):保證非授權(quán)人員不能非法獲取信息,通過數(shù)據(jù)加密來實(shí)現(xiàn);B、確認(rèn)(Authentication):保證對方屬于所聲稱的實(shí)體,通過數(shù)字簽名來實(shí)現(xiàn);C、數(shù)據(jù)完整性(Data integrity):保證信息內(nèi)容不被篡改,入侵者不可能用假消息代替合法消息,通過數(shù)字簽名來實(shí)現(xiàn);D、不可抵賴性(Nonrepudiation):發(fā)送者不可能事后否認(rèn)他發(fā)送過消息,消息的接受者可以向中立的第三方證實(shí)所指的發(fā)送者確實(shí)發(fā)出了消息,通過數(shù)字簽名來實(shí)現(xiàn)。可見公鑰加密系統(tǒng)滿足信息安全的所有主要目標(biāo)。
RSA公鑰密碼體制的優(yōu)勢(意義)
1 解決大規(guī)模網(wǎng)絡(luò)應(yīng)用中密鑰的分發(fā)和管理問題
采用分組密碼、序列密碼等對稱密碼體制時(shí),加解密雙方所用的密鑰都是秘密的,而且需要定期更換,新的密鑰總是要通過某種秘密渠道分配給使用方,在傳遞的過程中,稍有不慎,就容易泄露。
公鑰密碼加密密鑰通常是公開的,而解密密鑰是秘密的,由用戶自己保存,不需要往返交換和傳遞,大大減少了密鑰泄露的危險(xiǎn)性。同時(shí),在網(wǎng)絡(luò)通信中使用對稱密碼體制時(shí),網(wǎng)絡(luò)內(nèi)任何兩個(gè)用戶都需要使用互不相同的密鑰,只有這樣,才能保證不被第三方竊聽,因而N個(gè)用戶就要使用N(N–1)/2個(gè)密鑰。在大型網(wǎng)絡(luò)中,如果有100萬個(gè)用戶,則要使用4950萬個(gè)密鑰,密鑰量太大,難以管理,而且使用起來非常麻煩。采用公鑰密碼體制,N個(gè)用戶只需要產(chǎn)生N對密鑰。仍以100萬個(gè)用戶為例,只需100萬對密鑰,需要秘密保存的僅100萬個(gè)私鑰,二者相差近50倍,數(shù)量大大減少,而且分發(fā)簡單,安全性好。由此可見,只有公鑰密碼才能方便、可靠地解決大規(guī)模網(wǎng)絡(luò)應(yīng)用中密鑰的分發(fā)和管理問題。
2 實(shí)現(xiàn)網(wǎng)絡(luò)中的數(shù)字簽名機(jī)制
對稱密鑰技術(shù)由于其自身的局限性,無法提供網(wǎng)絡(luò)中的數(shù)字簽名。這是因?yàn)閿?shù)字簽名是網(wǎng)絡(luò)中表征人或機(jī)構(gòu)的真實(shí)性的重要手段,數(shù)字簽名的數(shù)據(jù)需要有惟一性、私有性,而對稱密鑰技術(shù)中的密鑰至少需要在交互雙方之間共享,因此,不滿足惟一性、私有性,無法用做網(wǎng)絡(luò)中的數(shù)字簽名。相比之下,公鑰密碼技術(shù)由于存在一對公鑰和私鑰,私鑰可以表征惟一性和私有性,而且經(jīng)私鑰加密的數(shù)據(jù)只能用與之對應(yīng)的公鑰來驗(yàn)證,其他人無法仿冒,所以,可以用做網(wǎng)絡(luò)中的數(shù)字簽名服務(wù)。
具體而言,一段消息以發(fā)送方的私鑰加密之后,任何擁有與該私鑰相對應(yīng)的公鑰的人均可將它解密。由于該私鑰只有發(fā)送方擁有,且該私鑰是密藏不公開的,所以,以該私鑰加密的信息可看做發(fā)送方對該信息的簽名,其作用和現(xiàn)實(shí)中的手工簽名一樣有效而且具有不可抵賴性。
一種具體的做法是:認(rèn)證服務(wù)器和用戶各持有自己的證書,用戶端將一個(gè)隨機(jī)數(shù)用自己的私鑰簽名后和證書一起用服務(wù)器的公鑰加密后傳輸?shù)椒?wù)器;使用服務(wù)器的公鑰加密保證了只有認(rèn)證服務(wù)器才能進(jìn)行解密,使用用戶的密鑰簽名保證了數(shù)據(jù)是由該用戶發(fā)出;服務(wù)器收到用戶端數(shù)據(jù)后,首先用自己的私鑰解密,取出用戶的證書后,使用用戶的公鑰進(jìn)行解密,若成功,則到用戶數(shù)據(jù)庫中檢索該用戶及其權(quán)限信息,將認(rèn)證成功的信息和用戶端傳來的隨機(jī)數(shù)用服務(wù)器的私鑰簽名后,使用用戶的公鑰進(jìn)行加密,然后,傳回給用戶端,用戶端解密后即可得到認(rèn)證成功的信息。
介紹RSA公鑰密碼體制
RSA是Rivest,Shamir,Adleman提出基于數(shù)論的非對稱密鑰體制。RSA是建立在大整數(shù)分解的困難上的,是一種分組密碼體制。它是以推廣的歐拉定理為基礎(chǔ)的(見下):
定理1 若(a,n)=1, 則 =(mod n) ,其中φ(n) 表示不超過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為公開加密密鑰,由e求出秘密解密密鑰d:d • e= 1 mod φ(n)= k
'φ(n) +1
•加密/解密:
將明文分成長度小于 位的明文塊m,
加密過程是:c = E(m,e) = mod n
解密過程是: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, 收方只有用對應(yīng)的e "解密"
才能知道明文, 同時(shí)也驗(yàn)證了發(fā)方的身份。
RSA公鑰密碼體制的安全性分析
RSA的安全性依賴于大整數(shù)的因式分解問題。實(shí)際上,人們推測RSA的安全性依賴于大整數(shù)的因式分解問題,但誰也沒有在數(shù)學(xué)上證明從c和e計(jì)算m需要對n進(jìn)行因式分解。可以想象可能會有完全不同的方式去分析RSA。然而,如果這種方法能讓密碼解析員推導(dǎo)出d,則它也可以用作大整數(shù)因式分解的新方法。最難以令人置信的是,有些RSA變體已經(jīng)被證明與因式分解同樣困難。甚至從RSA加密的密文中恢復(fù)出某些特定的位也與解密整個(gè)消息同樣困難。另外,對RSA的具體實(shí)現(xiàn)存在一些針對協(xié)議而不是針對基本算法的攻擊方法。
攻擊者對RSA系統(tǒng)攻擊的目標(biāo)可以分為三類:
設(shè)計(jì)RSA系統(tǒng)的注意事項(xiàng)
1經(jīng)過對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相對模數(shù)n來說不應(yīng)過??;
•應(yīng)該或者加密密鑰大;或者被加密的信息m總是大而且m不能是一些已知值的乘積,后面一種情況可以在加密前對m填充隨機(jī)值實(shí)現(xiàn)。
•相關(guān)的消息不能用同樣的密鑰加密,加密前對消息進(jìn)行隨機(jī)值填充破壞消息之間的代數(shù)聯(lián)系及相關(guān)性,但是要注意填充算法的選擇;
•應(yīng)該使獲得對任意值的原始簽名不可能。
•被簽名的消息應(yīng)該與模數(shù)差不多大,而且不是一些已知值的乘積;
•使用平均解密時(shí)間和混亂(blinding)等方法使時(shí)間攻擊中使用的統(tǒng)計(jì)手段失效;
•如果有條件,采用規(guī)模差別比較大的質(zhì)因子p,q來提高系統(tǒng)的安全性;
2 RSA系統(tǒng)的參數(shù)選擇
RSA系統(tǒng)是第一個(gè)將安全性植基于因子分解的系統(tǒng)。很明顯地,在公開密鑰(e,N)中,若N能被因子分解,則在模N中所有元素價(jià)的最小公倍數(shù)(即所謂陷門)T=φ(N)=(p-1)(q-1)即無從隱藏。使得解密密鑰d不再是秘密,進(jìn)而整個(gè)RSA系統(tǒng)即不安全。雖然迄今人們尚無法“證明”,破解RSA系統(tǒng)等于因子分解。但一般“相信”RSA系統(tǒng)的安全性,等價(jià)于因子分解。即:若能分解因子N,即攻破RSA系統(tǒng);
若能攻破RSA系統(tǒng),即分解因子N(相信,但未證明)
因此,在使用RSA系統(tǒng)時(shí),對于公開密鑰N的選擇非常重要。必須使得公開N后,任何人無法從N得到T。此外,對于公開密鑰e與解密密鑰d,亦需有所限制。否則在使用上可能會導(dǎo)致RSA系統(tǒng)被攻破,或應(yīng)用在密碼協(xié)議上不安全。
經(jīng)過分析,我們知道RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系,X.931標(biāo)準(zhǔn)對此提出以下幾點(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ù)的長應(yīng)該為1024+256x,x=0,1• • • • • • ;
•質(zhì)數(shù)p,q應(yīng)通過質(zhì)數(shù)檢測,使出錯(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ù)字簽名
長期以來的日常生活中,對于重要的文件,為了防止對文件的否認(rèn),偽造,篡改等等的破壞,傳統(tǒng)的方法是在文件上手寫簽名。但是在計(jì)算機(jī)系統(tǒng)中無法使用手寫簽名,而代之對應(yīng)的數(shù)字簽名機(jī)制。數(shù)字簽名應(yīng)該能實(shí)現(xiàn)手寫簽名的作用,其本質(zhì)特征就是僅能利用簽名者的私有信息產(chǎn)生簽名。因此,當(dāng)它被驗(yàn)證時(shí),它也能被信任的第三方(如法官)在任一時(shí)刻證明只有私有信息的唯一掌握者才能產(chǎn)生此簽名。
數(shù)字簽名具有以下特點(diǎn):
•簽名是可信的;
•簽名是不能偽造的;
•簽名是不可重用的;
•簽名后的文件是不能更改的;
•簽名是不能否認(rèn)的。
由于非對稱密碼體制的特點(diǎn),對于數(shù)字簽名的實(shí)現(xiàn)比在對稱密碼體制下要有效和簡單的多。
2 RSA公鑰簽名技術(shù)
數(shù)字簽名可以用秘密密鑰利,也可用公開密鑰。但采用秘密密鑰是建立在有一個(gè)眾人信任的中間機(jī)構(gòu)的基礎(chǔ)上,而采用公鑰加密法進(jìn)行數(shù)字簽名則不受此限制,收發(fā)兩方之間不需要任何可信賴機(jī)構(gòu)。假定公開密鑰加密和解密算法除了滿足D(E(P))=P外,還能滿足E(D(P))=P(RSA滿足這兩個(gè)條件,所以這個(gè)假定并不是不現(xiàn)實(shí)的)。那么發(fā)方A就可以通過EB(DA(P))的轉(zhuǎn)換,將一條簽名的明文信息P發(fā)給收方B。注意,A知道自己的私有解密密鑰DA,還知道B的公開密鑰EB,所以建立這條信息的工作應(yīng)由A來做。
當(dāng)B收到這條消息后,他象往常一樣用自己的私有密鑰將它解密,得到DA(P),如圖所示。他將這條信息放在一個(gè)安全的地方,然后用EA解密,得到初始的明文。
要了解這種簽名是如何工作的,現(xiàn)在假設(shè)A后來否認(rèn)曾經(jīng)發(fā)送消息P給B。當(dāng)案子上了法庭,B能夠出示P和 DA(P)。法官只要使用一下EA,就能輕易地證明B確實(shí)有一條用DA加密的有效信息。由于B不知道A的私有密鑰,B能得到用它加密的唯一途徑就是A發(fā)送過來的。
需要說明的是,雖然使用公開密鑰加密法進(jìn)行數(shù)字簽名的是一個(gè)很好的方法,但仍有一些問題存在于它們所應(yīng)用的環(huán)境而不是算法。只有當(dāng)
DA保密時(shí),B才能證明某條信息是A發(fā)送來的。如果A公開了它的私有密鑰,那么證據(jù)就不成立了,因?yàn)槿魏稳税˙都可以發(fā)送這條消息。
網(wǎng)絡(luò)技術(shù)的發(fā)展使得,電子商務(wù)正在廣泛開展,電子郵件也被普遍使用,數(shù)字簽名技術(shù)越來越重要。RSA雖然有算法復(fù)雜,速度慢的缺點(diǎn),但目前還是被廣泛的應(yīng)用于數(shù)字簽名中。隨著計(jì)算機(jī)技術(shù)的發(fā)展及對RSA的深入研究,目前RSA正在走向?qū)嵱没?,商業(yè)化,可以預(yù)見在網(wǎng)絡(luò)安全中,基于RSA的網(wǎng)絡(luò)安全系統(tǒng)的設(shè)計(jì)將會廣泛使用。
RSA密碼系統(tǒng)是較早提出的一種公開鑰密碼系統(tǒng)。1978年,美國麻省理工學(xué)院(MIT)的Rivest,Shamir和Adleman在題為《獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法》的論文中提出了基于數(shù)論的非對稱(公開鑰)密碼體制,稱為RSA密碼體制。RSA是建立在“大整數(shù)的素因子分解是困難問題”基礎(chǔ)上的,是一種分組密碼體制。
介紹公鑰密碼體制(背景)
1、對稱密碼體制
對稱密碼體制是一種傳統(tǒng)密碼體制,也稱為私鑰密碼體制。在對稱加密系統(tǒng)中,加密和解密采用相同的密鑰。因?yàn)榧咏饷苊荑€相同,需要通信的雙方必須選擇和保存他們共同的密鑰,各方必須信任對方不會將密鑰泄密出去,這樣就可以實(shí)現(xiàn)數(shù)據(jù)的機(jī)密性和完整性。對于具有n個(gè)用戶的網(wǎng)絡(luò),需要n(n-1)/2個(gè)密鑰,在用戶群不是很大的情況下,對稱加密系統(tǒng)是有效的。但是對于大型網(wǎng)絡(luò),當(dāng)用戶群很大,分布很廣時(shí),密鑰的分配和保存就成了問題。對機(jī)密信息進(jìn)行加密和驗(yàn)證隨報(bào)文一起發(fā)送報(bào)文摘要(或散列值)來實(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)由美國國家標(biāo)準(zhǔn)局提出,主要應(yīng)用于銀行業(yè)的電子資金轉(zhuǎn)帳(EFT)領(lǐng)域。DES的密鑰長度為56bit。Triple DES使用兩個(gè)獨(dú)立的56bit密鑰對交換的信息進(jìn)行3次加密,從而使其有效長度達(dá)到112bit。RC2和RC4方法是RSA數(shù)據(jù)安全公司的對稱加密專利算法,它們采用可變密鑰長度的算法。通過規(guī)定不同的密鑰長度,,C2和RC4能夠提高或降低安全的程度。對稱密碼算法的優(yōu)點(diǎn)是計(jì)算開銷小,加密速度快,是目前用于信息加密的主要算法。它的局限性在于它存在著通信的貿(mào)易雙方之間確保密鑰安全交換的問題。此外,某一貿(mào)易方有幾個(gè)貿(mào)易關(guān)系,他就要維護(hù)幾個(gè)專用密鑰。它也沒法鑒別貿(mào)易發(fā)起方或貿(mào)易最終方,因?yàn)橘Q(mào)易的雙方的密鑰相同。另外,由于對稱加密系統(tǒng)僅能用于對數(shù)據(jù)進(jìn)行加解密處理,提供數(shù)據(jù)的機(jī)密性,不能用于數(shù)字簽名。因而人們迫切需要尋找新的密碼體制。
2、非對稱密碼體制
非對稱密碼體制也叫公鑰加密技術(shù),該技術(shù)就是針對私鑰密碼體制的缺陷被提出來的。在公鑰加密系統(tǒng)中,加密和解密是相對獨(dú)立的,加密和解密會使用兩把不同的密鑰,加密密鑰(公開密鑰)向公眾公開,誰都可以使用,解密密鑰(秘密密鑰)只有解密人自己知道,非法使用者根據(jù)公開的加密密鑰無法推算出解密密鑰,顧其可稱為公鑰密碼體制。如果一個(gè)人選擇并公布了他的公鑰,另外任何人都可以用這一公鑰來加密傳送給那個(gè)人的消息。私鑰是秘密保存的,只有私鑰的所有者才能利用私鑰對密文進(jìn)行解密。公鑰密碼體制的算法中最著名的代表是RSA系統(tǒng),此外還有:背包密碼、McEliece密碼、Diffe_Hellman、Rabin、零知識證明、橢圓曲線、EIGamal算法等。公鑰密鑰的密鑰管理比較簡單,并且可以方便的實(shí)現(xiàn)數(shù)字簽名和驗(yàn)證。但算法復(fù)雜,加密數(shù)據(jù)的速率較低。公鑰加密系統(tǒng)不存在對稱加密系統(tǒng)中密鑰的分配和保存問題,對于具有n個(gè)用戶的網(wǎng)絡(luò),僅需要2n個(gè)密鑰。公鑰加密系統(tǒng)除了用于數(shù)據(jù)加密外,還可用于數(shù)字簽名。公鑰加密系統(tǒng)可提供以下功能:A、機(jī)密性(Confidentiality):保證非授權(quán)人員不能非法獲取信息,通過數(shù)據(jù)加密來實(shí)現(xiàn);B、確認(rèn)(Authentication):保證對方屬于所聲稱的實(shí)體,通過數(shù)字簽名來實(shí)現(xiàn);C、數(shù)據(jù)完整性(Data integrity):保證信息內(nèi)容不被篡改,入侵者不可能用假消息代替合法消息,通過數(shù)字簽名來實(shí)現(xiàn);D、不可抵賴性(Nonrepudiation):發(fā)送者不可能事后否認(rèn)他發(fā)送過消息,消息的接受者可以向中立的第三方證實(shí)所指的發(fā)送者確實(shí)發(fā)出了消息,通過數(shù)字簽名來實(shí)現(xiàn)。可見公鑰加密系統(tǒng)滿足信息安全的所有主要目標(biāo)。
RSA公鑰密碼體制的優(yōu)勢(意義)
1 解決大規(guī)模網(wǎng)絡(luò)應(yīng)用中密鑰的分發(fā)和管理問題
采用分組密碼、序列密碼等對稱密碼體制時(shí),加解密雙方所用的密鑰都是秘密的,而且需要定期更換,新的密鑰總是要通過某種秘密渠道分配給使用方,在傳遞的過程中,稍有不慎,就容易泄露。
公鑰密碼加密密鑰通常是公開的,而解密密鑰是秘密的,由用戶自己保存,不需要往返交換和傳遞,大大減少了密鑰泄露的危險(xiǎn)性。同時(shí),在網(wǎng)絡(luò)通信中使用對稱密碼體制時(shí),網(wǎng)絡(luò)內(nèi)任何兩個(gè)用戶都需要使用互不相同的密鑰,只有這樣,才能保證不被第三方竊聽,因而N個(gè)用戶就要使用N(N–1)/2個(gè)密鑰。在大型網(wǎng)絡(luò)中,如果有100萬個(gè)用戶,則要使用4950萬個(gè)密鑰,密鑰量太大,難以管理,而且使用起來非常麻煩。采用公鑰密碼體制,N個(gè)用戶只需要產(chǎn)生N對密鑰。仍以100萬個(gè)用戶為例,只需100萬對密鑰,需要秘密保存的僅100萬個(gè)私鑰,二者相差近50倍,數(shù)量大大減少,而且分發(fā)簡單,安全性好。由此可見,只有公鑰密碼才能方便、可靠地解決大規(guī)模網(wǎng)絡(luò)應(yīng)用中密鑰的分發(fā)和管理問題。
2 實(shí)現(xiàn)網(wǎng)絡(luò)中的數(shù)字簽名機(jī)制
對稱密鑰技術(shù)由于其自身的局限性,無法提供網(wǎng)絡(luò)中的數(shù)字簽名。這是因?yàn)閿?shù)字簽名是網(wǎng)絡(luò)中表征人或機(jī)構(gòu)的真實(shí)性的重要手段,數(shù)字簽名的數(shù)據(jù)需要有惟一性、私有性,而對稱密鑰技術(shù)中的密鑰至少需要在交互雙方之間共享,因此,不滿足惟一性、私有性,無法用做網(wǎng)絡(luò)中的數(shù)字簽名。相比之下,公鑰密碼技術(shù)由于存在一對公鑰和私鑰,私鑰可以表征惟一性和私有性,而且經(jīng)私鑰加密的數(shù)據(jù)只能用與之對應(yīng)的公鑰來驗(yàn)證,其他人無法仿冒,所以,可以用做網(wǎng)絡(luò)中的數(shù)字簽名服務(wù)。
具體而言,一段消息以發(fā)送方的私鑰加密之后,任何擁有與該私鑰相對應(yīng)的公鑰的人均可將它解密。由于該私鑰只有發(fā)送方擁有,且該私鑰是密藏不公開的,所以,以該私鑰加密的信息可看做發(fā)送方對該信息的簽名,其作用和現(xiàn)實(shí)中的手工簽名一樣有效而且具有不可抵賴性。
一種具體的做法是:認(rèn)證服務(wù)器和用戶各持有自己的證書,用戶端將一個(gè)隨機(jī)數(shù)用自己的私鑰簽名后和證書一起用服務(wù)器的公鑰加密后傳輸?shù)椒?wù)器;使用服務(wù)器的公鑰加密保證了只有認(rèn)證服務(wù)器才能進(jìn)行解密,使用用戶的密鑰簽名保證了數(shù)據(jù)是由該用戶發(fā)出;服務(wù)器收到用戶端數(shù)據(jù)后,首先用自己的私鑰解密,取出用戶的證書后,使用用戶的公鑰進(jìn)行解密,若成功,則到用戶數(shù)據(jù)庫中檢索該用戶及其權(quán)限信息,將認(rèn)證成功的信息和用戶端傳來的隨機(jī)數(shù)用服務(wù)器的私鑰簽名后,使用用戶的公鑰進(jìn)行加密,然后,傳回給用戶端,用戶端解密后即可得到認(rèn)證成功的信息。
介紹RSA公鑰密碼體制
RSA是Rivest,Shamir,Adleman提出基于數(shù)論的非對稱密鑰體制。RSA是建立在大整數(shù)分解的困難上的,是一種分組密碼體制。它是以推廣的歐拉定理為基礎(chǔ)的(見下):
定理1 若(a,n)=1, 則 =(mod n) ,其中φ(n) 表示不超過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為公開加密密鑰,由e求出秘密解密密鑰d:d • e= 1 mod φ(n)= k
'φ(n) +1
•加密/解密:
將明文分成長度小于 位的明文塊m,
加密過程是:c = E(m,e) = mod n
解密過程是: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, 收方只有用對應(yīng)的e "解密"
才能知道明文, 同時(shí)也驗(yàn)證了發(fā)方的身份。
RSA公鑰密碼體制的安全性分析
RSA的安全性依賴于大整數(shù)的因式分解問題。實(shí)際上,人們推測RSA的安全性依賴于大整數(shù)的因式分解問題,但誰也沒有在數(shù)學(xué)上證明從c和e計(jì)算m需要對n進(jìn)行因式分解。可以想象可能會有完全不同的方式去分析RSA。然而,如果這種方法能讓密碼解析員推導(dǎo)出d,則它也可以用作大整數(shù)因式分解的新方法。最難以令人置信的是,有些RSA變體已經(jīng)被證明與因式分解同樣困難。甚至從RSA加密的密文中恢復(fù)出某些特定的位也與解密整個(gè)消息同樣困難。另外,對RSA的具體實(shí)現(xiàn)存在一些針對協(xié)議而不是針對基本算法的攻擊方法。
攻擊者對RSA系統(tǒng)攻擊的目標(biāo)可以分為三類:
設(shè)計(jì)RSA系統(tǒng)的注意事項(xiàng)
1經(jīng)過對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相對模數(shù)n來說不應(yīng)過??;
•應(yīng)該或者加密密鑰大;或者被加密的信息m總是大而且m不能是一些已知值的乘積,后面一種情況可以在加密前對m填充隨機(jī)值實(shí)現(xiàn)。
•相關(guān)的消息不能用同樣的密鑰加密,加密前對消息進(jìn)行隨機(jī)值填充破壞消息之間的代數(shù)聯(lián)系及相關(guān)性,但是要注意填充算法的選擇;
•應(yīng)該使獲得對任意值的原始簽名不可能。
•被簽名的消息應(yīng)該與模數(shù)差不多大,而且不是一些已知值的乘積;
•使用平均解密時(shí)間和混亂(blinding)等方法使時(shí)間攻擊中使用的統(tǒng)計(jì)手段失效;
•如果有條件,采用規(guī)模差別比較大的質(zhì)因子p,q來提高系統(tǒng)的安全性;
2 RSA系統(tǒng)的參數(shù)選擇
RSA系統(tǒng)是第一個(gè)將安全性植基于因子分解的系統(tǒng)。很明顯地,在公開密鑰(e,N)中,若N能被因子分解,則在模N中所有元素價(jià)的最小公倍數(shù)(即所謂陷門)T=φ(N)=(p-1)(q-1)即無從隱藏。使得解密密鑰d不再是秘密,進(jìn)而整個(gè)RSA系統(tǒng)即不安全。雖然迄今人們尚無法“證明”,破解RSA系統(tǒng)等于因子分解。但一般“相信”RSA系統(tǒng)的安全性,等價(jià)于因子分解。即:若能分解因子N,即攻破RSA系統(tǒng);
若能攻破RSA系統(tǒng),即分解因子N(相信,但未證明)
因此,在使用RSA系統(tǒng)時(shí),對于公開密鑰N的選擇非常重要。必須使得公開N后,任何人無法從N得到T。此外,對于公開密鑰e與解密密鑰d,亦需有所限制。否則在使用上可能會導(dǎo)致RSA系統(tǒng)被攻破,或應(yīng)用在密碼協(xié)議上不安全。
經(jīng)過分析,我們知道RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系,X.931標(biāo)準(zhǔn)對此提出以下幾點(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ù)的長應(yīng)該為1024+256x,x=0,1• • • • • • ;
•質(zhì)數(shù)p,q應(yīng)通過質(zhì)數(shù)檢測,使出錯(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ù)字簽名
長期以來的日常生活中,對于重要的文件,為了防止對文件的否認(rèn),偽造,篡改等等的破壞,傳統(tǒng)的方法是在文件上手寫簽名。但是在計(jì)算機(jī)系統(tǒng)中無法使用手寫簽名,而代之對應(yīng)的數(shù)字簽名機(jī)制。數(shù)字簽名應(yīng)該能實(shí)現(xiàn)手寫簽名的作用,其本質(zhì)特征就是僅能利用簽名者的私有信息產(chǎn)生簽名。因此,當(dāng)它被驗(yàn)證時(shí),它也能被信任的第三方(如法官)在任一時(shí)刻證明只有私有信息的唯一掌握者才能產(chǎn)生此簽名。
數(shù)字簽名具有以下特點(diǎn):
•簽名是可信的;
•簽名是不能偽造的;
•簽名是不可重用的;
•簽名后的文件是不能更改的;
•簽名是不能否認(rèn)的。
由于非對稱密碼體制的特點(diǎn),對于數(shù)字簽名的實(shí)現(xiàn)比在對稱密碼體制下要有效和簡單的多。
2 RSA公鑰簽名技術(shù)
數(shù)字簽名可以用秘密密鑰利,也可用公開密鑰。但采用秘密密鑰是建立在有一個(gè)眾人信任的中間機(jī)構(gòu)的基礎(chǔ)上,而采用公鑰加密法進(jìn)行數(shù)字簽名則不受此限制,收發(fā)兩方之間不需要任何可信賴機(jī)構(gòu)。假定公開密鑰加密和解密算法除了滿足D(E(P))=P外,還能滿足E(D(P))=P(RSA滿足這兩個(gè)條件,所以這個(gè)假定并不是不現(xiàn)實(shí)的)。那么發(fā)方A就可以通過EB(DA(P))的轉(zhuǎn)換,將一條簽名的明文信息P發(fā)給收方B。注意,A知道自己的私有解密密鑰DA,還知道B的公開密鑰EB,所以建立這條信息的工作應(yīng)由A來做。
當(dāng)B收到這條消息后,他象往常一樣用自己的私有密鑰將它解密,得到DA(P),如圖所示。他將這條信息放在一個(gè)安全的地方,然后用EA解密,得到初始的明文。
要了解這種簽名是如何工作的,現(xiàn)在假設(shè)A后來否認(rèn)曾經(jīng)發(fā)送消息P給B。當(dāng)案子上了法庭,B能夠出示P和 DA(P)。法官只要使用一下EA,就能輕易地證明B確實(shí)有一條用DA加密的有效信息。由于B不知道A的私有密鑰,B能得到用它加密的唯一途徑就是A發(fā)送過來的。
需要說明的是,雖然使用公開密鑰加密法進(jìn)行數(shù)字簽名的是一個(gè)很好的方法,但仍有一些問題存在于它們所應(yīng)用的環(huán)境而不是算法。只有當(dāng)
DA保密時(shí),B才能證明某條信息是A發(fā)送來的。如果A公開了它的私有密鑰,那么證據(jù)就不成立了,因?yàn)槿魏稳税˙都可以發(fā)送這條消息。
網(wǎng)絡(luò)技術(shù)的發(fā)展使得,電子商務(wù)正在廣泛開展,電子郵件也被普遍使用,數(shù)字簽名技術(shù)越來越重要。RSA雖然有算法復(fù)雜,速度慢的缺點(diǎn),但目前還是被廣泛的應(yīng)用于數(shù)字簽名中。隨著計(jì)算機(jī)技術(shù)的發(fā)展及對RSA的深入研究,目前RSA正在走向?qū)嵱没?,商業(yè)化,可以預(yù)見在網(wǎng)絡(luò)安全中,基于RSA的網(wǎng)絡(luò)安全系統(tǒng)的設(shè)計(jì)將會廣泛使用。
您可能感興趣的文章:
- c# rsa注冊實(shí)現(xiàn)加密文字
- java加密算法分享(rsa解密、對稱加密、md5加密)
- 使用openssl實(shí)現(xiàn)rsa非對稱加密算法示例
- python使用rsa加密算法模塊模擬新浪微博登錄
- rsa加密算法使用示例分享
- 在ASP.Net中實(shí)現(xiàn)RSA加密的方法
- android md5加密與rsa加解密實(shí)現(xiàn)代碼
- PHP+JS+rsa數(shù)據(jù)加密傳輸實(shí)現(xiàn)代碼
- 關(guān)于firefox的ElementTraversal 接口 使用說明
- 在asp中通過vbs類實(shí)現(xiàn)rsa加密與解密的代碼
- 基于私鑰加密公鑰解密的RSA算法C#實(shí)現(xiàn)方法
相關(guān)文章
為什么經(jīng)常被網(wǎng)絡(luò)入侵?探究原因
為什么經(jīng)常被網(wǎng)絡(luò)入侵?探究原因...2007-01-01關(guān)于oblog、動易、風(fēng)訊等擁有源碼編輯的程序漏洞淺析
這篇文章主要介紹了關(guān)于oblog、動易、風(fēng)訊等擁有源碼編輯的程序漏洞淺析2007-01-01基于DoS攻擊的隨機(jī)數(shù)據(jù)包標(biāo)記源跟蹤算法
基于DoS攻擊的隨機(jī)數(shù)據(jù)包標(biāo)記源跟蹤算法...2007-01-01