新編密碼學(xué) 課件 第7章 公鑰密碼

7.1公鑰密碼體制的基本原理

7.2背包算法

7.3RSA算法

7.4Rabin算法

7.5ElGamal算法

7.6橢圓曲線密碼

7.7SM2公鑰加密算法

7.8基于身份的公鑰密碼體制7.1公鑰密碼體制的基本原理7.1.1公鑰密碼的基本思想運用DES等經(jīng)典密碼系統(tǒng)進行保密通信時,通信雙方必須擁有一個共享的秘密密鑰來實現(xiàn)對消息的加密和解密,而密鑰具有的機密性使得通信雙方如何獲得一個共同的密鑰變得非常困難。通常采用人工傳送的方式分配各方所需的共享密鑰,或借助一個可靠的密鑰分配中心來分配所需的共享密鑰。但在具體實現(xiàn)過程中,這兩種方式都面臨很多困難,尤其在計算機網(wǎng)絡(luò)化時代更為困難。1976年,兩位美國密碼學(xué)者W.Diffie和M.Hellman在該年度的美國國家計算機會議上提交了一篇名為“NewDirectionsinCryptography”(《密碼學(xué)的新方向》)的論文。文中首次提出公鑰密碼體制的新思想,為解決傳統(tǒng)經(jīng)典密碼學(xué)中面臨的諸多難題提供了一個新的思路。其基本思想是把密鑰分成兩個部分———公開密鑰(簡稱公鑰)和私有密鑰(簡稱私鑰),分別用于消息的加密和解密。公鑰密碼體制又稱為雙鑰密碼體制、非對稱密碼體制,與之對應(yīng),傳統(tǒng)的經(jīng)典密碼體制又稱為單鑰密碼體制、對稱密碼體制。公鑰密碼體制中的公開密鑰可被記錄在一個公共數(shù)據(jù)庫里,或者以某種可信的方式公開發(fā)放,而私有密鑰必須由持有者妥善、秘密地保存。這樣,任何人都可以通過某種公開的途徑獲得一個用戶的公開密鑰,然后與其進行保密通信,而解密者只能是那些知道相應(yīng)私鑰的密鑰持有者。用戶公鑰的這種公開性使得公鑰體制的密鑰分配變得非常簡單,目前常以公鑰證書的形式發(fā)放和傳遞用戶公鑰,而私鑰的保密專用性決定了它不存在分配的問題(但需要用公鑰來驗證它的真實性,以防止欺騙)。公鑰密碼算法的最大特點是采用兩個具有一一對應(yīng)關(guān)系的密鑰對k=(ps,sk)來分離加密和解密過程。當(dāng)兩個用戶希望借助公鑰體制進行保密通信時,發(fā)信方Alice用收信方Bob的公開密鑰pk加密消息并發(fā)送給接收方;而收信方Bob使用與公鑰相對應(yīng)的私鑰sk進行解密。根據(jù)公私鑰之間嚴格的一一對應(yīng)關(guān)系,只有與加密時所用公鑰相對應(yīng)的用戶私鑰才能正確解密,從而恢復(fù)出正確的明文。由于這個私鑰是通信中的收信方獨有的,其他用戶不可能知道,所以只有收信方Bob能正確恢復(fù)出明文消息,其他有意或無意獲得消息密文的用戶都不能解密出正確的明文,從而達到了保密通信的目的。圖7-1給出了公鑰密碼體制用于消息加、解密的基本流程。7.1.2公鑰密碼算法應(yīng)滿足的要求基于圖71給出的公鑰密碼體制加密、解密的基本流程,一個實際可用的公鑰密碼體制(M,C,K,E,D)的基本要求包括:(1)對于K中的每一個公私鑰對k=(pk,sk),都存在E中的一個加密變換Epk:M→C和D中的一個解密變換Dsk:C→M,使得任意明文消息m∈M都能找到一個唯一的c∈C滿足c=Epk[m],且m=Dsk[c]=Dsk[Epk[m]]。(2)對于任意的公私鑰對k=(pk,sk)∈K,加密變換Epk和解密變換Dsk都是多項式時間可計算的函數(shù),但由加密變換Epk推出解密變換Dsk在計算上是不可行的,或者說,在知道公鑰pk的情況下推知私鑰sk在計算上是不可行的。由上面的基本要求可以看出,公鑰密碼體制的核心在于加密變換與解密變換的設(shè)計。在密碼算法中,加解密變換是互逆的,但條件(2)說明在公鑰密碼體制中加解密變換不能簡單地直接互推。上述條件表明公鑰密碼體制的加解密變換類似于陷門單向函數(shù)的運算,因此可以利用陷門單向函數(shù)來構(gòu)造公鑰密碼體制。陷門單向函數(shù)是一個可逆函數(shù)f(x)。對于定義域中的任何x,函數(shù)值y=f(x)都是容易計算的;但對幾乎所有的x,要由y=f(x)求出x在計算上不可行(即使已經(jīng)知道函數(shù)f(x)),除非知道某些輔助信息(稱為陷門信息)。這里所說的“容易計算”是指函數(shù)值能在其輸入長度的多項式時間內(nèi)計算出來。例如,若輸入長度為n位,求函數(shù)值的計算時間是na(這里a是一個固定常數(shù))的某個倍數(shù),則稱此函數(shù)是容易計算的,否則就是不可行的。針對公鑰密碼體制(M,C,K,E,D)的基本要求,一個可行的公鑰密碼算法應(yīng)該滿足如下要求:(1)收信方Bob產(chǎn)生密鑰對k=(pkB,skB)在計算上是容易的。(2)發(fā)信方Alice用收信方Bob的公鑰pkB

加密消息m產(chǎn)生密文c=EpkB[m]在計算上是容易的。(3)收信方Bob用自己的私鑰skB

解密密文c,還原明文消息m=DskB[c]在計算上是容易的。(4)不僅攻擊者由密文c和Bob的公鑰pkB

恢復(fù)明文m在計算上是不可行的,而且攻擊者由Bob的公鑰pkB

求解對應(yīng)的私鑰skB

在計算上也是不可行的。(5)一般情況下,加解密的次序可交換,即DskB[EpkB[m]]=EpkB[DskB[m]]。公鑰密碼體制的思想完全不同于單鑰密碼體制。公鑰密碼算法的基本操作不再是單鑰密碼體制中使用的替換和置換。公鑰密碼體制通常將其安全性建立在某個尚未解決(且尚未證實能否有效解決)的數(shù)學(xué)難題的基礎(chǔ)上,并經(jīng)過精心設(shè)計來保證其具有非常高的安全性。公鑰密碼算法以非對稱的形式使用兩個密鑰,不僅在實現(xiàn)消息加解密基本功能的同時簡化了密鑰分配任務(wù),而且對密鑰協(xié)商與密鑰管理、數(shù)字簽名與身份認證等密碼學(xué)問題產(chǎn)生了深刻的影響?？梢哉f,公鑰密碼思想為密碼學(xué)的發(fā)展提供了新的理論和技術(shù)基礎(chǔ),是密碼學(xué)發(fā)展史上的一次革命。7.2背包算法7.2.1背包問題在組合數(shù)學(xué)中有一個背包問題:假設(shè)有一堆物品,體積各不相同,能否從這堆物品中找出幾個正好裝滿一個給定容量的背包(假定物品之間不留空隙)?記物品的體積分別為v1,v2,…,vn,背包的容量為C,則背包問題可表示為其中,bi(i=1,2,…,n)等于1或者0,bi=1表示第i個物品在背包中,bi=0表示第i個物品不在背包中;物品體積的序列(v1,v2,…,vn)稱為背包向量。理論上講,通過檢查背包向量V的所有子集,計算出每個子集的元素之和,總能找出一個子集作為背包問題的解,因此背包問題又稱為子集和問題。然而長度為n的背包向量V的全體子集共有2n

個,當(dāng)n很大時,對全部2n

個子集進行窮舉搜索是不可能的。事實上,背包問題是一類NPC問題,而目前還沒有發(fā)現(xiàn)比窮舉搜索更好的NPC問題求解方法。幸運的是,并非所有的背包問題都沒有有效算法,有一類特殊的背包問題是容易求解的,這就是超遞增背包問題。即V中每一項都大于它前面所有項之和,則稱V是一個超遞增向量,或者稱序列v1,v2,…,vn是一個超遞增序列,以V為背包向量的背包問題稱作超遞增背包問題。例如,序列1,2,4,…,2n就是一個超遞增序列。超遞增背包問題的解很容易通過以下過程找到:設(shè)背包容量為C,從右向左(從大到小)依次檢查超遞增背包向量V中的每個元素,以確定問題的解。若C≥vn,則vn在解中,對應(yīng)的bn應(yīng)為1,并將C的值更新為C-vn;若C<vn,則vn不在解中,對應(yīng)的bn應(yīng)為0,C的值保持不變。然后對vn-1,vn-2,…,v2,v1依次重復(fù)上述過程,并判斷C是否減少到0。若C最終變成0,則問題的解存在,否則解不存在。7.2.2背包算法的描述借助背包問題中的超遞增向量和相應(yīng)的非超遞增向量,可以構(gòu)造一個公鑰

密

碼

算法———背包密碼算法。背包算法的描述如下:私有密鑰設(shè)置為將一個超遞增向量V轉(zhuǎn)換為非超遞增向量U的參數(shù)t、t-1和k,公開密鑰設(shè)置為非超遞增向量U。加密變換:首先將二進制明文消息劃分成長度與非超遞增向量U長度相等的明文分組b1b2…bn;然后計算明文分組向量B=(b1,b2,…,bn)與非超遞增向量U=(u1,u2,…,un)的內(nèi)積B·U=b1u1+b2u2+…+bnun,所得結(jié)果為密文。解密變換:先還原出超遞增背包向量V=t-1Umodk≡t-1tVmodk,再將密文B·U模k乘以t-1的結(jié)果作為超遞增背包問題的背包容量,求解超遞增背包問題,得到消息明文。7.2.3背包算法的安全性背包算法利用難解的一般背包問題作為公開密鑰,可以方便地對明文進行加密;而私有密鑰則利用易解的超遞增背包問題給出一個解密的簡單方法。那些不知道私鑰的攻擊者要想破譯密文就不得不求解一個困難的背包問題,這在計算上看似是不可行的。背包算法提出兩年后即被破解。破解的基本思想是不必找出真正的模數(shù)k和乘數(shù)t,也不用窮舉搜索背包向量的所有子集,而是找出一對任意的k'和t',使得用公開的背包向量U模k'乘t'后能得到一個超遞增向量。究其原因是Merkle-Hellman背包體制的公開密鑰是由超遞增向量變換而來的,雖然經(jīng)過模乘置換,但超遞增向量內(nèi)在的規(guī)律性并不能完全被隱藏,這就給攻擊者留下了可乘之機。隨后Merkle又提出了多次迭代背包體制,但最終也被破解。1984年,Brickell最終證明了Merkle-Hellman背包體制的不安全性,并發(fā)現(xiàn)了一種可將難解的背包問題轉(zhuǎn)化為易解的背包問題的算法。背包算法是第一個使公鑰密碼體制成為現(xiàn)實的密碼算法,它說明了如何將數(shù)學(xué)難題應(yīng)用于公鑰密碼算法的設(shè)計。背包體制的優(yōu)勢是加解密速度很快,但它存在的不安全性使其不能用于商業(yè)目的。7.3RSA算法數(shù)論里有一個大數(shù)分解問題:計算兩個素數(shù)的乘積非常容易,但分解該乘積卻異常困難,特別是在這兩個素數(shù)都很大的情況下。基于這個事實,1978年,美國MIT(麻省理工學(xué)院)的三名數(shù)學(xué)家R.Rivest、A.Shamir和L.Adleman提出了著名的公鑰密碼體制———RSA公鑰算法。該算法基于指數(shù)加密概念,以兩個大素數(shù)的乘積作為算法的公鑰來加密消息,而密文的解密必須知道相應(yīng)的兩個大素數(shù)。迄今為止,RSA公鑰算法是思想最簡單、分析最透徹、應(yīng)用最廣泛的公鑰密碼體制。RSA算法非常容易理解和實現(xiàn),經(jīng)受住了密碼分析,密碼分析者既不能證明也不能否定它的安全性,這恰恰說明了RSA具有一定的可信度。7.3.1RSA算法的描述基于大數(shù)分解問題,為了產(chǎn)生公私鑰,首先獨立地選取兩個大素數(shù)p和q(注:為了獲得最大程度的安全性,選取的p和q的長度應(yīng)該差不多,都應(yīng)為長度在100位以上的十進制數(shù)字),計算這里φ(n)表示n的歐拉函數(shù),即φ(n)為比n小且與n互素的正整數(shù)的個數(shù)。隨機選取一個滿足1<e<φ(n)且gcd(e,φ(n))=1的整數(shù)e,那么e存在模φ(n)下的乘法逆元d≡e-1modφ(n),d可由擴展的歐幾里得算法求得。這樣我們由p和q獲得了3個參數(shù)n,e,d。在RSA算法里,以n和e作為公鑰,d作為私鑰(注:不再需要p和q,可以銷毀,但一定不能泄露)。具體的加解密過程如下所示。加密變換:先將消息劃分成數(shù)值小于n的一系列數(shù)據(jù)分組,即以二進制表示的每個數(shù)據(jù)分組的位長應(yīng)小于lbn。然后對每個明文分組m進行加密變換,得到密文c,即解密變換:m≡cdmodn。命題7.1RSA算法中的解密變換m≡cdmodn是正確的。證明

由數(shù)論中的歐拉定理知,如果兩個整數(shù)a和b互素,那么aφ(b)≡1modb。

在RSA算法中，明文m至少與兩個素數(shù)p和q中的一個互素。不然的話，若m與p和q都不互素，那么m既是p的倍數(shù)，也是q的倍數(shù)，于是m也是n的倍數(shù)，這與m<n矛盾。由de≡1modg(n)可知，存在整數(shù)k，使得de=kφ(n)+1。下面分兩種情形討論:情形一,m僅與p,q二者之一互素,不妨假設(shè)m與p互素且與q不互素,那么存在整數(shù)a,使得m=aq,由歐拉定理可知于是存在一個整數(shù)t,使得

兩邊同時乘以m=aq,得到由此得情形二,如果m與p和q都互素,那么m也和n互素,有RSA算法實質(zhì)上是一種單表代換系統(tǒng)。給定模數(shù)n和合法的明文m,其相應(yīng)的密文為c≡memodn,且對于m'≠m,必有c'≠c。RSA算法的關(guān)鍵在于:當(dāng)n極大時,在不知道陷門信息的情況下,很難確定明文和密文之間的對應(yīng)關(guān)系。7.3.2RSA算法的安全性RSA算法的安全性完全依賴于對大數(shù)分解問題的困難性的推測,但面臨的問題是迄今為止還沒有證明大數(shù)分解問題是一類NP問題。為了抵抗窮舉攻擊,RSA算法采用了大密鑰空間,通常模數(shù)n取值很大,e和d也取非常大的自然數(shù),但這樣做的一個明顯缺點是密鑰產(chǎn)生和加解密過程都非常復(fù)雜,系統(tǒng)運行速度比較慢。與其他密碼體制一樣,嘗試破解每一個可能的d是不現(xiàn)實的,那么分解模數(shù)n就成為最直接的攻擊方法。只要能夠分解n就可以求出φ(n),然后通過擴展的歐幾里得算法可以求得加密指數(shù)e模φ(n)的逆d,從而達到破解的目的。目前還沒有找到分解大整數(shù)的有效方法,但隨著計算能力的不斷提高和計算成本的不斷降低,許多被認為不可能分解的大整數(shù)已被成功分解。例如,模數(shù)為129位十進制數(shù)字的RSA-129已于1994年4月在Internet上通過分布式計算被成功分解出一個64位和一個65位的因子。更困難的RSA-130也于1996年被分解出來,緊接著RSA-154也被分解,據(jù)報道,158位的十進制整數(shù)也已被分解,這意味著512位模數(shù)的RSA已經(jīng)不安全了。更嚴重的安全威脅來自于大數(shù)分解算法的改進和新算法的不斷提出。當(dāng)年破解RSA-129采用的是二次篩法,而破解RSA-130使用的算法為推廣的數(shù)域篩法,該算法使破解RSA-130的計算量僅比破解RSA-129多10%。盡管如此,密碼專家認為一定時期內(nèi)1024~2048位模數(shù)的RSA還是相對安全的。除了對RSA算法本身的攻擊外,RSA算法還面臨著攻擊者對密碼協(xié)議的攻擊,即利用RSA算法的某些特性和實現(xiàn)過程對其進行攻擊。下面介紹一些攻擊方法。1.共用模數(shù)攻擊在RSA的實現(xiàn)中,如果多個用戶選用相同的模數(shù)n,但有不同的加解密指數(shù)e和d,這樣做會使算法運行更簡單,卻是不安全的。假設(shè)一個消息用兩個不同的加密指數(shù)加密且共用同一個模數(shù),如果這兩個加密指數(shù)互素(一般情況下都這樣),則不需要知道解密指數(shù),任何一個加密指數(shù)都可以恢復(fù)明文,理由如下所示。設(shè)e1和e2是兩個互素的加密密鑰,共用的模數(shù)為n。對同一個明文消息m加密得到c1≡me1modn和c2≡me2modn。攻擊者知道n,e1,e2,c1和c2,可以用如下方法恢復(fù)出明文m:由于e1和e2互素,因此由擴展的歐幾里得算法可找到滿足re1+se2=1的r和s,由此可得明文消息m被恢復(fù)出來。注意:r和s必有一個為負整數(shù),上述計算需要用擴展的歐幾里得算法算出c1或者c2在模n下的逆。2.低加密指數(shù)攻擊較小的加密指數(shù)e可以加快消息加密的速度,但e太小會影響RSA系統(tǒng)的安全性。在多個用戶采用相同的加密密鑰e和不同的模數(shù)n的情況下,如果將同一個消息(或者一組線性相關(guān)的消息)分別用這些用戶的公鑰加密,那么利用中國剩余定理可以恢復(fù)出明文。舉例來說,取e=3,3個用戶的不同模數(shù)分別是n1,n2和n3,將消息x用這3組密鑰分別加密,得到一般來講,應(yīng)使n1,n2和n3互素。根據(jù)中國剩余定理,可由y1,y2和y3求出由于x<n1,x<n2,x<n3,所以已經(jīng)證明,只要k>e(e+1)/2,將k個線性相關(guān)的消息分別使用k個加密指數(shù)相同而模數(shù)不同的加密鑰加密,則低加密指數(shù)攻擊能夠奏效;如果消息完全相同,那么e個加密鑰就夠了。因此,為了抵抗這種攻擊,加密指數(shù)e必須足夠大。對于較短的消息,則要進行獨立的隨機數(shù)填充,破壞明文消息的相關(guān)性,以防止低加密指數(shù)攻擊。3.中間相遇攻擊指數(shù)運算具有可乘性,這種可乘性有可能導(dǎo)致其他方式的攻擊。事實上,如果明文m可以被分解成兩項之積m=m1×m2,那么這意味著明文的分解可導(dǎo)致密文的分解,明文分解容易使得密文分解也容易。密文分解容易導(dǎo)致中間相遇攻擊,攻擊方法描述如下:假設(shè)

攻擊者知道m(xù)是一個合數(shù),且滿足

和m2

都小于那么由RSA的可乘性,有攻擊者可以先創(chuàng)建一個有序的序列國際電信聯(lián)盟的實質(zhì)性工作由國際電信聯(lián)盟標(biāo)準(zhǔn)化部門(ITU)、國際電信聯(lián)盟無線電通信部門和國際電信聯(lián)盟電信發(fā)展部門這三大部門承擔(dān)。其中國際電信聯(lián)盟標(biāo)準(zhǔn)化部門由原來的國際電報電話咨詢委員會(CCITT)和國際無線電咨詢委員會(CCIR)的標(biāo)準(zhǔn)化工作部門合并而成，主要職責(zé)是實現(xiàn)國際電信聯(lián)盟有關(guān)電信標(biāo)準(zhǔn)化的目標(biāo)，使全世界的電信完成標(biāo)準(zhǔn)化。ITU目前已制定了2024項國際標(biāo)準(zhǔn)。ITU的目標(biāo)和任務(wù)是：維持和發(fā)展國際合作，以改進和合理利用電信；促進技術(shù)設(shè)施的發(fā)展及其有效運用，以提高電信業(yè)務(wù)的效率；擴大技術(shù)設(shè)施的用途，并盡可能使之得到廣泛應(yīng)用；協(xié)調(diào)各國的活動等。然后,攻擊者搜索這個有序的序列,嘗試從這個有序的序列中找到兩項ie

和je,滿足其中攻擊者能在

步操作之內(nèi)找到ie

和je,攻擊者由此獲得明文m=i×j。當(dāng)明文消息的長度為40~60位時,明文可被分解成兩個大小相當(dāng)?shù)恼麛?shù)的概率為18%~50%。舉例來說,假設(shè)用1024位模數(shù)的RSA加密一個長度為56的位串,如果能夠提供228×1024=238位(約為32GB)的存儲空間,則經(jīng)過229次模指數(shù)運算,就可以有很大的把握找出明文位串,它是兩個28位的整數(shù)之積。這種空間和時間用一臺普通的個人計算機就可以實現(xiàn)。這說明用RSA直接加密一些比較短的位串(如DES等單鑰體制的密鑰或者長度小于64位的系統(tǒng)口令等)是非常危險的。7.3.3RSA算法的參數(shù)選擇通過對RSA算法的安全性分析可以看出,要想保證RSA體制的安全,必須審慎選擇系統(tǒng)的各個參數(shù)。下面討論參數(shù)選擇時需要注意的一些問題。1.模數(shù)n的確定首先,多用戶之間共用模數(shù)會導(dǎo)致共用模數(shù)攻擊,因此不能在多個用戶之間共用模數(shù)。其次,模數(shù)n是兩個大素數(shù)p和q的乘積,因此模數(shù)n的確定問題可轉(zhuǎn)化為如何恰當(dāng)?shù)剡x擇p和q。p和q除了要足夠大(100位以上的十進制整數(shù))以外,還應(yīng)滿足如下要求:(1)p和q應(yīng)為強素數(shù)。(2)p與q之差要合適。(3)p-1與q-1的最大公因子要小。一個素數(shù)p稱為強素數(shù)或一級素數(shù),如果p滿足條件:(1)存在兩個大素數(shù)p1和p2,使得p1|(p-1)、p2|(p+1),(2)存在4個大素數(shù)r1,s1,r2和s2,使得r1|(p1-1)、s1|(p1+1)、r2|(p2-1)、s2|(p2+1),則稱p1和p2為2級素數(shù),r1,s1,r2和s2為3級素數(shù)。為什么要采用強素數(shù)?這是因為p和q的取值會影響分解模數(shù)n的困難性。若p或q不是強素數(shù),則可通過下面的方法分解模數(shù)n。假設(shè)p-1有k個素因子,由算術(shù)基本定理可得

其中pi為素數(shù),ai為正整數(shù)(i=1,2,…,k)。如果pi都很小,不妨設(shè)pi<A(A為已知的小整數(shù)),構(gòu)造其中,a≥max{ai},顯然有(p-1)|R。因為任意小于素數(shù)p的正整數(shù)t均與p互素,不妨設(shè)t=2,由歐拉定理可知因而tR=2R≡1modp。計算X≡tRmodn≡2Rmodn,若X=1,則令t=3,重新計算X,直到X≠1。此時由gcd(X-1,n)=p,得到n的分解因子p和q。對于q也可以進行類似討論。因此p-1和q-1必須有大素因子,即p和q要為強素數(shù)。如果p與q之差很小,則由

可得

是一個小的平方數(shù),所以

近似。令

可以從大于

的整數(shù)中依次嘗試u且從而解出p與q。

盡管要求p與q之差不能太小,但二者之差也不能很大。如果很大,則其中一個必然較小,那么可以從一個小的素數(shù)開始依次嘗試,最終分解n。因此,p與q之差要適當(dāng),一般是長度相差幾位。

要求p-1與q-1的最大公因子要小是為了防止迭代攻擊。假設(shè)攻擊者截獲了密文c≡memodn,可以進行如下迭代攻擊:如果存在t,使得etmodφ(n)≡1,則有整數(shù)k,使et=kφ(n)+1,那么由歐拉定理可知與此同時還有

所以

因而如果t較小,則這種迭代攻擊很容易成功。由歐拉定理可知若p-1與q-1的最大公因子較小,則t較大;如果t大到(p-1)(q-1)的一半,則迭代攻擊難以奏效。2.加密密鑰e的選取加密密鑰e要滿足以下幾個條件:(1)e要與模數(shù)n的歐拉函數(shù)值φ(n)互素,即gcd(e,φ(n))=1,否則無法計算解密密鑰d。這一要求容易滿足,現(xiàn)在已經(jīng)證明兩個隨機數(shù)互素的概率約為3/5。(2)e不能太小,e太小容易遭受低加密指數(shù)攻擊。另外,如果e和m都很小且滿足me<n,此時密文c≡memodn不需要經(jīng)過模運算可直接得到,這樣由c開e次方可得明文m。(3)e在模數(shù)φ(n)下的階要足夠大,即滿足etmodφ(n)≡1的最小正整數(shù)t要盡可能大,一般應(yīng)達到(p-1)(q-1)/2。3.解密密鑰d的選取加密密鑰e選定之后,利用擴展的歐幾里得算法可以求出解密密鑰d。類似于對加密密鑰e的要求,解密密鑰d也不能太小,否則容易遭受已知明文攻擊。如果對明文m加密得到密文c,則在解密密鑰d很小的情況下,從某個正整數(shù)開始依次嘗試,直接找出一個數(shù)t滿足ctmodn≡m,這個t就是解密密鑰d。Wiener于1990年利用連分數(shù)理論證明了當(dāng)解密密鑰d小于

時很容易分解模數(shù)n,然后求出了解密密鑰d。因此,一般要求d不能小于7.4Rabin算法7.4.1求解數(shù)模下的平方根問題定理7.1假定n是大于1的奇數(shù),且有如下分解其中,pi

是互不相同的素數(shù),ei

是正整數(shù)。對于與n互素的整數(shù)a,如果a是模pi

的平方剩余,對所有的i=1,2,…,l都成立,那么同余方程x2≡amodn存在2l個模n的解。證明

根據(jù)已知條件,由同余理論可知,同余方程x2≡amodn等價于同余方程組:因此,問題轉(zhuǎn)化為求解上述同余方程組。對所有的i=1,2,…,l,由a是模pi

的平方剩余可知,同余方程

有兩個模

的解,分別記為這樣我們可以得到一系列一次同余方程組其中,bi可取bi,1或者bi,2。由中國剩余定理可知,每一個這樣的一次同余方程組都有唯一的模n解。由于每個bi可取bi,1和bi,2中的一個,所以可以產(chǎn)生2l

個不同的(b1,…,bl),即共有2l

個不同的一次同余方程組。因此同余方程組共有2l

個模n的解,即原同余方程x2≡amodn存在2l

個模n的解。命題7.2如果素數(shù)p≡3mod4,a是

模p的

平

方

剩

余,那

么a模p的

平

方

根

是證明

根據(jù)a是模p的平方剩余,由Euler準(zhǔn)則可知于是7.4.2Rabin算法的描述對于RSA算法,如果能夠成功分解模數(shù)n,則可攻破RSA系統(tǒng)。因此,攻擊RSA算法的難度不會超過大整數(shù)的分解,但它是否等價于大整數(shù)的分解目前還不知道。本節(jié)討論的Rabin算法既可看成RSA算法的一個特例,也可以看成對RSA算法的一個修正。Rabin算法是一個被證明其破解難度正好等價于大整數(shù)分解的公鑰密碼算法,它也是第一個可證明安全性的公鑰密碼算法。Rabin算法的安全性基于求解合數(shù)模下的平方根的困難性。Rabin算法的基本框架類似于RSA,也依賴于以兩個大素數(shù)之積為模數(shù)的模指數(shù)運算,但Rabin算法對模數(shù)的選擇和加解密模指數(shù)運算提出了特別的要求。Rabin算法的描述如下:選取兩個相異的滿足p=q≡3mod4的大素數(shù)p和q,以n=p×q為模數(shù),再隨機選取一個整數(shù)b∈?n。算法以(n,b)為公開密鑰,(p,q)為私有密鑰。加密變換:對于一個明文消息m,通過計算c≡m(m+b)modn得到密文c。解密變換:為了解密出密文c,需要求解二次同余方程如果令

上面的方程可改寫為如果再令

方程進一步可改寫為因此解密問題歸結(jié)為求C模n的平方根。方程x2≡Cmodn有4個解。由命題7.2可知,當(dāng)p=q≡3mod4時,方程x2≡Cmodp的2個解是方程x2≡Cmodq的2個解是例如，在萬方中外標(biāo)準(zhǔn)數(shù)據(jù)庫中檢索“永磁式直流電機”方面的標(biāo)準(zhǔn)文獻，可以通過高級檢索方式，選擇“題名或關(guān)鍵詞”字段，分別輸入“永磁式”和“直流電機”；邏輯運算符選擇“與”，單擊“檢索”按鈕，即可得到檢索結(jié)果(如圖7-9所示)。因此,可以組合得到4個一次同余方程組:利用中國剩余定理解這4個同余方程組得到4個解,它們是C模n的4個平方根。要尋找的明文就是4個解的其中之一。由上面的敘述可知,Rabin算法的加密函數(shù)不是單射,解密具有不確定性,合法用戶不能確切地知道到底哪一個解是真正的明文。如果加密之前在明文消息中插入一些冗余信息,比如用戶的身份數(shù)字、日期、時間或者事先約定的某個數(shù)值等,可以幫助收信者準(zhǔn)確識別解密后的明文。Rabin算法的解密過程是尋找C模n的平方根，這個問題的難度等價于n的因子分解。盡管計算模為素數(shù)的平方根是多項式時間可解的，但其過程仍然很復(fù)雜。要求p與q是模4同余3是為了使解密的計算和分析變得容易。在實踐中，通常使用Rabin算法的一個變形或者特例，即取b=0。在這種情況下，加解密處理變成如下形式:這種變形的Rabin算法可以看作加密指數(shù)e=2的RSA算法。7.5ElGamal算法7.5.1離散對數(shù)問題假設(shè)a是群G中的任一元素,滿足at=1的最小正整數(shù)t稱為元素a的階,如果不存在這樣的正整數(shù)t,則稱a的階為∞。假設(shè)群G為有限乘法群?p*(p為素數(shù)),我們將滿足at≡1modp的最小正整數(shù)t稱為元素a在模p下的階。如果元素a模p的階等于φ(p),則稱a是p的本原根或者本原元。如果模數(shù)取任意的正整數(shù),上面模運算下元素的階和本原根的概念仍然有意義。設(shè)a是素數(shù)p的本原根,那么在模p下互不相同且正好產(chǎn)生1到φ(p)=p-1的所有值。因此,對于b∈{1,2,…,p-1},一定存在唯一的x∈{1,2,…,p-1}滿足b≡axmodp,稱x為模p下以a為底b的離散對數(shù),并記為x≡logabmodp。如果已知a、p和x,那么使用快速指數(shù)算法可以輕易地算出b;但如果僅知a、p和b,特別是當(dāng)p的取值特別大時,要想求出x是非常困難的,目前還沒有特別有效的多項式時間算法。因此,離散對數(shù)問題可以用于設(shè)計公鑰密碼算法。為了使基于離散對數(shù)問題的公鑰密碼算法具有足夠的密碼強度,一般要求模數(shù)p的長度在150位以上。7.5.2ElGamal算法的描述設(shè)p是一個素數(shù),?p

是含有p個元素的有限域,?p*是?p

的乘法群,p的大小足以使乘法群?p*上的離散對數(shù)難以計算。選擇?p*的一個生成元g和一個秘密隨機數(shù)a,要求它們都小于p,計算公開密鑰取為(y,g,p),且g和p可由一組用戶共享;a作為私有密鑰,需要保密。加密變換:對于消息m,秘密選取一個隨機數(shù)k∈?p-1,然后計算c1與c2并聯(lián)構(gòu)成密文,即密文c=(c1,c2),因此密文的長度是明文的兩倍。解密變換:由加密變換可知所以解密結(jié)果是正確的。7.5.3ElGamal算法的安全性ElGamal密碼體制的安全性基于有限群?p*上離散對數(shù)問題的困難性。有學(xué)者曾提出,模p生成的離散對數(shù)密碼可能存在陷門,一些“弱”素數(shù)p下的離散對數(shù)較容易求解。因此,要仔細選擇p,且g應(yīng)是模p的本原根,一般認為這類問題是困難的,而且目前尚未發(fā)現(xiàn)有效解決該問題的多項式時間算法。此外,為了抵抗已知的攻擊,p應(yīng)該至少是300位的十進制整數(shù),并且p-1應(yīng)該至少有一個較大的素數(shù)因子。ElGamal算法的安全性還來自加密的不確定性。ElGamal體制的一個顯著特征是在加密過程中引入了隨機數(shù),這意味著相同的明文可能產(chǎn)生不同的密文,能夠給密碼分析者制造更大的困難。但在某些情況下,ElGamal體制也可能向攻擊者泄露部分信息。比如在實際應(yīng)用中,為了提高效率,一般會選用階r遠小于p的生成元g,在這種情況下,如果一個比較短的消息m并不是由g生成的子群中的元素,那么類似于RSA體制的中間相遇攻擊則有可能成功。這是因為對于密文攻擊者能夠得到即攻擊者將ElGamal的不確定加密體制轉(zhuǎn)化成一種確定性的算法,且具有指數(shù)運算的可乘性。因此,對于一個容易分解的小尺寸的消息,攻擊者能夠?qū)rmodp實施中間相遇攻擊。由此可知,當(dāng)一個明文消息不屬于由g生成的子群的時候,ElGamal密碼體制就成為一種確定性的體制。由于確定性加密體制允許使用多次嘗試的方法來尋找小的明文消息,因此泄露了部分信息。所以,在應(yīng)用ElGamal公鑰體制,特別是推廣的ElGamal體制的時候,一定要注意生成元g的選擇,確保每一個可能的明文消息都是由g生成的。7.6橢圓曲線密碼7.6.1橢圓曲線的定義與性質(zhì)橢圓曲線的圖形并非橢圓,只是因為它的曲線方程與計算橢圓周長的方程類似,所以將其叫作橢圓曲線。通常所說的橢圓曲線是指由Weierstrass方程所確定的平面曲線,其中a,b,c,d,e取自某個域F并滿足一些簡單的條件。橢圓曲線通常用字母E表示,滿足曲線方程的序偶(x,y)就是域F上的橢圓曲線E上的點。域F可以是數(shù)域,也可以是某個有限域GF(pn)。除了滿足曲線方程的所有點(x,y)之外,橢圓曲線E還包括一個特殊的點O,稱為無窮遠點。在上面的Weierstrass方程中用

代替y,得到其中,因此,橢圓曲線關(guān)于x軸對稱。圖7-2是實數(shù)域上橢圓曲線的兩個例子。我們可以在橢圓曲線E上定義一個二元運算,使其成為Abel群,通常稱這個運算為加法,并用表示,其定義如下所示。(1)取無窮遠點O為單位元,因此對任何點(2)如果有三個點P,Q,R∈E且在同一條直線,那么(3)設(shè)P=(x,y)∈E,那么P的加法逆元定義為

這是因為P與

的連線延長到無窮遠時將經(jīng)過無窮遠點O,所以P,和O三點共線,即而橢圓曲線E是關(guān)于x軸對稱的,所以可以將-P定義為P點關(guān)于x軸的對稱點(x,-y)∈E。此外,-O=O。(4)若P和Q是橢圓曲線E上x坐標(biāo)不相同的兩個點,那么P⊕Q定義如下:過P和Q畫一條直線L交橢圓曲線于另一點R,因為P≠Q(mào),所以R是唯一的。因此,P⊕Q⊕R=O,即P⊕Q=-R。也就是說,P⊕Q是P與Q的連線L交橢圓曲線E上的另一點R關(guān)于x軸的對稱點。如上定義的加法運算符合群的定義,同時滿足交換律,因此(E,⊕)是一個Abel群。在密碼學(xué)中使用的橢圓曲線通常定義在有限域上。也就是說,橢圓曲線方程中的所有系數(shù)都取自某個有限域GF(pn)。其中,最常用的是由有限域?p(p為素數(shù))上的同余方程確定的橢圓曲線,即由此同余方程的所有解(x,y)∈?p

×?p,再加上一個特殊的無窮遠點O,在上述加法運算下構(gòu)造的Abel群。通常用Ep(a,b)來表示這樣得到的Abel群。可以證明,在實數(shù)域,是保證方程

存在3個不同解(對于給定的y)的充分必要條件;否則,方程的3個解中至少有2個相同,并且稱這樣的橢圓曲線為奇異橢圓曲線。在?p

中要求

以保證曲線方程的各個解不相同。按照上面給出的加法運算的定義,假設(shè)P(x1,y1)和Q(x2,y2)是橢圓曲線Ep(a,b)上的點,如果P與Q關(guān)于x軸對稱,即x1=x2且y1=-y2,則P⊕Q=O,否則記P⊕Q=R。根據(jù)橢圓曲線的方程和P、Q連線的方程可以計算出R點的坐標(biāo)(x3,y3)如下(在此略去計算過程):其中:實際上,?p上的橢圓曲線只是一些不連續(xù)的點,并不像實數(shù)域上橢圓曲線有直觀的幾何解釋,但同樣定義的加法運算能夠保證(Ep(a,b),⊕)仍然是一個Abel群。7.6.2橢圓曲線上的密碼體制和ElGamal密碼體制一樣,橢圓曲線密碼體制也是建立在離散對數(shù)問題上的公鑰體制。我們已經(jīng)知道,由橢圓曲線可以生成Abel群,于是可以在這樣的群上構(gòu)造離散對數(shù)問題。我們把使用有限域上橢圓曲線產(chǎn)生的Abel群Ep(a,b)構(gòu)造的離散對數(shù)問題稱為橢圓曲線上的離散對數(shù)。目前的研究結(jié)果表明,解決橢圓曲線上的離散對數(shù)問題的最好算法比解決標(biāo)準(zhǔn)有限域上的離散對數(shù)問題的最好算法還要慢許多,這保證了在橢圓曲線上構(gòu)造密碼體制的可行性。橢圓曲線上的離散對數(shù)描述如下:設(shè)Ep(a,b)是有限域?p(p>3的素數(shù))上的一條橢圓曲線產(chǎn)生的Abel群,對于Ep(a,b)上的任意兩點P和Q,尋找一個整數(shù)k<p,使得Q=kP。如果已知k和P,則Q可直接求得;反過來,由P和Q很難計算出k,特別是當(dāng)k很大時,這個難度不亞于對k進行分解。這個問題稱為橢圓曲線上的離散對數(shù)問題,有限域上的橢圓曲線提供了構(gòu)造離散對數(shù)的一個新途徑,可以將這種建立在橢圓曲線上的離散對數(shù)問題應(yīng)用于公鑰密碼體制的構(gòu)造。橢圓曲線上的ElGamal公鑰密碼體制的描述如下:設(shè)Ep(a,b)是有限域?p(p>3的素數(shù))上的一條橢圓曲線產(chǎn)生的Abel群,任取g∈Ep(a,b),且滿足在由g生成的子群H上的橢圓曲線離散對數(shù)問題是難解的。再取正整數(shù)x<p,計算y=xg。公開密鑰取為g,y,p,私有密鑰取為x。加密變換:對于明文m,隨機選取正整數(shù)k<p,計算c1=kg和c2=m⊕ky。密文為c=(c1,c2)=(kg,m⊕ky)。解密變換:m=c2⊕(-xc1)。解密的正確性是顯而易見的。在使用橢圓曲線密碼算法時,需要注意一個問題:橢圓曲線密碼算法中的運算都是群Ep(a,b)上元素的加法運算,因此要用某種編碼方法將原始明文消息m嵌入到Ep(a,b)的點上,然后才能使用群Ep(a,b)的運算規(guī)則進行加法運算。原始消息到Ep(a,b)上點的嵌入編碼方法這里不予討論。下面利用例7.7的橢圓曲線及其Abel群E11(1,6)來說明橢圓曲線密碼體制的操作細節(jié)。7.6.3橢圓曲線密碼算法的特性求解橢圓曲線上離散對數(shù)問題的難度比求解標(biāo)準(zhǔn)有限域上離散對數(shù)問題的難度更高,在同等難度的情況下,橢圓曲線密碼算法比RSA等基于因數(shù)分解的密碼算法有更小密鑰量。因此橢圓曲線密碼算法具有更好的密碼學(xué)特性,具體如下:(1)安全性高?，F(xiàn)在已知的解決橢圓曲線上離散對數(shù)問題的最好算法是以Pollardρ算法為代表的通用離散對數(shù)求解算法,該類算法的時間復(fù)雜度為

其中ρmax是Ep(a,b)的最大循環(huán)子群的階的最大素因子。而要解決有限域?p上的標(biāo)準(zhǔn)離散對數(shù)問題,則可用指數(shù)積分法,它的時間復(fù)雜度為

其中,ρ是模數(shù),為素數(shù)。顯然,橢圓曲線離散對數(shù)比有限域上的標(biāo)準(zhǔn)離散對數(shù)的復(fù)雜度更高,因此橢圓曲線密碼體制也更安全。(2)密鑰量小,運算速度快。在同等安全級別的前提下,橢圓曲線密碼體制比其他公鑰密碼體制所需的密鑰位數(shù)要少得多。在算法的執(zhí)行速度方面,橢圓曲線上的一次群運算最終化為域上不超過15次的乘法運算,因此在算法實現(xiàn)上不成問題,但目前還難以將橢圓曲線與現(xiàn)有的其他公鑰體制進行準(zhǔn)確的定量比較,一個粗略的結(jié)論是橢圓曲線密碼體制比相應(yīng)的標(biāo)準(zhǔn)離散對數(shù)密碼體制快,且在

解

密

方

面

比RSA快,而

在

驗

證

加

密

方

面

比RSA慢。所

以橢圓曲線密碼體制除了常規(guī)的應(yīng)用以外,在移動計算設(shè)備和智能卡等存儲與計算能力受限的領(lǐng)域特別有優(yōu)勢。表7-2是在同等安全級別下,RSA算法與橢圓曲線算法所需密鑰大小的對比。(3)密碼資源豐富,靈活性好。對于一個給定的有限域,其上的循環(huán)群或者循環(huán)子群也

是

確

定

的

有

限

多

個。而

有限域上的橢圓曲線可以通過改變曲線方程的系數(shù),得到大量的不同曲線,進而生成更多的循環(huán)群,這為算法的安全性增加了額外的保障,同時也為算法的實現(xiàn)提供了更大的靈活性。盡管橢圓曲線公鑰體制具有如此好的密碼學(xué)特性,經(jīng)過眾多密碼學(xué)家多年來的深入分析,還是發(fā)現(xiàn)了一些問題。首先,正如DES算法存在某些容易破解的弱密鑰一樣,也有一些橢圓曲線,在其上建立的離散對數(shù)是易于求

解

的,并

且

有

人

給

出

了

對

應(yīng)

的

攻

擊

方

法。例

如,1993年,Menezes、Okamoto和Vanstone發(fā)

現(xiàn)

了

一

類

超

奇

異

橢

圓

曲

線

可

用

亞

指

數(shù)

攻

擊

法

破

解,這種方法現(xiàn)在被稱為MOV攻擊法。隨后,Semaev又發(fā)現(xiàn)了一類異常橢圓曲線可在線性時間內(nèi)求解。因此,在構(gòu)造橢

圓

曲

線

密

碼

體

制

時

應(yīng)

避

免

使

用

這

兩

類

曲

線。為

此,在選擇橢圓曲線時應(yīng)使所用Ep(a,b)的循環(huán)子群的階具有長度不少于160位的素因子。這樣的橢圓曲線離散對數(shù)的安全水平相當(dāng)于有限域?p上標(biāo)準(zhǔn)離散對數(shù)在p的長度不少于1000位情況下的安全性。之

所

以

有

如

此

大

的

差

異,是

因

為

已

知

的

指

數(shù)

積

分

攻

擊對橢圓曲線離散對數(shù)不起作用。其次,為抵抗已知的諸如Polardρ等求解橢圓曲線離散對數(shù)算法的攻擊,也應(yīng)該使橢圓曲線群Ep(a,b)具有階足夠大的循環(huán)子群,這一點與上述要求是一致的?？傊?已經(jīng)發(fā)現(xiàn)的橢圓曲線密碼體制的缺點還不多,大多

數(shù)

密

碼

學(xué)

家

對

這

種

公

鑰體制仍持

樂

觀

態(tài)

度,相

關(guān)

的

實

現(xiàn)

和

標(biāo)

準(zhǔn)

化

工

作

已

經(jīng)

逐

步

展

開,應(yīng)

用

的

領(lǐng)

域

也

日

漸擴大。7.7SM2公鑰加密算法7.7.1SM2算法的描述我國從2001年開始組織研究自主知識產(chǎn)權(quán)的ECC(,橢圓曲線密碼學(xué))算法,2004年研制完成SM2橢圓曲線公鑰密碼算法(簡稱SM2算法),2010年12月首次公開發(fā)布,2012年3月成為中國商用密碼標(biāo)準(zhǔn)(GM/T0003—2012),2016年8月成為中國國家密碼標(biāo)準(zhǔn)(GB/T32918—2016)。當(dāng)前,我國商用密碼行業(yè)對SM2算法正在進行大規(guī)模地應(yīng)用和推廣,2011年3月中國人民銀行發(fā)布了《中國金融集成電路(IC)卡規(guī)范》(簡稱PBOC3.0),PBOC3.0采用了SM2算法以增強金融IC卡應(yīng)用的安全性,以PBOC3.0為參考規(guī)范的非金融類應(yīng)用也基本采用了SM2算法。國際可信計算組織(TrustedComputingGroup,TCG)發(fā)布的TPM2.0規(guī)范采納了SM2算法。2016年10月,ISO/IECSC27會議通過了SM2算法標(biāo)準(zhǔn)草案,SM2算法進入了ISO148883正式文本階段。這些重要事件將進一步促進SM2算法的應(yīng)用和推廣。SM2算法包含3個不同功能的算法:公鑰加密算法、數(shù)字簽名算法、密鑰交換協(xié)議。本節(jié)只介紹SM2公鑰加密算法。迄今為止的相關(guān)研究表明,SM2算法的可證安全性已經(jīng)達到了公鑰密碼算法的最高安全級別,其實現(xiàn)效率相當(dāng)于或略優(yōu)于一些國際標(biāo)準(zhǔn)的同類型橢圓曲線密碼算法。SM2公鑰加密算法共包含3個子算法,分別是密鑰派生函數(shù)、加密算法、解密算法。算法初始化時首先選擇有限域Fq上的橢圓曲線E,同時選擇該曲線上的基點G=(xG,yG),G的階為n,記稱為余因子。選擇Hash函數(shù)Hv(x),輸出長度為v的Hash值,目前SM2一般取v=256。1.密鑰派生函數(shù)密鑰生成函數(shù)記作KDF(Z,Klen),其中:輸入:位串Z,整數(shù)Klen(該值表示要獲得的密鑰長度,要求小于(232-1)v)。輸出:長度為Klen的密鑰K。具體的函數(shù)計算過程如下:(1)初始化一個32位的計數(shù)器ct=00000001(十六進制的形式)。(2)循環(huán)執(zhí)行以下操作,其中ct=1,2,…,(3)若

不是整數(shù),則最后一輪算出來

只取最左邊的(4)令

輸出長度為Klen的密鑰K。2.SM2加密算法消息發(fā)送者A加密明文消息,將密文發(fā)送給消息接收者B,B解密密文得到原始的明文消息。設(shè)B的密鑰對分別為私鑰dB∈{1,2,…,n-1}和公鑰PB=dBG,待加密消息為M,M的長度為Klen,則A需要執(zhí)行以下操作:(1)使用隨機數(shù)生成器產(chǎn)生隨機數(shù)k∈{1,2,…,n-1}。(2)計算橢圓曲線點C1=kG=(x1,y1),將C1轉(zhuǎn)換為位串。(3)計算橢圓曲線點S=hPB,若S是無窮遠點,則報錯退出。(4)計算橢圓曲線點kPB=(x2,y2),將坐標(biāo)轉(zhuǎn)換為位串。(5)計算t=KDF(x2‖y2,Klen),若t為全0位串,則返回1,重新選擇k。(6)計算C2=M⊕t。(7)計算C3=Hash(x2‖M‖y2)。(8)輸出密文C=C1‖C2‖C3。SM2的加密流程如圖7-3所示。3.SM2解密算法接收者B接收到密文C=C1‖C2‖C3以后,執(zhí)行以下操作進行解密:(1)從C中取出位串C1,將C1的數(shù)據(jù)類型轉(zhuǎn)換為橢圓曲線上的點,驗證C1是否滿足橢圓曲線方程,若不滿足則報錯退出。(2)計算橢圓曲線上的點S=hC1,若S是無窮遠點,則報錯退出。(3)計算dBC1=(x1,y2),將坐標(biāo)轉(zhuǎn)換為位串。(4)計算t=KDF(x2‖y2,Klen),若t為全0位串,則報錯退出。(5)從C中取出位串C2,計算M'=C2⊕t。(6)計算u=Hash(x2‖M'‖y2),從C中取出位串C3,若u≠C3,則報錯退出。(7)輸出明文M'。SM2的解密流程如圖7-4所示。4.解密的正確性分析根據(jù)上述解密算法的描述,如果整個解密過程不出現(xiàn)報錯退出的情況,則第3步計算的(x2,y2)與加密算法中的一致,即此時第4步得到的t也與加密算法中的一致,最終第7步得到的M'滿足此外,第6步計算并與C3進行比較,起到的是校驗的作用,若相等則說明解密正確,否則解密有錯誤。7.7.2SM2加密算法的分析1.安全性分析由SM2的加解密過程可以看出,接收者B的公私鑰滿足條件PB=dBG。顯然,在已知G的前提下,由私鑰dB計算公鑰PB是容易的,但是要由公鑰PB計算私鑰dB就等價于求解橢圓曲線上的離散對數(shù)問題。離散對數(shù)問題的求解關(guān)系到SM2的安全性,因此SM2算法必須選擇安全的橢圓曲線,即避免弱橢圓曲線。目前對于一般橢圓曲線上的離散對數(shù)問題,求解的方法均為采用指數(shù)級計算復(fù)雜度算法,未發(fā)現(xiàn)有效的亞指數(shù)級計算復(fù)雜度的攻擊方法,但是對于某些特殊曲線上的離散對數(shù)問題,存在多項式級計算復(fù)雜度或者亞指數(shù)級計算復(fù)雜度算法,這些曲線稱為弱橢圓曲線。一般來說,為了避免Pollard方法的攻擊,基點G的階n必須是一個足夠大的素數(shù),即G生成一個素數(shù)階循環(huán)群。SM2算法采用的橢圓曲線參數(shù)經(jīng)檢測完全滿足安全性條件,其上的離散對數(shù)問題不存在亞指數(shù)級計算復(fù)雜度的攻擊方法,n為256位的素數(shù),具有足夠的長度。SM2算法加密的過程中使用了Hash函數(shù),密文中的一部分C3是具有校驗功能的Hash值,而計算C3所使用的位串又是根據(jù)一次性的秘密隨機數(shù)生成的。攻擊者不能獲得或偽造任何有效的密文,保證SM2算法具備CCA2的安全性。2.效率分析一般來說,ECC類加密算法的實現(xiàn)效率本身就優(yōu)于RSA。SM2加密算法的實現(xiàn)效率比起普通的ECC加密算法更高,這主要體現(xiàn)在加密的核心步驟C2=M⊕t是逐位模2加法,具有很高的加密速度。SM2加密算法的唯一不足在于密文偏長。與普通ECC加密算法相比,SM2生成的密文包含了3部分,數(shù)據(jù)擴張程度嚴重,但是擴張的密文中的C3具備校驗功能,又進一步提高了算法的數(shù)據(jù)完整性和可靠性。目

前,SM2加

密

算

法

已

經(jīng)

得

到

了

廣

泛

的

應(yīng)

用

。例

如,我

國

正

在

推

廣

使

用

的eID(ElectronicIdentity,公民網(wǎng)絡(luò)電子身份標(biāo)識)就使用了SM2算法。此外,SM2在可信計算、通信、金融、衛(wèi)生、電力系統(tǒng)等領(lǐng)域都有著廣泛的應(yīng)用。7.8基于身份的公鑰密碼體制7.8.1概述在公鑰密碼的實際應(yīng)用中,需要一種機制能夠很方便地驗證公鑰與主體身份之間的聯(lián)系,對于這一問題,傳統(tǒng)的解決方法是采用基于公鑰基礎(chǔ)設(shè)施(PublicKeyInfrastructure,PKI)的公鑰證書機制,但這種方式的證書管理過程需要很高的計算開銷和存儲開銷。為了簡化證書

管

理

工

作,1984年,Shamir首

先

提

出

了

基

于

身

份

密

碼

體

制的思想。在這種新的密碼系統(tǒng)中,用戶的身份信息直接作為公鑰,或者公鑰可以容易地從身份信息中計算得到,而私鑰則由可信的第三方私鑰生成中心產(chǎn)生后發(fā)送給用戶。當(dāng)用戶使用通信對方的公鑰時,僅需知道其身份信息,而無須獲得并驗證其公鑰證書,這樣就大大節(jié)省了公鑰證書管理和使用中的開銷。為了闡述IBC的工作過程,Shamir設(shè)計了一個郵件加密的方案,當(dāng)用戶Alice向Bob發(fā)送郵件時,假設(shè)Bob的郵箱為Bob@,則Alice直接用公開的字符串Bob@加密信息即可,無須從任何證書管理機構(gòu)獲得Bob的公鑰證書。Bob收到密文時,與PKG聯(lián)系,通過認證后,得到自己的私鑰,從而解密信息。這樣做可以大大簡化郵件系統(tǒng)中的密鑰管理,使公鑰密碼的應(yīng)用變得極為方便?？梢钥吹?基于身份的密碼系統(tǒng)與傳統(tǒng)基于證書的密碼系統(tǒng)都屬于公鑰密碼體制,具有相似的功能,但是基于身份的密碼系統(tǒng)的用戶公鑰直接與身份信息自然地綁定在一起,不再需要證書和公鑰目錄,因此在密鑰生成和管理方面具有很大的優(yōu)勢,節(jié)約了計算和通信成本。一個理想的基于身份的密碼系統(tǒng)應(yīng)滿足以下幾個特點:(1)用戶只需知道通信對方的身份。(2)用戶不用存儲任何公鑰、證書之類的列表。(3)PKG只是在系統(tǒng)的建立階段提供服務(wù),且用戶絕對無條件信任該可信機構(gòu)。傳統(tǒng)基于證書密碼體制與基于身份的密碼體制的相同之處在于:(1)都屬于公開密鑰體系,具有一對公開密鑰和私有密鑰,公開密鑰可以公開,私有密鑰由用戶秘密保存。(2)用戶的身份都需要認證。傳統(tǒng)基于證書密碼體制中,用戶需要向證書權(quán)威機構(gòu)CA證實自己的身份;基于身份的密碼體制中,用戶需要向PKG證實自己的身份。(3)公鑰和私鑰用于加密方案中,都是公鑰用于加密,私鑰用于解密;用于簽名方案中,都是私鑰用于簽名,公鑰用于驗證簽名。(4)體系的安全性都可以依賴于大數(shù)分解、離散對數(shù)求解、橢圓曲線求解等數(shù)學(xué)難題。傳統(tǒng)基于證書密碼體制與基于身份的密碼體制的不同之處在于:(1)密鑰生成過程不同。傳統(tǒng)基于證書的密碼體制中,用戶的私鑰和公鑰同時產(chǎn)生。由用戶先選取私鑰,然后計算出公鑰=F(私鑰)(其中F是一個從私鑰空間映射到公鑰空間的有效單向函數(shù))。基于身份的密碼體制中,用戶的公鑰是已經(jīng)被公開的用戶的身份信息,由PKG為用戶生成私鑰,私鑰=F(主密鑰,公鑰),其中主密鑰由PKG秘密保存。由此可見,這兩種密碼體制的密鑰生成過程正好相反。(2)用戶身份信息的獲取方式不同。在傳統(tǒng)基于證書的密碼體制中,用戶的身份